ZERO / HERO
A row of light switches

Bit Manipulation

The analogy

A number is secretly a row of on/off switches. Once you can flip, test and count switches directly, a surprising number of problems collapse into one or two operations — and sets of up to 64 things fit into a single integer.

Visualizer

Switches in a byte

step 1 / 9
0
7
0
6
1
5
0
4
1
3
1
2
0
1
0
0

x = 44 is secretly a row of switches: 00101100. Bit positions run right to left from 0.x = 44 = 0b00101100

x & (x - 1)        # clear lowest set bit
x & -x             # isolate lowest set bit (Fenwick step)
x | (1 << i)       # set bit i
x & ~(1 << i)      # clear bit i
x ^ (1 << i)       # flip bit i
(x >> i) & 1       # test bit i
x.bit_count()      # popcount, Python 3.10+

def single_number(a):          # everything twice but one
    out = 0
    for v in a:
        out ^= v               # x ^ x == 0
    return out

# enumerate all subsets of n items
for mask in range(1 << n):
    subset = [a[i] for i in range(n) if mask >> i & 1]

# iterate submasks of m
s = m
while s:
    ...
    s = (s - 1) & m
Check yourself

Every element appears twice except one. Best approach?