Built-in Java bit operations

Integer.bitCount(n) returns the number of 1 bits in the 32-bit two's complement form of n. For negative numbers that includes all the high 1s: Integer.bitCount(-1) is 32.

It is the right tool for popcount: for subsets it gives the size of a mask, and it is a HotSpot intrinsic compiled to the popcnt instruction on x86.

1Integer.bitCount(44);          // 3   (0010 1100)
2Integer.bitCount(-1);          // 32
3int subsetSize = Integer.bitCount(mask);

Integer.numberOfLeadingZeros(n) counts the zero bits above the highest set bit. It is 32 for n = 0 and 0 for any negative number. From it you get the position of the highest set bit, 31 - nlz, and the bit length, 32 - nlz.

A fast floor of the base-2 logarithm is 31 - Integer.numberOfLeadingZeros(n) for n > 0. The next power of two at or above n is Integer.highestOneBit(n - 1) << 1 for n > 1.

1int n = 44;                                        // 0010 1100
2int nlz = Integer.numberOfLeadingZeros(n);         // 26
3int highestBit = 31 - nlz;                         // 5
4int bitLength = 32 - nlz;                          // 6
5int floorLog2 = 31 - Integer.numberOfLeadingZeros(n);
6int highest = Integer.highestOneBit(n);            // 32

Integer.numberOfTrailingZeros(n) counts the zero bits below the lowest set bit. It is 32 for n = 0. It gives the index of the lowest set bit directly, and for a power of two it is the exponent: numberOfTrailingZeros(64) is 6.

Combined with n & -n or Integer.lowestOneBit(n) it is how you loop over the set bits of a mask: take the lowest bit's index, then clear that bit.

1Integer.numberOfTrailingZeros(44);     // 2
2Integer.numberOfTrailingZeros(64);     // 6
3Integer.numberOfTrailingZeros(0);      // 32
4for (int m = mask; m != 0; m &= m - 1) {
5    int bit = Integer.numberOfTrailingZeros(m);
6    visit(bit);
7}

Long has the same methods for 64-bit values: Long.bitCount, Long.numberOfLeadingZeros, Long.numberOfTrailingZeros. Use long and 1L << i for masks of more than 31 bits, such as bitmask DP over up to 63 items.

A common bug is 1 << i where i can exceed 31. The 1 is an int, so 1 << 40 is 1 << 8 = 256. Write 1L << i.

1long mask = 0;
2mask |= 1L << 40;                         // correct
3long wrong = 1 << 40;                     // 256: int shift, distance taken mod 32
4Long.bitCount(mask);                      // 1
5Long.numberOfTrailingZeros(mask);         // 40

java.util.BitSet stores a set of non-negative integers as a growing array of longs, using one bit per element. It supports set, clear, get, flip, cardinality, nextSetBit and nextClearBit, plus whole-set and, or, xor and andNot.

It is ideal for a sieve of Eratosthenes with millions of entries (8 times smaller than a boolean[]) and for set algebra on dense integer sets. For fewer than 64 elements a plain long is faster.

1BitSet sieve = new BitSet(100);
2sieve.set(2, 100);                                   // assume 2..99 are prime
3for (int p = 2; p * p < 100; p = sieve.nextSetBit(p + 1)) {
4    for (int m = p * p; m < 100; m += p) sieve.clear(m);
5}
6System.out.println(sieve.cardinality());             // 25 primes below 100
7for (int i = sieve.nextSetBit(0); i >= 0; i = sieve.nextSetBit(i + 1)) { /* i is prime */ }

A rotation moves bits like a shift, but the bits that fall off one end come back at the other, so no information is lost. Integer.rotateLeft(x, k) and Integer.rotateRight(x, k) do this for 32 bits, and Long.rotateLeft for 64.

Rotations are used in hash functions and ciphers. Written by hand: (x << k) | (x >>> (32 - k)).

1int x = 0b1001_0000_0000_0000_0000_0000_0000_0001;
2Integer.rotateLeft(x, 1);                    // 0b0010_0000_..._0011
3Integer.rotateRight(x, 1);                   // 0b1100_1000_..._0000
4int manual = (x << 3) | (x >>> (32 - 3));    // same as rotateLeft(x, 3)