vault

Bit Manipulation Tricks

32 min read

Bit Manipulation Tricks

Bit manipulation is the discipline of treating an integer as a packed array of independent boolean flags — its bits — and using the CPU’s single-cycle bitwise operators (AND, OR, XOR, NOT, <<, >>) to read, write, count, and combine those flags faster than any data structure can. The toolbox is small (set, clear, toggle, test, isolate-low-bit, clear-low-bit, count-population, parity) but underwrites a remarkable amount of practical algorithmics: bitmask dynamic programming, lowbit indexing in a Fenwick Tree, permission flags in operating-system APIs, hash-bit selection for Bloom Filter lookups, and the “set as 64-bit integer” representation that turns subset enumeration on small universes into a tight inner loop the optimizer loves.

1. Intuition — A Row of Light Switches

An n-bit unsigned integer is, mechanically, a row of n light switches numbered from 0 (the rightmost, “least significant”) to n−1 (the leftmost, “most significant”). The integer’s value is the binary-encoded sum of which switches are on:

bit index:    7 6 5 4 3 2 1 0
switches:     0 1 0 0 1 1 0 1
value:                            64 + 8 + 4 + 1 = 77

Bit-manipulation tricks are nothing more than recipes for flipping, reading, or counting these switches efficiently using the bitwise operators the CPU already has wired up. Every operation in this note takes one or two arithmetic logic unit (ALU) cycles on commodity hardware — orders of magnitude faster than any software loop or hash lookup.

Two analogies make the deeper structure click:

  1. A subset of {0, 1, …, n-1} is naturally encoded as an n-bit integer where bit k is 1 if and only if k is in the subset. Set union becomes OR, intersection becomes AND, symmetric difference becomes XOR, and complement-within-the-universe becomes XOR ((1<<n)-1). Subset enumeration becomes a for k in range(1<<n) loop. This is the substrate of Bitmask DP.
  2. The bit pattern of n and n-1 differ in exactly the trailing-1s region of n. If n = ...XYZ100 (some prefix XYZ then 100), then n-1 = ...XYZ011 — the borrow propagates through the trailing zeros, flips the lowest 1, and stops. So n & (n-1) = ...XYZ000 — n with its lowest set bit cleared. This single observation underlies population count (Brian Kernighan’s algorithm), power-of-two detection, and the inner loop of the Fenwick Tree.

Once you internalize these two facts — that integers are sets, and that n and n-1 agree on every bit above the lowest set bit of n — most of the tricks in this note are corollaries.

2. Tiny Worked Example — Tracing Each Idiom on a Concrete Number

Let n = 0b0010_1101 (decimal 45). The bits are indexed 0 through 7 from the right:

bit index:    7 6 5 4 3 2 1 0
n:            0 0 1 0 1 1 0 1     = 45

We trace each idiom explicitly.

Set bit k — n |= 1 << k

To set bit 1 (currently 0):

1 << 1     = 0 0 0 0 0 0 1 0   = 2
n          = 0 0 1 0 1 1 0 1   = 45
n | (1<<1) = 0 0 1 0 1 1 1 1   = 47

The OR forces bit 1 to 1 and leaves every other bit unchanged because OR-with-zero is the identity (x | 0 = x).

Clear bit k — n &= ~(1 << k)

To clear bit 3 (currently 1):

1 << 3      = 0 0 0 0 1 0 0 0   = 8
~(1 << 3)   = 1 1 1 1 0 1 1 1   = (interpreted as 8-bit) 247
n           = 0 0 1 0 1 1 0 1   = 45
n & ~(1<<3) = 0 0 1 0 0 1 0 1   = 37

The mask ~(1<<k) is “all 1s except at position k.” AND-with-1 preserves a bit; AND-with-0 clears it.

Toggle bit k — n ^= 1 << k

To toggle bit 5 (currently 1):

1 << 5      = 0 0 1 0 0 0 0 0   = 32
n           = 0 0 1 0 1 1 0 1   = 45
n ^ (1<<5)  = 0 0 0 0 1 1 0 1   = 13

XOR-with-1 flips a bit (x ^ 1 = NOT x); XOR-with-0 leaves it (x ^ 0 = x). Toggling twice returns the original value because XOR is self-inverse — the central identity of XOR Properties.

Check bit k — (n >> k) & 1

To read bit 2 (expect 1):

n >> 2       = 0 0 0 0 1 0 1 1   = 11
(n >> 2) & 1 =                 1

Shifting right by k brings bit k into position 0; ANDing with 1 isolates it. An equivalent idiom is (n & (1 << k)) != 0, which avoids the shift but produces a non-1/0 truth value (anything nonzero is “true”). The two forms are interchangeable for boolean tests; the >> k & 1 form is preferred when you need an integer 0 or 1 (e.g., to add into an accumulator).

Isolate the lowest set bit — n & -n

For n = 45 = 0b00101101:

-n in two's complement on 8 bits = ~n + 1
~n  = 1 1 0 1 0 0 1 0
+1  = 1 1 0 1 0 0 1 1   = -45 (as signed 8-bit, or 211 as unsigned)
n & -n = 0 0 0 0 0 0 0 1   = 1

The result is the value of the single lowest set bit (here, the bit at position 0, with value 2⁰ = 1). For n = 12 = 0b00001100, n & -n = 0b00000100 = 4. This idiom is the heartbeat of the Fenwick Tree — the i & -i term gives the size of the responsibility interval ending at index i.

Clear the lowest set bit — n & (n-1)

For n = 45 = 0b00101101:

n - 1     = 0 0 1 0 1 1 0 0   = 44
n & (n-1) = 0 0 1 0 1 1 0 0   = 44

The trailing 1 turned into 0; everything to its left was preserved. For n = 12 = 0b00001100, n-1 = 0b00001011, so n & (n-1) = 0b00001000 = 8 — the lowest set bit (at position 2) is gone, and only the bit at position 3 remains. This is the engine of Brian Kernighan’s population-count algorithm.

Detect a power of two — (n & (n-1)) == 0

A power of two has exactly one set bit. Clearing that bit yields zero. For n = 8 = 0b1000, n-1 = 0b0111, n & (n-1) = 0 — power of two confirmed. For n = 12 = 0b1100, n & (n-1) = 0b1000 ≠ 0 — not a power of two. Edge case: n = 0 also satisfies the test (0 & -1 = 0), so always guard with n > 0 if zero should not be classified as a power of two.

3. The Identities — Reference Card

The following table is the working set every interviewer expects you to have memorized. Each row gives the operation (what you want to do), the idiom (the bit expression), and the use case (what real algorithm it powers).

OperationIdiomUse case
Set bit k of n to 1n | (1 << k)Mark element k as in a subset
Clear bit k of n to 0n & ~(1 << k)Remove element k from subset
Toggle bit k of nn ^ (1 << k)Flip element k’s membership
Read bit k of n(n >> k) & 1Iterate digits / decode a flag
Bit-check returning truthyn & (1 << k)Conditional in if statement
Lowest set bit (value)n & -nFenwick Tree traversal step
Lowest set bit (position)(n & -n).bit_length() - 1; or de Bruijn multiply-shift-lookup (§12.7)Decode index in binary indexed tree; branchless CTZ
Clear lowest set bitn & (n - 1)Population count loop body
Set lowest unset bitn | (n + 1)Find next “fillable” slot
Extract lowest k bitsn & ((1 << k) - 1)Bucket index from a hash
Clear lowest k bitsn & ~((1 << k) - 1)Round down to multiple of 2^k
Round up to next 2^k boundary(n + (1<<k) - 1) & ~((1<<k) - 1)Memory alignment
Detect power of two (n > 0)(n & (n-1)) == 0Capacity-doubling growth check
Detect oddn & 1Last-bit parity
Negate (two’s complement)~n + 1 (== -n)Sign flip
Absolute value, branchless (32-bit)(n ^ (n>>31)) - (n>>31)Avoiding branch mispredict on hot path
Min of two ints, branchlessb ^ ((a^b) & -(a<b))Tight inner loop optimizations
Swap without tempa ^= b; b ^= a; a ^= bInterview parlor trick (don’t use in real code)
Count set bits (population)Brian Kernighan loop, bin(n).count('1'), n.bit_count() (Py 3.10+)Bitmask DP subset cardinality
Iterate set bits one by onewhile n: lo = n & -n; ...; n &= n - 1Sparse subset traversal
Iterate all subsets of a masks = mask; while s: ...; s = (s - 1) & maskBitmask DP partition enumeration
Reverse bits (hand-coded, 32-bit)Hacker’s Delight §7-1 lookup-table or shift+mask cascadeFFT bit-reversal permutation

The idioms break down into three families: single-bit edits (set/clear/toggle/check), lowest-bit operations (n & -n, n & (n-1)), and subset/mask manipulation (intersection/union/iteration). Sections 5 through 9 below unpack each family in depth.

4. The Bitwise Operators — Truth Tables and Identities

Before composing tricks, fix the four primitives. For one-bit operands a, b ∈ {0, 1}:

aba & b (AND)a | b (OR)a ^ b (XOR)~a (NOT, on 8-bit)
000001 (i.e., 0xFF in unsigned 8-bit)
010111
100110 (i.e., 0xFE in 8-bit)
111100

Multi-bit operands are processed bit-by-bit independently. The useful identities — every one of which the bit tricks below leans on:

  • x & 0 = 0, x & ~0 = x (AND with zero clears, AND with all-ones preserves)
  • x | 0 = x, x | ~0 = ~0 (OR with zero preserves, OR with all-ones forces 1s)
  • x ^ 0 = x, x ^ x = 0, x ^ ~0 = ~x (XOR is self-inverse — see XOR Properties)
  • AND, OR, XOR are commutative and associative
  • ~~x = x, -(-x) = x
  • De Morgan’s laws: ~(a & b) = ~a | ~b, ~(a | b) = ~a & ~b
  • a + b = (a ^ b) + 2 · (a & b) — XOR is “addition without carry,” AND captures the carry. This is the seed of carry-save adder design and of bitwise tricks for arithmetic.

The shifts:

  • x << k shifts x left by k bits, equivalent to multiplying by 2^k (modulo wraparound or undefined behavior at the high end).
  • x >> k shifts right by k. For unsigned x, this is integer division by 2^k. For signed x, behavior depends on language: C is implementation-defined (but every mainstream compiler does arithmetic shift, replicating the sign bit); Python’s >> is arithmetic on its arbitrary-precision integers; Java’s >> is arithmetic, Java’s >>> is logical (zero-fill). This signed-vs-unsigned distinction is a recurrent interview gotcha — see Pitfalls §10.

5. Two’s Complement — The Reason -n Behaves Like an Inverter Plus One

Most modern CPUs represent signed integers in two’s complement: an n-bit signed integer encodes values in [-2^(n-1), 2^(n-1) - 1], with the top bit acting as a sign indicator and the remaining bits encoding the magnitude in a way that makes addition uniform across signed and unsigned.

The key identity: in n-bit two’s complement, -x = ~x + 1. To negate, flip all bits and add 1. Why this choice?

  • Single representation of zero. A naive sign-magnitude encoding would have +0 (00…0) and −0 (10…0); two’s complement eliminates the duplicate. Wikipedia’s Two’s complement article discusses the alternatives historically considered.
  • Addition is the same circuit for signed and unsigned. The hardware adder doesn’t need to know whether you’re treating its inputs as signed; it just adds modulo 2^n. This is why (uint8_t)(-1) == 255 and (int8_t)(-1) == -1 are the same bit pattern 11111111 — only the interpretation differs.
  • Subtraction is a + (-b) = a + ~b + 1. No special subtractor circuit needed.

The concrete consequence for our tricks: n & -n works because in two’s complement, -n = ~n + 1. Adding 1 to ~n propagates a carry through the trailing 1-run of ~n (which corresponds to the trailing 0-run of n), stopping at the position of the lowest 0-bit of ~n, i.e., the lowest 1-bit of n. So the bits of -n agree with n at that lowest 1-bit position and the bits below (both end in 0…010…0 and …111…1 after the carry) — the AND there is 1. Above the lowest set bit of n, ~n has its bits flipped relative to n, so the AND is 0.

The formal proof. Write n with its lowest set bit factored out: n = m · 2^(k+1) + 2^k, where 2^k is the lowest set bit and m is whatever the bits above position k happen to be (bits 0..k-1 of n are all zero by construction, since 2^k is the lowest set bit). In w-bit two’s complement, -n ≡ 2^w − n (mod 2^w). Substitute:

-n = 2^w − (m·2^(k+1) + 2^k)
   = 2^w − m·2^(k+1) − 2^k

Now AND with n. Below position k, both n and −n are zero (the 2^k term and the 2^w − … borrow leave bits 0..k-1 clear in both), so the AND is 0 there. At position k, n has a 1 by definition, and −n also has a 1 — the borrow from 2^w − n propagates up through the trailing zeros of n and settles exactly at the lowest set bit, leaving it 1. Above position k, −n’s bits are the bitwise complement of n’s (the two’s-complement negation flips every bit strictly above the lowest set bit), so each AND there is b · ¬b = 0. The result therefore has exactly one set bit, at position k: n & -n = 2^k, the value of the lowest set bit. This matches the exhaustive numeric check (45 & -45 = 1, 12 & -12 = 4) and the worked symbol-by-symbol derivation in Hacker’s Delight §2-1, “Manipulating Rightmost Bits”. The one place this can break in practice is a fixed-width type at its most negative value, where the negation overflows — see Pitfalls §10.4.

6. Brian Kernighan’s Population Count

The question “how many 1-bits does n have?” is called population count, popcount, Hamming weight, or bit count. The naive method scans all n bits in O(n). Brian Kernighan’s algorithm — folklore, attributed to Kernighan in many references but earlier appearances exist — runs in time proportional to the number of set bits, which is often much smaller than the bit width.

popcount_kernighan(n):
    count = 0
    while n != 0:
        n = n & (n - 1)      # clears lowest set bit
        count += 1
    return count

Each loop iteration removes exactly one set bit, so the iteration count equals the popcount. For n = 45 = 0b00101101, the loop runs 4 times (the four set bits at positions 0, 2, 3, 5):

iter 1: n=45 (00101101), n & (n-1)=44 (00101100), count=1   [cleared bit 0]
iter 2: n=44 (00101100), n & (n-1)=40 (00101000), count=2   [cleared bit 2]
iter 3: n=40 (00101000), n & (n-1)=32 (00100000), count=3   [cleared bit 3]
iter 4: n=32 (00100000), n & (n-1)= 0 (00000000), count=4   [cleared bit 5]

For dense inputs the algorithm degrades to O(b) where b is the bit width; for sparse inputs (typical in Bitmask DP subset operations on small populated sets), it is much faster than scanning all bits. In production, prefer the hardware POPCNT instruction: GCC’s __builtin_popcount, MSVC’s __popcnt, Java’s Integer.bitCount, Python 3.10+‘s int.bit_count(). These compile to a single CPU instruction on x86-64 (since the SSE4.2 extension, 2008) and ARMv8.

7. Iterating All Subsets of a Mask — The “Submask Trick”

A common Bitmask DP subroutine: given a bitmask mask representing a set S, enumerate every subset of S (including S itself and the empty set). The naive method enumerates all 2^n integers and tests each against the mask — O(2^n) per outer iteration.

The submask iteration trick runs in time proportional to the number of subsets — 2^|S|, where |S| is the popcount of mask:

s = mask
while s > 0:
    # ... use s as a subset of mask ...
    s = (s - 1) & mask
# handle s = 0 (empty subset) explicitly if needed

The expression (s - 1) & mask “decrements within the mask”: it subtracts 1 from s, which may temporarily flip bits outside mask, then re-AND with mask to project back. The net effect is to enumerate the subsets of mask in decreasing order. This is one of the few tricks where understanding why it works requires a short but non-trivial proof — see Knuth TAOCP Vol. 4A §7.1.3 for the full discussion.

The total work across all 2^n masks (in an outer DP loop) is Σ_{|S|=0..n} C(n, |S|) · 2^|S| = (1+2)^n = 3^n by the binomial theorem — the famous “3^n bound” of subset-of-subset DP. This is why Held-Karp TSP DP is O(2^n · n²) per iteration but related “merge over subsets” DPs come out to O(3^n).

8. Branchless Operations — Why and When

Modern CPUs predict branches; mispredictions cost ~10-20 cycles each. Bitwise tricks let you compute conditionals without branching, which can be a 2-5× speedup in tight loops where the branch is poorly predictable.

Branchless absolute value (32-bit signed n):

mask = n >> 31         # arithmetic shift: 0xFFFFFFFF if n < 0, else 0
abs_n = (n ^ mask) - mask

When n ≥ 0: mask = 0, so (n ^ 0) - 0 = n. When n < 0: mask = -1 (all bits set), so n ^ -1 = ~n, and ~n - (-1) = ~n + 1 = -n. Either branch gives |n| without a conditional.

Branchless min (a, b) for signed integers:

min_ab = b ^ ((a ^ b) & -(a < b))

a < b is 1 when true, 0 when false. -(1) = -1 (all bits), -(0) = 0. So when a < b: b ^ (a^b) = a; when a ≥ b: b ^ 0 = b. Useful in cycle-counted code; in modern compilers, however, min(a, b) often compiles to cmov (conditional move), which is itself branchless. Profile before deploying these — handwritten branchless code can be slower than what the compiler produces from clean code.

Uncertain

Verify: that handwritten branchless bit tricks beat the branchful form for your specific case. Reason: the answer is genuinely workload- and CPU-dependent and not pinnable to one source. A predictable branch (e.g. a loop bound, or a condition that is almost always true) is essentially free after the predictor warms up, so the branchful version wins; an unpredictable branch (data-dependent, ~50/50) costs a ~10–20-cycle misprediction each time, where branchless dominates. Modern compilers also emit cmov (conditional move) from clean branchful code, which is itself branchless — so the hand-rolled trick may merely duplicate what -O2 already does, or worse, defeat an optimization the compiler would have applied. To resolve: benchmark the actual hot path with perf stat (watch branch-misses) on the target microarchitecture; do not assume.

9. Python Implementation — The Toolbox in One File

Python 3.10+ provides int.bit_count() and int.bit_length() as optimized built-ins, removing most reasons to hand-roll bit tricks. The functions below illustrate the idioms; for production Python, prefer the built-ins.

def set_bit(n: int, k: int) -> int:
    """Return n with bit k set to 1."""
    return n | (1 << k)
 
def clear_bit(n: int, k: int) -> int:
    """Return n with bit k cleared to 0."""
    return n & ~(1 << k)
 
def toggle_bit(n: int, k: int) -> int:
    """Return n with bit k flipped."""
    return n ^ (1 << k)
 
def get_bit(n: int, k: int) -> int:
    """Return the value (0 or 1) of bit k of n."""
    return (n >> k) & 1
 
def lowest_set_bit_value(n: int) -> int:
    """Return 2^k where k is the lowest set bit position. 0 if n == 0."""
    return n & -n
 
def lowest_set_bit_position(n: int) -> int:
    """Return k where the lowest set bit is at position k. -1 if n == 0."""
    if n == 0:
        return -1
    return (n & -n).bit_length() - 1   # bit_length(2^k) = k+1
 
def clear_lowest_set_bit(n: int) -> int:
    """Return n with its lowest set bit cleared."""
    return n & (n - 1)
 
def is_power_of_two(n: int) -> bool:
    """True iff n is a positive power of two."""
    return n > 0 and (n & (n - 1)) == 0
 
def popcount_kernighan(n: int) -> int:
    """Brian Kernighan: number of set bits, in O(popcount) iterations."""
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count
 
# In Python 3.10+:
#   n.bit_count()        -> popcount
#   n.bit_length()       -> position of highest set bit + 1
#   bin(n).count('1')    -> popcount, slower string-based fallback
 
def iter_set_bits(n: int):
    """Yield bit positions where n has a 1, low to high."""
    while n:
        lo = n & -n
        yield lo.bit_length() - 1
        n &= n - 1
 
def iter_subsets(mask: int):
    """Yield all submasks of mask (including 0 and mask), in decreasing order."""
    s = mask
    while s > 0:
        yield s
        s = (s - 1) & mask
    yield 0
 
def xor_swap(a: int, b: int) -> tuple[int, int]:
    """Swap two integers without a temp variable. Pedagogical only."""
    a ^= b
    b ^= a       # b now holds original a
    a ^= b       # a now holds original b
    return a, b

A subtle point: Python integers are arbitrary precision. ~n in Python is -n - 1, not a fixed-width complement. So ~5 = -6 (because Python conceptually treats ints as having “infinite” leading sign bits). To get a 32-bit two’s complement complement, mask with 0xFFFFFFFF:

def not32(n: int) -> int:
    return (~n) & 0xFFFFFFFF

This is the most common cross-language confusion when porting C bit tricks to Python — a C int32_t and a Python int agree on &, |, ^, <<, but disagree on ~ and >> of negative values. See Pitfalls §10.6.

10. Pitfalls

10.1 Operator Precedence Surprises

In C, Python, Java, and most C-family languages, == binds tighter than &, |, ^. So n & 1 == 0 parses as n & (1 == 0) = n & 0 = 0, not (n & 1) == 0. Always parenthesize bit operations in conditionals: (n & 1) == 0. This bug is endemic in interview code on the whiteboard.

10.2 Shift Amount ≥ Bit Width

In C/C++, shifting an int by a count ≥ 32 (or by a negative count) is undefined behavior per the standard. Compilers do whatever; on x86, shl eax, 33 actually shifts by 33 mod 32 = 1 because the hardware masks the count. Code that depends on this is non-portable and probably wrong.

Python and Java behave deterministically: Python supports arbitrary shifts (no UB), Java’s << on an int masks the shift count to its low 5 bits (x << 33 is x << 1). Know your language.

10.3 Signed Right Shift vs. Unsigned Right Shift

In C/C++, >> on a signed type is implementation-defined; on every mainstream compiler it is arithmetic shift (the sign bit replicates: (int)-1 >> 1 == -1, not 0x7FFFFFFF). On unsigned types, >> is logical shift (zero fill).

Java has separate operators: >> is arithmetic, >>> is logical.

Python has only >>, which on its arbitrary-precision integers is arithmetic (preserves sign). To simulate logical shift in Python, mask first: (n & 0xFFFFFFFF) >> k.

Interview trap: “Reverse bits of a 32-bit integer” — solutions that rely on n >>= 1 to walk the bits leak negatively-signed garbage in Python or Java unless you mask explicitly.

10.4 n & -n on the Most Negative Integer

In two’s complement, the most negative value (e.g., INT_MIN = -2^31 = 0x80000000) is its own negation: -INT_MIN = INT_MIN (because +2^31 doesn’t fit in 32 signed bits and overflows back). So INT_MIN & -INT_MIN = INT_MIN, which is correct (the lowest set bit is bit 31, the only set bit), but the C standard considers integer overflow on signed types undefined behavior. Compilers in practice produce the right answer; the standard formally does not guarantee it.

In Python this is a non-issue because there is no integer overflow.

10.5 bin(n).count('1') vs int.bit_count() vs Hardware POPCNT

Three Python idioms with very different performance:

  • bin(n).count('1') — converts to a string, scans characters. Slow. O(b) with a large constant.
  • n.bit_count() (Python ≥ 3.10) — built-in, internally uses CPython’s bit-twiddling. Fast.
  • __builtin_popcount(n) (C/C++/GCC) — compiles to one POPCNT instruction on modern x86 (SSE4.2+) and ARMv8. One cycle.

Java’s Integer.bitCount similarly compiles to POPCNT on hot paths via the JIT.

Don’t write bin(n).count('1') in interviews after Python 3.10 unless you want to demonstrate the algorithm. Use n.bit_count().

10.6 Python ~n Is Not a Fixed-Width Bitwise NOT

~5 == -6 in Python because Python integers are arbitrary precision; ~n is -n - 1. To mimic uint32_t ~n in Python: (~n) & 0xFFFFFFFF. This is the most-frequent porting bug from Hacker’s Delight C snippets to Python.

10.7 Endianness Does Not Affect Bit Operations on Integers

A frequent confusion: “endianness” is about byte order in memory. Bit operations on integers in your language are value-based — they operate on the number, not the memory representation. n & 1 extracts the least-significant bit regardless of whether the platform is little-endian or big-endian. Endianness matters only when you reinterpret bytes through unions/casts/serialization, not for &, |, ^, <<, >> on integer-typed values.

10.8 The XOR Swap Trick Is Worse Than the Temp-Variable Swap

a ^= b; b ^= a; a ^= b is a parlor trick. In real code:

  • The compiler optimizes a temp swap into a pair of register moves anyway.
  • XOR swap fails if a and b are aliases of the same memory location: after a ^= b (with a == b), both are 0; the swap leaves both at 0, not their original values.
  • It impedes pipelining because each XOR depends on the prior result.

Mention it in interviews if asked, but never deploy it. The temp-variable version is faster and correct.

10.9 Treating XOR as a “Difference” Operator

XOR is not arithmetic difference: 5 - 3 = 2 but 5 ^ 3 = 0b101 ^ 0b011 = 0b110 = 6. Using a ^ b to mean “are they different” yields a truthy nonzero value when they differ and 0 when equal — that’s correct as a boolean test (a ^ b != 0 ⇔ a != b), but the value of the XOR is meaningless as a difference. See XOR Properties for what XOR actually means algebraically.

10.10 (n & (n-1)) == 0 Treats Zero as a Power of Two

0 & -1 == 0 so the test fires for n = 0. Always guard: n > 0 && (n & (n-1)) == 0. Many production “is-power-of-two” routines have shipped this bug.

11. Diagram — How n & -n Isolates the Lowest Bit

flowchart LR
  subgraph N["n = 45 (0b00101101)"]
    n7[0] --- n6[0] --- n5[1] --- n4[0] --- n3[1] --- n2[1] --- n1[0] --- n0[1]
  end
  subgraph M["-n in 8-bit two's complement (0b11010011 = 211 unsigned)"]
    m7[1] --- m6[1] --- m5[0] --- m4[1] --- m3[0] --- m2[0] --- m1[1] --- m0[1]
  end
  subgraph A["n & -n = 0b00000001 = 1"]
    a7[0] --- a6[0] --- a5[0] --- a4[0] --- a3[0] --- a2[0] --- a1[0] --- a0[1]
  end
  N --> A
  M --> A

What this diagram shows. Three bit-patterns aligned by position: n = 45, its two’s-complement negation -n (= ~n + 1 = 211 unsigned in 8 bits), and their bitwise AND. The AND has exactly one set bit — the lowest set bit of n, at position 0. This works because -n = ~n + 1: the +1 propagates a carry through the trailing zeros of n (which are trailing ones in ~n), stopping at the lowest set bit of n. At that bit position, both n and -n are 1 (the carry just settled there); below, both are 0; above, n’s bits and -n’s bits are complements. The AND therefore agrees only at that single position. The i & -i form is the heart of Fenwick Tree traversal: it gives the responsibility-interval length of node i.

12. Variants and Generalizations

12.1 Hacker’s Delight — The Comprehensive Reference

Henry Warren’s Hacker’s Delight (2nd ed., 2012) is the canonical encyclopedia of bit tricks: 350+ pages of branchless integer manipulation, exact bounds on what is achievable, and proofs of correctness for every idiom. Chapter 2 covers single-bit operations; Chapter 5 covers counting; Chapter 7 covers rearrangement (bit reversal, reverse-byte, gray code); Chapter 11 covers some divisions by constants via shift-and-add. If you need any bit trick not in this note, look in Warren first.

12.2 Stanford Bit Twiddling Hacks

Sean Eron Anderson’s bit hacks page is the best free online compendium. Notable: parity in 64 bits with a magic multiplication; reversing bits via a 5-step shift-and-mask cascade; computing the next-greater integer with the same popcount (used in combinatorial enumeration).

12.3 SWAR — SIMD Within a Register

The SIMD-Within-A-Register paradigm packs multiple small values into a single wide register and processes them in parallel using bitwise ops. The SWAR popcount uses this to count bits in groups of 2, 4, 8, 16, 32, 64 — a logarithmic-depth tree that runs in O(log b) operations rather than O(popcount) or O(b):

count = (n & 0x5555...) + ((n >> 1) & 0x5555...)    # 2-bit pairs
count = (count & 0x3333...) + ((count >> 2) & 0x3333...)
count = (count + (count >> 4)) & 0x0F0F...
count = (count * 0x0101...) >> (b - 8)              # horizontal sum via multiply

This is what hardware POPCNT essentially does (sometimes faster via parallel adders). The 64-bit version is given by Hacker’s Delight §5-1. SWAR techniques generalize to byte-level minima, prefix-sums-within-a-register, and so on.

12.4 Population Count via Lookup Table

For bytes, a 256-entry lookup table gives popcount in 4 lookups + 3 adds for a 32-bit input. Faster than Brian Kernighan when bits are dense; slower than POPCNT on hardware that has it. Used in FPGAs and embedded systems lacking POPCNT.

12.5 Gray Code

The k-th Gray code is k ^ (k >> 1). Successive Gray codes differ in exactly one bit, useful for rotary encoders, Bitmask DP over subsets enumerated such that consecutive subsets differ in one element (allowing incremental updates), and Karnaugh maps.

12.6 The Count Leading Zeros (CLZ) and Count Trailing Zeros (CTZ) Instructions

x86’s BSR (bit-scan-reverse) and BSF (bit-scan-forward), exposed in C as __builtin_clz and __builtin_ctz, find the position of the highest or lowest set bit in O(1) hardware instruction. ARM has CLZ; ARMv8 has both. In Python, n.bit_length() gives “highest set bit + 1” but no built-in CTZ; the closest idiom is (n & -n).bit_length() - 1, which is fast but not single-instruction.

These instructions enable O(1) Fenwick / segment tree index calculations and O(1) “find next available bit” in bitmap allocators (slab allocators, file system free-block tracking, the Linux kernel’s find_first_bit).

12.7 The de Bruijn Sequence Trick — Branchless CTZ Without a Hardware Instruction

On a platform that lacks a count-trailing-zeros instruction (or a language like Python that does not expose one), there is a classic O(1) software trick that turns “which position is the lowest set bit at?” into a single multiply, a shift, and one table lookup — no loop, no branch. It is built on a de Bruijn sequence, and it is one of the most elegant bit hacks in the canon, so it is worth understanding mechanically rather than memorizing.

A binary de Bruijn sequence B(2, k) is a cyclic bit string of length 2^k in which every one of the 2^k distinct length-k bit substrings appears exactly once as a contiguous window (wrapping around the end) (Wikipedia: de Bruijn sequence). For k = 5 (32-bit words) one such sequence, packed into a 32-bit integer, is the constant 0x077CB531. The crucial property: if you take this constant and shift it left by p bits, the top 5 bits of the result form a 5-bit value unique to p. Because every length-5 window of the de Bruijn sequence is distinct, the top-5-bits-after-shifting-by-p is a perfect (collision-free) hash of p into 0..31.

The algorithm exploits that as follows. To find the position of the lowest set bit of v:

DE_BRUIJN_32 = 0x077CB531
# table[i] = the bit position p such that (0x077CB531 << p)'s top 5 bits == i
CTZ_TABLE = [0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8,
             31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9]
 
def count_trailing_zeros_32(v: int) -> int:
    """Position of the lowest set bit of a nonzero 32-bit v, in O(1) ops."""
    isolated = v & -v                                  # 1: keep only lowest set bit -> 2^p
    index = ((isolated * DE_BRUIJN_32) & 0xFFFFFFFF) >> 27   # 2: hash p into 0..31
    return CTZ_TABLE[index]                            # 3: decode position

Walking it line by line. Step 1, v & -v, isolates the lowest set bit, producing exactly 2^p where p is the answer we want (this is the same lowest-set-bit idiom from §1, now used to reduce the problem to “find the position of a single set bit”). Step 2, multiplying 2^p by the de Bruijn constant is identical to shifting the constant left by p (x · 2^p == x << p); masking to 32 bits emulates the overflow of a uint32_t, and >> 27 keeps the top 5 bits — a value in 0..31 that is unique to p by the de Bruijn property. Step 3 uses a precomputed 32-entry table to map that unique hash back to the actual position p. There is no branch and no loop: three arithmetic operations and a memory load, regardless of where the bit sits.

I verified this exhaustively against the ground truth (v & -v).bit_length() - 1 for all single-bit inputs 1<<k, k∈0..31 and thousands of random 32-bit values — it agrees in every case. The constant 0x077CB531 and the multiply-shift-by-27 structure are confirmed against Sean Anderson’s Stanford Bit Twiddling Hacks, which presents this as the canonical de Bruijn log2 / find-first-set routine. The same construction with a shift of >> (32 - k) and the appropriate table generalizes to other widths; the 64-bit version uses a 64-bit de Bruijn constant and a 64-entry table.

The historical relevance is that this trick was the fastest portable CTZ before SSE4.2’s hardware TZCNT/BSF became ubiquitous, and it still appears in chess engines (bit-board square indexing), the find first set fallbacks of libraries on CTZ-less targets, and any setting where you have a 32- or 64-bit “set” and need its smallest member without a hardware instruction. On a CPU that has __builtin_ctz / TZCNT, prefer the instruction — it is a single cycle and skips the table load entirely.

13. Common Interview Problems

ProblemLeetCode #What’s tested
Number of 1 Bits191Brian Kernighan’s popcount
Counting Bits338DP using dp[i] = dp[i & (i-1)] + 1
Power of Two231n > 0 && (n & (n-1)) == 0
Power of Four342Power of two + bit position parity (& 0x55555555)
Reverse Bits190Shift-and-mask cascade or lookup table
Single Number136XOR all elements; see XOR Properties
Single Number II137Mod-3 bit counting OR ones/twos state machine
Single Number III260XOR all → split by a differing bit; see XOR Properties
Missing Number268XOR with [0, n] or sum trick
Sum of Two Integers371Add without +: XOR for sum-no-carry, AND<<1 for carry
Bitwise AND of Numbers Range201Common prefix via right-shifting
Maximum XOR of Two Numbers in Array421Trie of bits, greedy from MSB
Subsets78Iterate 0 .. (1<<n) - 1 and decode each integer’s bits
Hamming Distance461popcount(a ^ b)
UTF-8 Validation393Check leading bit patterns with masks
Total Hamming Distance477Per-bit-column counting
Repeated DNA Sequences187Encode 10-char DNA strings as 20-bit integers
Find Duplicate Number (Bit version)287Per-bit-column count parity
Sort Integers by Number of 1 Bits1356Sort key = (popcount, value)

The bit-manipulation theme appears in roughly 30 LeetCode problems, but the underlying tricks are almost always: popcount, power-of-two test, lowest set bit, XOR identities, or bit-by-bit DP.

14. Open Questions

  • When does a SWAR popcount beat a hardware POPCNT? On older hardware lacking POPCNT, SWAR wins by definition; on modern hardware, POPCNT is one cycle. SWAR remains relevant on GPU shaders that lack POPCNT, on embedded MCUs, and inside SIMD code that wants to popcount many words in parallel.
  • Can the optimizer produce n & -n from naive code like for (k=0; k<32; k++) if (n & (1<<k)) break; result = 1<<k;? Empirically GCC at -O3 does not see this transformation; it remains a loop. Hand-rolling n & -n is therefore still worth doing.
  • The “swap without temp via XOR” trick — is there any modern context where it is genuinely faster? Anecdotally no: register-renaming CPUs make a temp swap free, and the XOR-chain dependency hurts pipelining. If you find a counter-example, it’s a curiosity, not a guideline.

15. See Also

Graph View

Backlinks