Bit Manipulation Applications: Adders, Bit Reversal, and Numerical Processing

Implementing an Adder with Bitwise Logic

The essence of addition can be decomposed into two parts: The Sum (XOR) and The Carry (AND then Left Shift).

1. Bitwise Sum (without carry): a ^ b. This handles bits that don't overlap.
2. Bitwise Carry: (a & b) << 1. This finds positions where both bits are 1 and shifts the carry to the next power of two.

Repeat the process until there is no carry remaining.

public int add(int a, int b) {
    while (b != 0) {
        int carry = (a & b) << 1; // Calculate bits to carry
        a ^= b;                  // Sum without carry
        b = carry;               // Make carry the new summand
    }
    return a;
}

Subtraction: a - b = a + (-b) = a + (~b + 1).

Reverse Bits (LeetCode 190)

Reverse the bits of a given 32-bit unsigned integer.

Method 1: Iterative Shift (Intuitive)

public int reverseBits(int n) {
    int res = 0;
    for (int i = 0; i < 32; i++) {
        // Shift result left to make room, then insert n's current LSB
        res = (res << 1) | (n & 1);
        n >>>= 1; // logical shift right (crucial in Java for negative n)
    }
    return res;
}

Method 2: Divide and Conquer Swapping (O(1) Masks)

This method swaps chunks of bits recursively (16-bit halves, then 8-bit quarters, etc.) using fixed masks.

public int reverseBitsFast(int n) {
    // Swap 16-bit blocks
    n = (n >>> 16) | (n << 16);
    // Swap 8-bit blocks within each 16-bit block
    n = ((n & 0xff00ff00) >>> 8) | ((n & 0x00ff00ff) << 8);
    // Swap 4-bit blocks
    n = ((n & 0xf0f0f0f0) >>> 4) | ((n & 0x0f0f0f0f) << 4);
    // Swap 2-bit blocks
    n = ((n & 0xcccccccc) >>> 2) | ((n & 0x33333333) << 2);
    // Swap adjacent 1-bit blocks
    n = ((n & 0xaaaaaaaa) >>> 1) | ((n & 0x55555555) << 1);
    return n;
}

Hamming Distance (LeetCode 461 / 477)

The Hamming Distance is the count of positions at which the corresponding bits of two integers are different.

Single Pair Distance

public int hammingDistance(int x, int y) {
    return Integer.bitCount(x ^ y); // XOR flips different bits to 1
}

Total Hamming Distance (LeetCode 477)

Find the sum of Hamming distances between all pairs in an array.

Logic: Analyzing $O(N^2)$ pairs is too slow. Instead, analyze each of the 32 bits independently.

• For bit position $i$, count how many numbers have a 1 at that position ($K$).
• The remaining $N - K$ numbers have a 0 at $i$.
• Each pair of (1, 0) contributes exactly 1 to the Hamming distance at this bit.
• Total distance for bit $i = K \times (N - K)$.

public int totalHammingDistance(int[] nums) {
    int total = 0, n = nums.length;
    for (int i = 0; i < 32; i++) {
        int onesCount = 0;
        for (int num : nums) {
            onesCount += (num >> i) & 1;
        }
        total += onesCount * (n - onesCount);
    }
    return total;
}

Number Range Bitwise AND (LeetCode 201)

Find the bitwise AND of all numbers in the range $[left, right]$.

Observation: The AND result only preserves the common prefix of $left$ and $right$. As soon as a bit differs between any two numbers in a range, that bit (and all bits to its right) will eventually encounter a 0 and be zeroed out in the final AND result.

public int rangeBitwiseAnd(int left, int right) {
    int shifts = 0;
    // Shift both until they are equal (finding the common prefix)
    while (left != right) {
        left >>= 1;
        right >>= 1;
        shifts++;
    }
    return left << shifts;
}

Maximum XOR Value (LeetCode 421)

Find the maximum XOR of two numbers in an array.

Greedy Logic: Iterate from the MSB (31) down to LSB (0). Try to set the current bit of the result to 1.

• For a target max | (1 << i), we check if there exist prefixes $a, b$ such that $a \oplus b = target$.
• By XOR properties: $a \oplus b = target \iff a \oplus target = b$.
• Use a HashSet to verify if $a \oplus target$ exists in our prefix set.

public int findMaximumXOR(int[] nums) {
    int maxResult = 0, mask = 0;
    for (int i = 31; i >= 0; i--) {
        mask |= (1 << i);
        Set<Integer> prefixes = new HashSet<>();
        for (int n : nums) prefixes.add(n & mask);
        
        int greedyTry = maxResult | (1 << i);
        for (int p : prefixes) {
            if (prefixes.contains(greedyTry ^ p)) {
                maxResult = greedyTry;
                break;
            }
        }
    }
    return maxResult;
}

Technical Summary Table