Home/Questions/Q 3526
Next
In Process

RTSALL Latest Articles

aarav0
Asked: 2026-09-11T09:52:04-05:00 In: ,

How does Brian Kernighan’s bit algorithm work, and why does n & (n – 1) clear the lowest set bit?

In low-level systems programming and coding interviews, people always use the expression n & (n - 1) to count set bits (Hamming Weight) or check if a number is a power of 2.

I know it works, but what is the exact binary arithmetic proof behind why subtracting 1 from an integer flips all bits up to and including the lowest set bit?

Leave an answer

You must login to add an answer.

Need An Account,

2 Answers

  1. Abhay Tiwari
    Begginer

    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.

    • 0
  2. Anonymous
    Begginer

    Here is the modern C++20 bit-manipulation implementation. In modern C++ (C++20), you also have std::popcount from the <bit> header which compiles to the hardware POPCNT instruction.

    Modern C++20 Solution (Fully Runnable)

    #include <iostream>
#include <cstdint>
#include <bit>

// Brian Kernighan's Algorithm: runs in O(k) loops where k = set bits
int countSetBitsKernighan(uint64_t n) {
    int count = 0;
    while (n > 0) {
        n &= (n - 1); // Clears the lowest set bit
        ++count;
    }
    return count;
}

int main() {
    uint64_t val = 0b101100101101; // 7 set bits
    std::cout << "Kernighan Set Bits: " << countSetBitsKernighan(val) << "n";
    // Modern C++20 hardware intrinsic alternative:
    std::cout << "std::popcount (HW): " << std::popcount(val) << "n";
    return 0;
}

    Efficiency: Runs only as many iterations as there are 1 bits in the integer.

    • 0