Bit Manipulation

The operators

XOR: the cancellation trick

XOR cancels equal values, so XOR-ing a list isolates the element appearing an odd number of times in O(1) space — “Single Number”:

def single_number(nums):
    out = 0
    for x in nums: out ^= x      # pairs cancel; the unique one survives
    return out

Extensions: Single Number III (two uniques — XOR all, then split by a differing bit); missing number (XOR indices with values); find the duplicate (XOR variants). XOR also swaps without a temp and detects “differ by exactly one bit.”

The essential low-bit idioms

• x & 1 — is the last bit set (odd)?
• x & (x - 1) — clears the lowest set bit; loop it to count set bits (Brian Kernighan), or test x & (x-1) == 0 for a power of two.
• x & -x — isolates the lowest set bit (used by Fenwick trees).
• x | (1 << i) set bit i; x & ~(1 << i) clear it; x ^ (1 << i) toggle it; (x >> i) & 1 read it.

def hamming_weight(n):
    count = 0
    while n:
        n &= n - 1               # drop lowest set bit
        count += 1
    return count

“Counting Bits” for 0..n uses DP: bits[i] = bits[i >> 1] + (i & 1).

Bitmasks as sets

A small set (≤ ~20 elements) fits in one integer — each bit = membership. This is the basis of subset enumeration and bitmask DP:

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

Enumerating submasks of a mask (sub = (sub - 1) & mask) iterates only its subsets — useful in set-cover DP.

Bitmask DP

When the state is “which subset have I used/visited,” encode it as a bitmask dp[mask]:

• Travelling Salesman — dp[mask][i] = min cost visiting mask ending at i; O(2ⁿ·n²).
• Assignment / set cover / “shortest path visiting all nodes” — dp[mask] over visited sets.

The mask compresses an exponential set-state into an integer index — recognize it when n is small (≤ ~20) and the state is a subset.

Arithmetic without operators

• Sum of two integers without + — XOR is the sum-without-carry, (a & b) << 1 is the carry; loop until no carry.
• Multiply/divide by powers of two — shifts.

Where it shows up

Single Number I/II/III, Counting Bits, Reverse Bits, Number of 1 Bits, Power of Two/Four, Sum of Two Integers, Subsets (mask form), and bitmask-DP problems (TSP, “Partition to K Equal Subsets,” “Shortest Path Visiting All Nodes”).

Pitfalls

• Fixed-width vs Python ints — Python ints are arbitrary precision; mask with & 0xFFFFFFFF and handle the sign manually for 32-bit problems.
• Operator precedence — bitwise ops bind loosely; parenthesize ((x >> i) & 1).
• Negative numbers / two’s complement — ~x == -x - 1; be careful with right shifts on negatives.

Choosing in an interview

• “Find the unique / odd-one-out / missing” → XOR.
• Count/manipulate individual bits → the low-bit idioms.
• State is “which subset” with small n → bitmask (DP).
• No-arithmetic-operator constraint → XOR + carry.