Advanced Topics7 min read

Bit Manipulation

Flip switches at the speed of electricity — and do it in \(O(1)\)
all bitwise ops:\(O(1)\) — single CPU instructionword size:64 bits on modern hardwarehardware popcount:\(O(1)\) via POPCNT instruction

Every integer in your computer is stored as a row of light switches — each switch is a bit, either on (1) or off (0). Bit manipulation means reaching in and flipping individual switches directly, without going through the slow machinery of arithmetic.

Why bother? Because these operations run in a single CPU clock cycle — literally the fastest thing a computer can do. Many tricks that look like they'd take \(O(n)\) work collapse to \(O(1)\) with the right combination of switches.

The six basic operations

AND (&): bit is 1 only if both inputs have 1. Use it to mask (isolate) specific bits.
OR (|): bit is 1 if either input has 1. Use it to set specific bits.
XOR (^): bit is 1 if inputs differ. Use it to toggle bits or detect differences.
NOT (~): flips all bits. In two's complement: ~x = −x − 1.
Left shift (<< k): multiply by 2^k (shift bits left, pad with zeros).
Right shift (>> k): divide by 2^k (shift right; arithmetic shift preserves sign).

Essential tricks

Check if n is a power of 2: n & (n−1) == 0 (and n > 0). A power of 2 has exactly one bit set. Subtracting 1 flips all bits below it and clears the top bit. AND gives 0.

Isolate the lowest set bit: n & (−n). In two's complement, −n = ~n + 1. The carry propagates through trailing zeros, stopping at the lowest 1-bit — which survives the AND.

Clear the lowest set bit: n & (n−1). This clears exactly one bit per call — the basis of Brian Kernighan's popcount algorithm.

XOR superpowers

Swap without a temp variable: a ^= b; b ^= a; a ^= b. Works because XOR is its own inverse: (a^b)^b = a.

Find the lone non-duplicate: XOR all elements. Pairs cancel (x^x = 0), zero is identity (0^x = x), so you're left with the unique element. XOR is commutative and associative — order doesn't matter.

Missing number in 0..n: XOR all elements with 0^1^2^…^n. Paired values cancel, leaving the missing one.

Bitmasks for subsets

Represent a subset of {0, 1, …, n−1} as an integer where bit i is 1 iff element i is in the subset. You get 2^n possible subsets for free, each as a single integer. This representation is the foundation of bitmask DP.

Check if element i is in mask: (mask >> i) & 1.
Add element i: mask | (1 << i).
Remove element i: mask & ~(1 << i).
Iterate all subsets of mask: for s = mask; s > 0; s = (s−1) & mask.

Counting set bits (popcount)

Hardware POPCNT: on any modern CPU, __builtin_popcount(n) (C/C++), Integer.bitCount(n) (Java), or bin(n).count('1') (Python) compile to a single POPCNT instruction. Always prefer this.

Brian Kernighan's method: while n: n &= n−1; count++. Clears one bit per iteration, so it runs in \(O(popcount(n)\)) — great when very few bits are set.

Note: XOR is the Swiss Army knife of bit manipulation: toggle, swap, find differences, cancel duplicates. Whenever you see 'pair', 'difference', or 'toggle' in a problem, ask: 'can XOR solve this in \(O(1)\)?'

Bit tricks — power of 2, popcount, XOR find-unique

# Power of 2 check
def is_power_of_2(n):
    return n > 0 and (n & (n - 1)) == 0


print(is_power_of_2(16))   # True
print(is_power_of_2(18))   # False


# Isolate lowest set bit
def lowest_bit(n):
    return n & (-n)


print(bin(lowest_bit(0b10110)))  # 0b10 (bit 1)


# Count set bits (popcount)
def popcount(n):
    count = 0
    while n:
        n &= n - 1  # clear lowest set bit
        count += 1
    return count


print(popcount(0b101101))  # 4
print(bin(255).count('1')) # 8  (faster way)


# XOR: find the single non-duplicate
def find_unique(arr):
    result = 0
    for x in arr:
        result ^= x
    return result


print(find_unique([4, 1, 2, 1, 2]))  # 4
print(find_unique([3, 3, 7, 5, 5]))  # 7


# Subset enumeration
mask = 0b1011  # subset {0, 1, 3}
subsets = []
s = mask
while s > 0:
    subsets.append(bin(s))
    s = (s - 1) & mask
print(subsets)
Output
True
False
0b10
4
8
4
7
['0b1011', '0b1010', '0b1001', '0b1000', '0b11', '0b10', '0b1']

Complexity

⚡ AND, OR, XOR, NOT, shiftsLiterally the fastest operations a CPU can perform — one clock cycle each
Single CPU instruction\(O(1)\)
🔢 Hardware popcount (POPCNT)Available on all modern x86/ARM CPUs — use __builtin_popcount, Integer.bitCount, or BitOperations.PopCount
Single CPU instruction\(O(1)\)
🔁 Brian Kernighan's popcountGreat when very few bits are set; otherwise prefer hardware POPCNT
One iteration per set bit\(O(popcount(n)\))
📦 Subset enumeration via bitmaskEach subset is an integer — all subset operations (add, remove, check) are \(O(1)\)
Visit all 2^n subsets\(O(2^n)\)

Quick check

What does the expression n & (n-1) compute?

Continue reading

Bitmask DP
Track every possible subset of choices in a single integer
→
0/1 Knapsack
Pack a suitcase for maximum value — each item is all-or-nothing
→