Bit Manipulation: Foundational Techniques and Classic Problems

Why Use Bit Manipulation?

Bit manipulation operates directly on the binary representation of integers. It is extremely fast (usually a single CPU instruction) and requires no extra memory. In algorithms, it is primarily used for:

• State Compression: Representing a set of 32 booleans using bits of a single 32-bit integer.
• Mathematical Efficiency: Multiplying/dividing by powers of 2, and checking parity.
• Symmetry Breaking: Using XOR to cancel out paired elements.
• Subset Enumeration: Using bitmasks to iterate through all possible subsets of a set.

Foundational Operator Cheat Sheet

[!IMPORTANT] In Java, >>> is crucial for handling negative numbers in bitwise logic, as it prevents sign extension (padding with 1s).

Essential Bitwise Tricks

// ========== DETECTION ==========
(n & 1) == 1           // Check if n is ODD
(n >> k) & 1           // Get the value of the k-th bit (0 or 1)
(n & (1 << k)) != 0   // Check if the k-th bit is set to 1

// ========== BIT MODIFICATION ==========
n | (1 << k)           // Set the k-th bit to 1
n & ~(1 << k)          // Clear the k-th bit (set to 0)
n ^ (1 << k)           // Flip the k-th bit (0->1 or 1->0)

// ========== BRIAN KERNIGHAN'S ALGORITHM ==========
n & (n - 1)            // Clear the lowest SET bit (1100 -> 1000)
n & (-n)               // Extract ONLY the lowest set bit (1100 -> 0100)
                       // Since -n = ~n + 1 (2's complement), n & (-n) = lowbit

// ========== XOR IDENTITIES ==========
a ^ a == 0             // Self-XOR results in zero
a ^ 0 == a             // XOR with zero is identity
Integer.bitCount(n)    // Count total set bits (built-in Java method)

Why does n & (n-1) work? If the lowest set bit is at position $k$, then $n$ looks like ...1000. Subtracting 1 makes $n-1$ look like ...0111. Performing AND clears the bit at $k$ and everything below it.

XOR: The Law of Three

a ^ a = 0     (Self-cancellation)
a ^ 0 = a     (Identity)
a ^ b = b ^ a (Commutativity)
(a ^ b) ^ c = a ^ (b ^ c) (Associativity)

Single Number I (LeetCode 136)

Every element appears twice except for one. Find that single number.

public int singleNumber(int[] nums) {
    int res = 0;
    for (int n : nums) res ^= n;
    // Pairs cancel out: a ^ a = 0
    // Result is the remaining unique element
    return res;
}

Single Number III (LeetCode 260)

Two elements appear once, all others twice. Find the two unique elements.

public int[] singleNumber(int[] nums) {
    int xor = 0;
    for (int n : nums) xor ^= n; // xor = a ^ b
    
    // Find the lowest bit where a and b differ
    int diff = xor & (-xor);
    
    // Partition numbers into two groups based on this bit
    int a = 0;
    for (int n : nums) {
        if ((n & diff) != 0) a ^= n;
    }
    // group1 XOR yields 'a', the rest is 'b'
    return new int[]{a, xor ^ a};
}

Counting Set Bits (Hamming Weight)

Method: Brian Kernighan (Targeted Counting)

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1); // Remove the lowest set bit one by one
        count++;
    }
    return count;
}

Complexity: $O(K)$ where $K$ is the number of 1s (always $\le 32$).

Power of Two Detection

boolean isPowerOfTwo(int n) {
    // A power of two has exactly one bit set to 1.
    return n > 0 && (n & (n - 1)) == 0;
}

boolean isPowerOfFour(int n) {
    // 1. Must be a power of two
    // 2. The single bit must be at an even position (0, 2, 4...)
    // 0xAAAAAAAA covers all odd positions (1, 3, 5...)
    return n > 0 && (n & (n - 1)) == 0 && (n & 0xAAAAAAAA) == 0;
}

Technical Summary: Scene-to-Technique Mapping