#Bit manipulation

Recognition in one line: the problem mentions bits or binary directly, asks for constant space where counting would need a map, or has n ≤ 20 and asks about subsets.

A small pattern with a high ratio of "trivial once you know the trick" to "impossible if you do not."

#1 · Recognition cues

n ≤ 20 is the tell for bitmask problems. 2²⁰ is about a million states — comfortably enumerable. The constraint is telling you the intended solution iterates over subsets.

#2 · The eight operations

Memorise these. They cover the large majority of what comes up.

1.  x & 1                 is x odd?
2.  x >> 1                divide by 2   (x >>> 1 in Java for unsigned)
3.  x << 1                multiply by 2
4.  x & (1 << i)          is bit i set?
5.  x | (1 << i)          SET bit i
6.  x & ~(1 << i)         CLEAR bit i
7.  x ^ (1 << i)          TOGGLE bit i
8.  x & (x - 1)           CLEAR THE LOWEST SET BIT      <- the important one

And the two derived from #8:

x & (x - 1) == 0          x is a power of two (or zero -- guard x > 0)
x & (-x)                  ISOLATE the lowest set bit

Why x & (x-1) clears the lowest set bit — worth being able to explain rather than memorise:

x     = 1011 0100
x - 1 = 1011 0011      subtracting 1 flips the lowest 1 to 0
                       and turns every 0 below it into 1
x&(x-1)=1011 0000      the AND kills that lowest 1 and everything below

So looping `while (x) { x &= x - 1; count++; }` counts set bits in
O(number of set bits), not O(32). That is Brian Kernighan's algorithm.

#3 · XOR — four properties that solve most problems

1.  x ^ x = 0             a value cancels itself
2.  x ^ 0 = x             identity
3.  commutative + associative -> ORDER DOES NOT MATTER
4.  x ^ y ^ y = x         XOR is its own inverse

Property 1 plus property 3 is the whole trick. If every value appears twice except one, XOR everything: the pairs cancel regardless of order, and the survivor is the answer.

def single_number(nums):
    result = 0
    for x in nums:
        result ^= x        # pairs cancel; order is irrelevant
    return result

O(n) time, O(1) space — where a hash map would be O(n) space. That space saving is the reason the problem is asked.

The three canonical XOR problems:

LC 260's partition step is the one worth understanding, because it generalises: a ^ b has a 1 wherever a and b differ, so any set bit splits the array into a group containing a and a group containing b — reducing the problem to two instances of LC 136.

#4 · Bitmasks as subsets

An integer's bits are a subset of a set of size n. Bit i set means element i is included.

n = 4, mask = 1011 (binary) = 11 (decimal)
             ^^^^
             3210      -> elements {0, 1, 3} are in the subset

Iterate ALL subsets of an n-element set:

def all_subsets(nums):
    n = len(nums)
    out = []
    for mask in range(1 << n):                 # 2^n masks
        subset = [nums[i] for i in range(n) if mask & (1 << i)]
        out.append(subset)
    return out

for (int mask = 0; mask < (1 << n); mask++) {
    List<Integer> subset = new ArrayList<>();
    for (int i = 0; i < n; i++) {
        if ((mask & (1 << i)) != 0) subset.add(nums[i]);
    }
    out.add(subset);
}

This is an alternative to backtracking for subsets, and worth having: it is iterative, has no recursion depth, and the mask itself is a convenient key for memoisation — which is exactly what makes bitmask DP work.

Useful mask operations:

The submask enumeration idiom is genuinely non-obvious and worth knowing: (sub - 1) & mask walks exactly the subsets of mask in decreasing order, and the whole loop over all masks and their submasks is O(3ⁿ), not O(4ⁿ).

#5 · Language pitfalls

These cause real bugs and are worth mentioning aloud in an interview.

#Java

#Python

def get_sum(a, b):
    """Add two integers without + or -. LC 371."""
    MASK = 0xFFFFFFFF
    MAX_INT = 0x7FFFFFFF

    while b != 0:
        carry = ((a & b) << 1) & MASK    # AND finds where a carry is generated
        a = (a ^ b) & MASK               # XOR is addition without carry
        b = carry
    # Python ints are unbounded, so reinterpret as signed 32-bit.
    return a if a <= MAX_INT else ~(a ^ MASK)

a ^ b is addition without carry; (a & b) << 1 is the carry. Repeat until there is no carry. That is a full adder, and it is the answer to "add without +".

#6 · The ladder

#Foundational

#Medium

#Hard

If you only do five: 191, 136, 268, 338, 78.

#7 · Worked example — LC 338, Counting Bits

Problem: for every i from 0 to n, return the number of 1 bits.

The naive answer is O(n log n) — Kernighan's per number. The intended solution is O(n), and it comes from a bit-level recurrence.

i in binary, shifted right by one, is i/2.
Shifting drops exactly the lowest bit.

  so  popcount(i) = popcount(i >> 1) + (lowest bit of i)
                  = dp[i >> 1] + (i & 1)

  i=5  101  ->  dp[2] + 1  =  1 + 1  =  2   ✓
  i=6  110  ->  dp[3] + 0  =  2 + 0  =  2   ✓
  i=7  111  ->  dp[3] + 1  =  2 + 1  =  3   ✓

Every value depends on a strictly smaller index, so one forward pass works.

def count_bits(n):
    dp = [0] * (n + 1)
    for i in range(1, n + 1):
        dp[i] = dp[i >> 1] + (i & 1)     # i>>1 is already computed
    return dp

public 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;
}

An alternative recurrence worth knowing: dp[i] = dp[i & (i-1)] + 1 — clearing the lowest set bit gives a smaller number with exactly one fewer bit. Both are O(n); mentioning both shows fluency.

#8 · Worked example — LC 318, Maximum Product of Word Lengths

Problem: find the maximum len(a) × len(b) over pairs of words sharing no common letter.

The insight: checking letter overlap with sets is O(26) per pair. Encode each word as a 26-bit mask and overlap becomes a single &.

"abc"  -> bits 0,1,2 set   -> 0000...0111
"def"  -> bits 3,4,5 set   -> 0000...111000

mask_a & mask_b == 0  <=>  no shared letter.  ONE instruction.

def max_product(words):
    masks = []
    for w in words:
        m = 0
        for ch in w:
            m |= 1 << (ord(ch) - ord("a"))   # set the letter's bit
        masks.append(m)

    best = 0
    for i in range(len(words)):
        for j in range(i + 1, len(words)):
            if masks[i] & masks[j] == 0:     # disjoint letter sets
                best = max(best, len(words[i]) * len(words[j]))
    return best

O(n² ) with a constant-time inner check instead of O(n²·26). The transferable idea: a small fixed universe (26 letters, 20 cities, 32 tasks) compresses into one integer, and set operations become single instructions.

#9 · Failure modes

#10 · Interview questions

#Stop condition

You know this pattern when you can:

1. write the eight operations from memory,
2. explain why x & (x-1) clears the lowest set bit,
3. give XOR's four properties and solve LC 136 and 268 with them,
4. explain the LC 260 partition trick,
5. enumerate subsets by mask and know the n ≤ 20 tell, and
6. name the Java >>> and Python masking pitfalls.