Bit Manipulation

At a glance

The instinct

Every int is secretly an array of 32 booleans that the CPU can flip, combine and slide in a single instruction. Bit manipulation problems reward you for noticing that the question is really about parity, presence, or binary structure rather than about magnitude. If a hash set would work but the interviewer asks for O(1) extra space, or the problem says "without using + or -", the answer is almost always hiding in the bits.

Recognise it

Not this pattern if...

• Duplicates can appear an arbitrary number of times and you need counts - use a hash map or counting array.
• Values are huge (beyond 64 bits) or the question is really about decimal digits - use math or strings.
• "Subsets" have n around 40+ - 2^n masks are too many; think backtracking with pruning or meet-in-the-middle.

Memory hack

Analogy: a row of light switches in a hallway. AND asks "are both lights on?", OR asks "is either on?", XOR asks "are they different?", and a shift slides every switch one door over. Flipping a switch twice leaves the hallway as it was - that is why paired numbers cancel.

Say it out loud in the interview:

1. "What property survives in binary - parity, a single set bit, or a shared prefix?"
2. "Which identity do I need: x ^ x = 0, n & (n-1), n & -n, or (n >> i) & 1?"
3. "Am I safe on negatives and overflow - should I use >>> and a long?"

How it works

The toolbox is small - learn these six moves and most problems become a two-line loop:

Worked trace for Sum of Two Integers, a = 5 (0101), b = 3 (0011):

For Single Number III (two loners), XOR everything to get x ^ y, isolate any set bit with d & -d - x and y differ there - then split the array into two groups by that bit and XOR each group separately.

Java template

class BitTricks {
    // XOR fold: whatever appears an odd number of times survives.
    static int xorAll(int[] nums) {
        int acc = 0;
        for (int x : nums) acc ^= x;
        return acc;
    }

    // Kernighan: loop runs once per set bit, works for negatives too.
    static int popCount(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }

    // Walk all 32 positions; use >>> so the sign bit does not smear.
    static int reverseBits(int n) {
        int result = 0;
        for (int i = 0; i < 32; i++) {
            result = (result << 1) | (n & 1);
            n >>>= 1;
        }
        return result;
    }

    // Arithmetic without + : XOR is the sum, AND<<1 is the carry.
    static int add(int a, int b) {
        while (b != 0) {
            int carry = (a & b) << 1;
            a ^= b;
            b = carry;
        }
        return a;
    }

    // Subset enumeration: each mask is one subset of n items.
    static void forEachSubset(int n) {
        for (int mask = 0; mask < (1 << n); mask++) {
            for (int i = 0; i < n; i++) {
                if (((mask >> i) & 1) == 1) {
                    // item i is in this subset - problem-specific work here
                }
            }
        }
    }
}

Complexity

Variations

• Cancellation by XOR - pairs vanish: Single Number, Missing Number.
• Partition by a differing bit - find the bit where two answers differ, then split: Single Number III.
• Per-bit counting - count each of the 32 bits modulo k when elements repeat k times (Single Number II).
• Bit DP - reuse the answer for i >> 1 or i & (i - 1): Counting Bits.
• Common prefix - shift both ends right until equal, then shift back: Bitwise AND of Numbers Range.
• Carry simulation - XOR plus shifted AND: Sum of Two Integers.
• Bitmask as a set - visited states in BFS or DP over subsets (e.g. travelling-salesman-style DP).

Common mistakes

• Operator precedence: n & 1 == 0 parses as n & (1 == 0) and does not compile in Java - always parenthesise (n & 1) == 0.
• Writing 1 << 31 or 1 << 32 and expecting a positive or 64-bit result; use 1L << k for longs.
• Treating n & (n - 1) == 0 as "power of two" without also checking n > 0 (0 and Integer.MIN_VALUE slip through).
• Forgetting that ~x equals -x - 1, so ~ is not "negative x".
• Reaching for bit tricks when a plain hash set is clearer and space is not constrained - mention both and let the interviewer choose.

All practice problems

8 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.