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;
}