Bit manipulation — the tricks that show up repeatedly

A handful of bitwise operations, combined in a small number of recurring patterns, solve a surprising range of problems in O(1) space and often O(n) time where the obvious approach reaches for a hash set or extra array — recognizing the pattern is most of the work.

Intermediate

4 min read

The operations themselves, and what each one actually does

a = 0b1100  # 12
b = 0b1010  # 10
 
a & b   # 0b1000 (8)  — AND: 1 only where BOTH bits are 1
a | b    # 0b1110 (14) — OR: 1 where EITHER bit is 1
a ^ b     # 0b0110 (6)  — XOR: 1 where the bits DIFFER
~a         # NOT: flips every bit (in Python, ~a == -(a+1) due to two's-complement)
a << 1      # 0b11000 (24) — LEFT SHIFT: multiply by 2 per shift
a >> 1       # 0b0110 (6)   — RIGHT SHIFT: divide by 2 per shift (integer division)

Every bitwise operation works independently, bit by bit, with no carrying or borrowing between positions — which is exactly what makes them fast (genuinely O(1) per operation, not proportional to the number's size in any practical sense) and why they compose into patterns that solve problems an obvious hash-set-based approach would need real extra memory for.

XOR's one property that makes it genuinely useful: it cancels itself out

x ^ x == 0   # any value XORed with ITSELF is always 0
x ^ 0 == x    # any value XORed with 0 is unchanged
# and XOR is commutative/associative — order doesn't matter

This single property — x ^ x == 0 — is the mechanism behind a real, classic problem: given an array where every number appears twice except one, find the single unpaired number, in O(n) time and O(1) space, with no hash set at all.

def find_single(nums):
    result = 0
    for n in nums:
        result ^= n  # every PAIRED number cancels itself out; only the unpaired one survives
    return result
 
find_single([4, 1, 2, 1, 2])  # 4 — the 1s and 2s cancel each other out via XOR

XORing every element together means every number that appears an even number of times cancels itself to 0 (since x ^ x == 0, and XOR is order-independent), leaving only the number that appeared an odd number of times — a hash-set approach solves the same problem correctly but needs real O(n) extra space to track which numbers have been seen; this XOR trick needs none.

Checking, setting, and clearing a specific bit

def get_bit(n, i):
    return (n >> i) & 1          # shift bit i to position 0, then mask everything else off
 
def set_bit(n, i):
    return n | (1 << i)           # OR with a mask that has ONLY bit i set
 
def clear_bit(n, i):
    return n & ~(1 << i)           # AND with a mask that has EVERY bit set except i

1 << i produces a number with only bit i set (a mask) — the standard building block for checking, setting, or clearing one specific bit without touching any others: OR-ing with a mask sets that bit (leaving every other bit unchanged, since OR-ing with 0 changes nothing), AND-ing with the mask's complement clears it (AND-ing with 1 preserves every other bit), and shifting a bit down to position 0 before masking with & 1 isolates just that one bit's value for checking.

Counting set bits, and the `n & (n - 1)` trick specifically

def count_set_bits(n):
    count = 0
    while n:
        n &= (n - 1)  # clears the LOWEST set bit, each iteration
        count += 1
    return count
 
# n = 0b1100 (12): after one iteration, 0b1000 (the lowest set bit is gone)

n - 1 flips every bit from the lowest set bit down to (and including) that bit itself — so n & (n - 1) always clears exactly the lowest set bit and leaves everything else unchanged, meaning this loop runs exactly once per set bit, not once per bit position — genuinely faster than checking all 32 (or 64) bit positions individually when a number has far fewer set bits than its total width, and a real, recognizable trick worth knowing on sight rather than re-deriving.

Powers of two: a genuinely elegant one-line check

def is_power_of_two(n):
    return n > 0 and (n & (n - 1)) == 0
 
# 8 = 0b1000, 7 = 0b0111 — 8 & 7 == 0 — no shared set bits at all
# 6 = 0b0110, 5 = 0b0101 — 6 & 5 == 0b0100 — NOT zero, 6 is not a power of two

A power of two has exactly one set bit (8 = 0b1000), which means n - 1 flips that single bit off and turns on every bit below it (7 = 0b0111) — since there's only one set bit to begin with, n & (n-1) clears it entirely, leaving 0. Any number that isn't a power of two has more than one set bit, so n - 1 can't clear all of them, and the AND result is non-zero — a real, common interview question with a clean, memorable one-line answer once the underlying mechanism (the same n & (n-1) trick from bit-counting above) is understood.