Bit manipulation
Coding interviews

Bit manipulation

XOR cancels, popcount, missing number, and subset masks — interview bit toolkit with Python and Java.

Pooja Singh 6 min read ·

When bits beat loops

Bit tricks are short interviews and strong Amazon/Google signals when you narrate them. Always state word size (32/64) and signedness for Java >>> vs >>.

Analogy: a row of light switches

Each bit is a switch. AND asks “are both on?”, OR “is either on?”, XOR “do they differ?” Clearing the lowest set bit (x & (x−1)) is turning off the rightmost glowing switch. Isolating it (x & −x) is pointing at that switch alone.

Toolkit you should recite

# Core ops (Python ints are arbitrary width — mask if you need 32-bit)
x & (x - 1)   # clear lowest set bit
x & -x        # isolate lowest set bit
x & ((1 << k) - 1)  # lowest k bits
bin(x).count("1")   # popcount
x ^ y         # toggle bits where they differ
// Java: use >>> for logical right shift on signed ints
x & (x - 1);           // clear lowest set bit
x & -x;                // isolate lowest set bit
Integer.bitCount(x);   // popcount
x ^ y;                 // xor

Edges & gotchas

What to say in the first 60 seconds

Bit rounds are short. Win them by naming the invariant in one sentence, writing a 5-line fold, and checking the empty / single-element cases out loud.

Why XOR works (say this)

XOR is associative and commutative; x ^ x = 0; x ^ 0 = x. Folding a list where every value appears twice leaves 0 ^ singleton = singleton. Missing Number is the same idea on the closed range [0..n]: XOR all indices with all values so the absent one remains.

Pattern bank (5 questions)

Q: Single Number — every element appears twice except one; find it in linear time and constant space.

def single_number(nums):
    x = 0
    for v in nums:
        x ^= v
    return x
int singleNumber(int[] nums) {
    int x = 0;
    for (int v : nums) x ^= v;
    return x;
}

Q: Number of 1 Bits (Hamming Weight) — return the number of set bits.

def hamming_weight(n: int) -> int:
    c = 0
    while n:
        n &= n - 1
        c += 1
    return c
int hammingWeight(int n) {
    int c = 0;
    while (n != 0) { n &= (n - 1); c++; }
    return c;
}

Q: Counting Bits — for every i in [0, n], return popcount(i).

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)
    return dp
int[] countBits(int n) {
    int[] dp = new int[n + 1];
    for (int i = 1; i <= n; i++)
        dp[i] = dp[i >> 1] + (i & 1);
    return dp;
}

Q: Missing Number — array of n distinct numbers in [0, n]; find the missing one.

def missing_number(nums):
    x = len(nums)
    for i, v in enumerate(nums):
        x ^= i ^ v
    return x
int missingNumber(int[] nums) {
    int x = nums.length;
    for (int i = 0; i < nums.length; i++) x ^= i ^ nums[i];
    return x;
}

Q: Subsets — return all subsets of a distinct-integer array (bit mask enumeration).

def subsets(nums):
    n = len(nums)
    out = []
    for mask in range(1 << n):
        cur = []
        for j in range(n):
            if mask & (1 << j):
                cur.append(nums[j])
        out.append(cur)
    return out
List<List<Integer>> subsets(int[] nums) {
    int n = nums.length;
    List<List<Integer>> out = new ArrayList<>();
    for (int mask = 0; mask < (1 << n); mask++) {
        List<Integer> cur = new ArrayList<>();
        for (int j = 0; j < n; j++)
            if ((mask & (1 << j)) != 0) cur.add(nums[j]);
        out.add(cur);
    }
    return out;
}

Pattern drill: 40 minutes

codingbitsxorbit-manipulation

← Lattice