Bit Manipulation

XOR tricks, counting bits, bitmasks as sets and arithmetic without operators.

Bit manipulation questions look intimidating, but they rely on a short list of identities. Learn the identities below and most questions reduce to applying one or two of them. XOR does most of the work.

The operators

Identities worth memorizing

Check bit i:          (x >> i) & 1
Set bit i:            x | (1 << i)
Clear bit i:          x & ~(1 << i)
Toggle bit i:         x ^ (1 << i)
Lowest set bit:       x & -x
Clear lowest set bit: x & (x - 1)
Power of two:         x > 0 and x & (x - 1) == 0

XOR tricks

XOR is its own inverse: a ^ a = 0 and a ^ 0 = a, in any order. So XOR-ing everything together cancels out every pair.

from functools import reduce
from operator import xor

def single_number(nums):
    return reduce(xor, nums, 0)

Missing number in 0..n: XOR all the indexes and all the values. Only the missing number is left.
Two numbers that appear once: XOR everything to get a ^ b. Any set bit in that result separates a from b, so split the numbers by that bit and XOR each group.
Prefix XOR: xor(l..r) = px[r+1] ^ px[l], the same idea as prefix sums.

Counting bits

def count_ones(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Counting bits for 0..n with DP: bits[i] = bits[i >> 1] + (i & 1).

Bitmasks as sets

An integer with n bits can represent any subset of n items. That gives you:

All subsets: loop mask from 0 to 2ⁿ − 1. Item i is in the subset if mask >> i & 1.
Fast set operations: union is |, intersection is &, and "share no letters" is a & b == 0. For *Maximum Product of Word Lengths*, build a 26-bit mask for each word.
Bitmask DP: state = (subset visited, current node). Use it for traveling salesman variants and assignment problems when n ≤ about 20.

def subsets(items):
    n = len(items)
    return [[items[i] for i in range(n) if mask >> i & 1]
            for mask in range(1 << n)]

Arithmetic without operators

Sum of two integers without +: XOR gives the sum without carries, and (a & b) << 1 gives the carries. Repeat until there are no carries left. In Python, integers have unlimited size, so mask the result to 32 bits and convert back to a signed value at the end.

def get_sum(a, b):
    mask = 0xFFFFFFFF
    while b & mask:
        a, b = (a ^ b) & mask, ((a & b) << 1) & mask
    a &= mask
    return a if a <= 0x7FFFFFFF else ~(a ^ mask)

[!WARNING] Python's integers have no fixed width ~x, right shifts of negative numbers, and "reverse the 32 bits" problems behave differently from Java or C++. Mention this and mask with 0xFFFFFFFF where it matters. Interviewers appreciate it when you call out language-specific behavior.

Where bit tricks show up outside puzzles

Feature flags and permission sets stored as bitmasks
Bloom filters and bitmap indexes
Gray codes, hashing and checksums
Checking alignment, for example that size is a multiple of 8: size & 7 == 0

[!TIP] Practice Single Number · Number of 1 Bits · Counting Bits · Missing Number · Power of Two · Single Number III · Sum of Two Integers · Maximum Product of Word Lengths · Reverse Bits