The trick n & (n - 1) is one of the most elegant one-liners in computer engineering. Let’s look at the exact bitwise mechanics so the mathematical proof becomes obvious.

1. What happens when you subtract 1 in binary?

Think about standard base-10 math: when you subtract 1 from 1000, what happens? The lowest non-zero digit (1) becomes 0, and all trailing zeroes become 9s: 0999.

Binary works exactly the same way, but with 0s and 1s:

Any positive binary integer can be written in this general form:

n = (arbitrary prefix) 1 0 0 0 ... 0

where the 1 shown is the lowest set bit (the rightmost 1), followed by zero or more 0s.

When you compute n - 1:

1. The arbitrary prefix before the lowest 1 remains completely untouched.
2. That lowest 1 turns into a 0 (borrowing from the subtraction).
3. All the trailing 0s flip into 1s!

    n     = (prefix) 1 0 0 0
  n - 1   = (prefix) 0 1 1 1

2. The Bitwise AND Operation: n & (n – 1)

Now perform a bitwise AND between n and n - 1:

    n     = (prefix) 1 0 0 0
& n - 1   = (prefix) 0 1 1 1
----------------------------
  result  = (prefix) 0 0 0 0

Look at what happened:

• The prefix matched identically → remains preserved.
• The rightmost 1 was paired with 0 → becomes 0!
• The trailing 0s were paired with 1s → remain 0!

Conclusion: The operation n & (n - 1) turns off the lowest set bit in n and leaves every other bit completely unchanged. Pure mathematical magic!

3. Real-World Applications

A. Counting Set Bits in O(k) time (where k is number of 1s)

Instead of looping 32 or 64 times, Brian Kernighan’s algorithm loops only as many times as there are 1-bits:

def count_set_bits(n: int) -> int:
    count = 0
    while n > 0:
        n &= (n - 1)  # Strips off one set bit per loop iteration
        count += 1
    return count

If a 64-bit integer has only two set bits, this loop executes exactly twice and terminates!

B. Instant Power of Two Check in O(1)

A power of two in binary has exactly one set bit (e.g. 8 = 1000_2, 16 = 10000_2). If you strip that single bit and the result is 0, it was a power of 2:

def is_power_of_two(n: int) -> bool:
    return n > 0 and (n & (n - 1)) == 0

C. Hardware POPCNT Alternative

On modern x86_64 CPUs, you have the dedicated hardware assembly instruction POPCNT (or __builtin_popcount in GCC/Clang), which computes set bits in a single CPU cycle. But when writing portable code or kernel routines without AVX/SSE guarantees, Brian Kernighan’s algorithm remains the golden standard.