Bitwise tricks in Java

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 C for the same functions in C and C++.

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.

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

public class BitTricks {
  public static boolean is_power_of_two(int x) {
    return (x & (x - 1)) == 0;
  }

  public static boolean is_power_of_two(long x) {
    return (x & (x - 1)) == 0;
  }

  public static int bitcount(int 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;
  }

  public static int bitcount(long x) {
    x = (x & 0x5555555555555555L) + ((x >>  1) & 0x5555555555555555L);
    x = (x & 0x3333333333333333L) + ((x >>  2) & 0x3333333333333333L);
    x = (x & 0x0F0F0F0F0F0F0F0FL) + ((x >>  4) & 0x0F0F0F0F0F0F0F0FL);
    x = (x & 0x00FF00FF00FF00FFL) + ((x >>  8) & 0x00FF00FF00FF00FFL);
    x = (x & 0x0000FFFF0000FFFFL) + ((x >> 16) & 0x0000FFFF0000FFFFL);
    return (int)x + (int)(x >>> 32);
  }

  public static int reverse(int 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;
  }

  public static long reverse(long x) {
    x = (x & 0x5555555555555555L) <<  1 | ((x >>  1) & 0x5555555555555555L);
    x = (x & 0x3333333333333333L) <<  2 | ((x >>  2) & 0x3333333333333333L);
    x = (x & 0x0F0F0F0F0F0F0F0FL) <<  4 | ((x >>  4) & 0x0F0F0F0F0F0F0F0FL);
    x = (x & 0x00FF00FF00FF00FFL) <<  8 | ((x >>  8) & 0x00FF00FF00FF00FFL);
    x = (x & 0x0000FFFF0000FFFFL) << 16 | ((x >> 16) & 0x0000FFFF0000FFFFL);
    x =                x << 32 | x >>> 32;
    return x;
  }

  public static int floor_log2(int x) {
    x |= x >>> 1;
    x |= x >>> 2;
    x |= x >>> 4;
    x |= x >>> 8;
    x |= x >>> 16;
    return bitcount(x) - 1;
  }

  public static int floor_log2(long x) {
    x |= x >>> 1;
    x |= x >>> 2;
    x |= x >>> 4;
    x |= x >>> 8;
    x |= x >>> 16;
    x |= x >>> 32;
    return bitcount(x) - 1;
  }
}