## 2012-11-10

### Bitwise tricks in C

This blog post shows some tricky uses of bitwise operators in C, mostly to compute some functions quickly, processing many bits at a time in a parallel way.

See also Bitwise tricks in Java for the same functions in Java.

See more tricks like this in the GNU Classpath source of java.lang.Integer and java.lang.Long. Check the methods bitCount, rotateLeft, rotateRight, highestOneBit, numberOfLeadingZeros, lowestOneBit, numberOfTrailingZeros, reverse.

```#include <stdint.h>

See even better tricks in Chapter 2 of Hacker's Delight, in Bit Twiddling Hacks and in HAKMEM.

char is_power_of_two_32(uint32_t x) {
return !(x & (x - 1));
}

char is_power_of_two_64(uint64_t x) {
return !(x & (x - 1));
}

int bitcount_32(uint32_t x) {
x = (x & 0x55555555) + ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);
x = (x & 0x0000FFFF) + (x >> 16);
return x;
}

int bitcount_64(uint64_t x) {
x = (x & 0x5555555555555555LL) + ((x >>  1) & 0x5555555555555555LL);
x = (x & 0x3333333333333333LL) + ((x >>  2) & 0x3333333333333333LL);
x = (x & 0x0F0F0F0F0F0F0F0FLL) + ((x >>  4) & 0x0F0F0F0F0F0F0F0FLL);
x = (x & 0x00FF00FF00FF00FFLL) + ((x >>  8) & 0x00FF00FF00FF00FFLL);
x = (x & 0x0000FFFF0000FFFFLL) + ((x >> 16) & 0x0000FFFF0000FFFFLL);
x = (x & 0x00000000FFFFFFFFLL) + (x >> 32);
return x;
}

uint32_t reverse_32(uint32_t x) {
x = (x & 0x55555555) <<  1 | ((x >> 1) & 0x55555555);
x = (x & 0x33333333) <<  2 | ((x >> 2) & 0x33333333);
x = (x & 0x0F0F0F0F) <<  4 | ((x >> 4) & 0x0F0F0F0F);
x = (x & 0x00FF00FF) <<  8 | ((x >> 8) & 0x00FF00FF);
x =                x << 16 | x >> 16;
return x;
}

uint64_t reverse_64(uint64_t x) {
x = (x & 0x5555555555555555LL) <<  1 | ((x >>  1) & 0x5555555555555555LL);
x = (x & 0x3333333333333333LL) <<  2 | ((x >>  2) & 0x3333333333333333LL);
x = (x & 0x0F0F0F0F0F0F0F0FLL) <<  4 | ((x >>  4) & 0x0F0F0F0F0F0F0F0FLL);
x = (x & 0x00FF00FF00FF00FFLL) <<  8 | ((x >>  8) & 0x00FF00FF00FF00FFLL);
x = (x & 0x0000FFFF0000FFFFLL) << 16 | ((x >> 16) & 0x0000FFFF0000FFFFLL);
x =                x << 32 | x >> 32;
return x;
}

int floor_log2_32(uint32_t x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
return bitcount_32(x) - 1;
}

int floor_log2_64(uint64_t x) {
x |= x >> 1;
x |= x >> 2;
x |= x >> 4;
x |= x >> 8;
x |= x >> 16;
x |= x >> 32;
return bitcount_64(x) - 1;
}```

#### 1 comment:

zsbana said...

As an alternate solution, get the library libecb "http://software.schmorp.de/pkg/libecb.html". This has implementations for all functions listed here, except for reverse_64. The library will choose machine-specific nonportable versions in some cases, so it will usually give a better performance than the functions here, but will fall back to generic implementations similar to these if it can't.