Advanced bit arithmetic

The parity of a number is whether it has an odd number of 1 bits. XOR is addition modulo 2, so XOR-ing all the bits together gives the parity. Instead of looping over 32 bits, fold the number onto itself: XOR the upper half into the lower half, then the upper half of that, and so on until one bit remains. Step through 182 in the animation: three folds are enough for 8 bits (five for 32).

Parity is used for error detection: a parity bit makes the total number of ones even or odd, so any single flipped bit is detected.

1static int parity(int x) {          // 32-bit version
2    x ^= x >>> 16;
3    x ^= x >>> 8;
4    x ^= x >>> 4;
5    x ^= x >>> 2;
6    x ^= x >>> 1;
7    return x & 1;
8}
9// equivalent: Integer.bitCount(x) & 1

1static int parity(int x) {            // 8-bit value
2    x ^= x >> 4;                      // fold the upper half onto the lower
3    x ^= x >> 2;
4    x ^= x >> 1;
5    return x & 1;                     // 1 if the number of set bits is odd
6}

A Gray code lists all n-bit numbers in an order where consecutive values differ in exactly one bit. The binary reflected Gray code of i is i ^ (i >> 1). Run the animation with 3 bits: every new code differs from the previous in a single highlighted bit, and the last code differs from the first in one bit too.

Gray codes are used in rotary encoders (no glitch when a position changes), Karnaugh maps, and puzzle solving. To convert back, XOR together the code shifted right by 1, 2, 3, … until it is zero.

1static int toGray(int i) { return i ^ (i >> 1); }
2
3static int fromGray(int g) {
4    int n = g;
5    while ((g >>= 1) != 0) n ^= g;     // n = g ^ (g >> 1) ^ (g >> 2) ^ ...
6    return n;
7}

1static List<Integer> grayCode(int n) {
2    List<Integer> result = new ArrayList<>();
3    for (int i = 0; i < (1 << n); i++) {
4        result.add(i ^ (i >> 1));        // binary XOR itself shifted right
5    }
6    return result;
7}

To reverse the bits of a 32-bit int, swap adjacent bits, then adjacent pairs, then nibbles, then bytes, then halves. Each step uses a mask and a shift, and the whole thing takes 5 steps instead of 32. Integer.reverse does exactly this.

Bit reversal is the permutation at the start of the fast Fourier transform and appears in problems that ask to reverse the binary form of a number.

1static int reverseBits(int x) {
2    x = ((x & 0x55555555) << 1) | ((x >>> 1) & 0x55555555);   // swap adjacent bits
3    x = ((x & 0x33333333) << 2) | ((x >>> 2) & 0x33333333);   // swap adjacent pairs
4    x = ((x & 0x0F0F0F0F) << 4) | ((x >>> 4) & 0x0F0F0F0F);   // swap nibbles
5    x = ((x & 0x00FF00FF) << 8) | ((x >>> 8) & 0x00FF00FF);   // swap bytes
6    return (x << 16) | (x >>> 16);                            // swap halves
7}
8// same as Integer.reverse(x)

Addition can be built from bit operations. The XOR of two numbers is their sum without carries, and (a & b) << 1 is the carries. Add them again, and repeat until no carry remains. This works for negative numbers too, because of two's complement.

To detect int overflow of a + b without using long, check whether both operands have the same sign and the result has a different one: ((a ^ r) & (b ^ r)) < 0 where r = a + b. Java also provides Math.addExact, which throws an ArithmeticException.

1static int add(int a, int b) {
2    while (b != 0) {
3        int carry = (a & b) << 1;      // positions where both bits are 1 carry to the next one
4        a ^= b;                        // sum without carries
5        b = carry;
6    }
7    return a;
8}
9
10static boolean addOverflows(int a, int b) {
11    int r = a + b;
12    return ((a ^ r) & (b ^ r)) < 0;    // operands share a sign that the result lost
13}

To compute a^b, look at the binary form of b. Each set bit contributes one of the powers a, a², a⁴, a⁸, …. Square the base every step, multiply it into the result when the current bit of b is 1, and shift b right. The loop runs once per bit of b, so it needs O(log b) multiplications instead of b - 1.

In the animation, 3^13 with 13 = 1101₂ multiplies in 3, 3⁴ and 3⁸: 3 × 81 × 6561 = 1,594,323. With a modulus applied at every multiplication this is how modular powers are computed in cryptography and combinatorics.

1static long power(long a, int b) {
2    long result = 1;
3    while (b > 0) {
4        if ((b & 1) == 1) result *= a;   // this bit of b is set
5        a *= a;                          // a, a^2, a^4, a^8, ...
6        b >>= 1;
7    }
8    return result;
9}
10
11static long powMod(long a, long b, long m) {
12    long result = 1;
13    a %= m;
14    for (; b > 0; b >>= 1, a = a * a % m) {
15        if ((b & 1) == 1) result = result * a % m;
16    }
17    return result;                       // m < 2^31 keeps a * a inside a long
18}

1static long power(long a, int b) {
2    long result = 1;
3    while (b > 0) {
4        if ((b & 1) == 1) result *= a;     // this bit of b is set
5        a *= a;                            // a, a^2, a^4, a^8, ...
6        b >>= 1;                           // move to the next bit
7    }
8    return result;
9}

A bitwise trie stores numbers as paths of bits from the most significant to the least. Each node has two children, for 0 and 1. It answers questions about XOR: to find the stored number that gives the largest XOR with x, walk down and at each bit prefer the child with the opposite bit.

The maximum XOR of any two numbers in an array of n values takes O(n · 32) with this trie, much better than the O(n²) of trying all pairs. Tries are covered fully in Chapter 28.

1static int maxXorPair(int[] nums) {
2    int[][] child = new int[nums.length * 31 + 2][2];       // child[node][bit], 0 means none
3    int nodes = 1;
4    int best = 0;
5    for (int x : nums) {
6        int cur = 0, xorHere = 0, probe = 0;
7        for (int bit = 30; bit >= 0; bit--) {
8            int b = (x >> bit) & 1;
9            // insert x
10            if (child[cur][b] == 0) child[cur][b] = nodes++;
11            cur = child[cur][b];
12        }
13        probe = 0;
14        for (int bit = 30; bit >= 0; bit--) {
15            int b = (x >> bit) & 1;
16            if (child[probe][1 - b] != 0) { xorHere |= 1 << bit; probe = child[probe][1 - b]; }
17            else probe = child[probe][b];
18        }
19        best = Math.max(best, xorHere);
20    }
21    return best;
22}