Coding Interview Patterns

Bit Manipulation Tricks

A small toolkit of bitwise idioms — clearing the lowest set bit, XOR cancellation, bitmasking subsets — answers a surprising number of interview problems in O(1) extra space and a handful of instructions.

n & (n - 1) clears the lowest set bit — powers-of-two check (n > 0 && (n & (n-1)) == 0), and the basis of Brian Kernighan's bit-count algorithm
XOR cancels a value with itself (x ^ x == 0) and is identity with zero (x ^ 0 == x) — the trick behind "find the single number among duplicates"
A bitmask represents a subset of a small set (n ≤ ~20): bit i set means element i is included — the basis of bitmask dynamic programming
Left shift << and right shift >> are multiply/divide by 2, but >> on a negative int sign-extends — use >>> (unsigned shift) when the sign bit shouldn't propagate
The Integer/Long classes already provide bitCount, highestOneBit, numberOfTrailingZeros — reach for those before hand-rolling the loop

Three core bit tricks

// Count set bits (Brian Kernighan's algorithm)
static int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= (n - 1);   // clears the lowest set bit each iteration
        count++;
    }
    return count;
}

// Find the single number where every other value appears twice
static int singleNumber(int[] nums) {
    int result = 0;
    for (int n : nums) result ^= n;   // pairs cancel to 0, the lone value survives
    return result;
}

// Iterate all subsets of a bitmask (subset DP building block)
static void forEachSubset(int mask, java.util.function.IntConsumer visit) {
    for (int sub = mask; sub > 0; sub = (sub - 1) & mask) visit.accept(sub);
}

Common bit tricks
Expression	Computes
`n & (n - 1)`	n with its lowest set bit cleared
`n & (-n)`	isolates the lowest set bit
`n & 1`	checks if n is odd
`x ^ x == 0`, `x ^ 0 == x`	the basis of the "find the unique element" pattern
`1 << i`	a mask with only bit i set — check inclusion via `(mask >> i) & 1`