Bit Manipulation

Binary refresher

An integer is a sequence of bits. Bit i (counting from 0 at the right) has value 2^i.

13 = 1101₂ = 8 + 4 + 0 + 1

Negative numbers use two's complement: −x = ~x + 1. So −1 is all ones, and x & −x isolates the lowest set bit.

Operators

The essential tricks

(x >> i) & 1          # is bit i set?
x | (1 << i)          # set bit i
x & ~(1 << i)         # clear bit i
x ^ (1 << i)          # toggle bit i
x & (x - 1)           # clear the lowest set bit
x & -x                # isolate the lowest set bit
x & (x - 1) == 0      # power of two (for x > 0)
bin(x).count("1")     # popcount (Python 3.10+: x.bit_count())
x.bit_length()        # number of bits needed (position of highest set bit + 1)
(1 << n) - 1          # mask of n ones

(x >> i) & 1;
x | (1 << i);
x & ~(1 << i);
x ^ (1 << i);
x & (x - 1);
x & -x;
__builtin_popcount(x);      // __builtin_popcountll for 64-bit
__builtin_ctz(x);           // count trailing zeros (x != 0)
__builtin_clz(x);           // count leading zeros (x != 0)
1LL << 40;                  // use 1LL for shifts >= 31!

XOR: the star of the show

Properties:

• a ^ a = 0, a ^ 0 = a
• commutative and associative → order doesn't matter
• a ^ b = c ⇔ a ^ c = b (self-inverse)

Single number (every element appears twice except one):

def single_number(nums):
    x = 0
    for n in nums:
        x ^= n
    return x

Two single numbers (all others twice): XOR everything → a ^ b. Any set bit of that differs between a and b; split the array by that bit and XOR each half.

def single_number_iii(nums):
    xor_all = 0
    for n in nums:
        xor_all ^= n
    diff = xor_all & -xor_all         # lowest bit where a and b differ
    a = 0
    for n in nums:
        if n & diff:
            a ^= n
    return [a, xor_all ^ a]

Missing number in 0..n: XOR all indices and all values.

Every element three times except one: count each bit position modulo 3.

def single_number_ii(nums):
    res = 0
    for i in range(32):
        s = sum((n >> i) & 1 for n in nums) % 3
        if s:
            res |= 1 << i
    return res - (1 << 32) if res >= 1 << 31 else res   # restore sign

Counting bits

def count_bits(n):          # popcount for 0..n in O(n)
    bits = [0] * (n + 1)
    for i in range(1, n + 1):
        bits[i] = bits[i >> 1] + (i & 1)
    return bits

Brian Kernighan's loop runs once per set bit:

def popcount(x):
    c = 0
    while x:
        x &= x - 1
        c += 1
    return c

Subsets as bitmasks

For n ≤ 20, a subset of {0..n−1} is an integer from 0 to 2ⁿ − 1.

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

# iterate all submasks of a mask (O(3^n) over all masks total)
sub = mask
while sub:
    ...                     # use sub
    sub = (sub - 1) & mask

for (int mask = 0; mask < (1 << n); mask++)
    for (int i = 0; i < n; i++)
        if (mask >> i & 1) { /* item i is in the subset */ }

for (int sub = mask; sub; sub = (sub - 1) & mask) { /* each non-empty submask */ }

This is the foundation of bitmask DP (TSP, assignment problems) — see Advanced DP.

Bitmask as a compact set / state

• 26 lowercase letters fit in one int: mask |= 1 << (ord(c) - 97). Two words share no letters iff m1 & m2 == 0 (Maximum Product of Word Lengths).
• Parity of counts: toggle a bit per character; a substring has all-even counts iff prefix masks are equal (Longest Awesome Substring).
• Visited set in BFS over small graphs: state = (node, mask) (Shortest Path Visiting All Nodes).

Arithmetic with bits

def add(a, b):                       # without + (32-bit emulation in Python)
    MASK = 0xFFFFFFFF
    while b & MASK:
        a, b = a ^ b, (a & b) << 1
    # if the carry ran past 32 bits the true result lives in the low 32 bits of a
    return a & MASK if b > 0 else a

int getSum(int a, int b) {
    while (b != 0) {
        unsigned carry = (unsigned)(a & b) << 1;
        a = a ^ b;
        b = (int)carry;
    }
    return a;
}

• Multiply/divide by powers of two with shifts.
• Fast exponentiation walks the bits of the exponent (see Math).
• Gray code: i ^ (i >> 1) — consecutive values differ in one bit.

Maximum XOR pair: binary trie

Insert numbers bit by bit from the most significant. For each number, walk the trie greedily choosing the opposite bit when available.

def find_maximum_xor(nums):
    root = {}
    for n in nums:
        node = root
        for i in range(31, -1, -1):
            node = node.setdefault((n >> i) & 1, {})
    best = 0
    for n in nums:
        node, cur = root, 0
        for i in range(31, -1, -1):
            b = (n >> i) & 1
            if 1 - b in node:
                cur |= 1 << i
                node = node[1 - b]
            else:
                node = node[b]
        best = max(best, cur)
    return best

Common mistakes

• Operator precedence: in C++ and Python, &, ^, | bind looser than ==. Write (x & 1) == 0, not x & 1 == 0.
• 1 << k overflow in C++ for k ≥ 31.
• Python's unbounded negative integers when emulating fixed-width arithmetic.
• Right-shifting negative numbers: arithmetic shift in most languages (sign bit copied); Java has >>> for logical shift.