vault

Brian Kernighan's Algorithm

22 min read

Brian Kernighan’s Algorithm

Brian Kernighan’s algorithm counts the number of set bits (1-bits) in a non-negative integer n by repeatedly applying the identity n & (n - 1), which clears the lowest set bit of n. Each iteration of the loop while n != 0: count++; n = n & (n-1) removes exactly one 1-bit, so the loop runs popcount(n) times rather than the O(bit_width) iterations a naïve “test each bit” approach would need. For a 64-bit integer with only k ones (a “sparse” bit pattern), Kernighan’s runs in k steps versus naïve’s 64 — a substantial constant-factor win when k << 64. The trick is one of the most cited “bit hacks” in computer-science folklore: it appears as Exercise 2-9 in Kernighan & Ritchie’s The C Programming Language, 2nd edition (1988), and the underlying observation traces further back to Peter Wegner’s 1960 Communications of the ACM note “A technique for counting ones in a binary computer” (CACM 3(5), p. 322), which described the same n & (n-1) iteration. The algorithm is named after Kernighan because of K&R’s wide adoption rather than original discovery; in fact Wegner’s 1960 publication predates Kernighan’s career. On modern hardware, the dedicated popcnt machine instruction (Intel SSE4.2, AMD ABM, ARM NEON cnt) computes the population count in a single cycle for any input — making Kernighan’s algorithm no longer the fastest method in the absolute sense. But Kernighan’s remains pedagogically central as the “obvious” O(popcount) algorithm, is portable across architectures lacking popcnt, and is the canonical inner loop when iterating over the set bits themselves (not just counting them) — which is its most common modern application, e.g., in Subset Enumeration with Bitmasks and Bitmask DP traversals.

1. Intuition — Why n & (n - 1) Clears the Lowest Set Bit

The whole algorithm rests on one observation about subtracting 1 from a binary number. Take any non-zero integer n. Look at its binary representation:

n      = (some bits)  1  (some zeros)
                     ^^^
                  the lowest 1-bit, with k zeros to its right (k >= 0)

For example, n = 0b0110_1100 = 108:

n = 0 1 1 0 1 1 0 0
                 ^
                 lowest 1-bit is at position 2; positions 0, 1 are zeros.

Now subtract 1. The subtraction borrows through the trailing zeros, flipping them to 1s, and stops at the lowest 1-bit, flipping it to 0:

n - 1 = 0 1 1 0 1 0 1 1
                 ^^^
                 the lowest 1 became 0; the trailing zeros became 1s.

Compare bit-by-bit:

  • Bit positions above the lowest 1-bit: unchanged in n - 1.
  • The lowest 1-bit position itself: was 1, now 0.
  • Bit positions below the lowest 1-bit: were 0, now 1.

When you AND n with n - 1:

  • Above the lowest 1-bit: n & (n-1) matches n (both have the same bits there).
  • At the lowest 1-bit position: 1 & 0 = 0.
  • Below the lowest 1-bit position: 0 & 1 = 0.
n     = 0 1 1 0 1 1 0 0
n - 1 = 0 1 1 0 1 0 1 1
n & (n-1) = 0 1 1 0 1 0 0 0
                         ^
                         lowest 1-bit is gone; everything else preserved.

So n & (n - 1) is exactly n with its lowest set bit cleared. Iterating this operation peels off 1-bits one by one until n becomes 0.

A real-world analogy: imagine a row of light switches, some on and some off. To count how many are on without looking at every switch, you could grope along the row for the rightmost lit switch, turn it off, and tick a counter. Repeat until no lit switches remain. The number of ticks is the count. Kernighan’s algorithm does exactly this — n & (n-1) is the “find and turn off the rightmost lit switch” operation, all in one CPU cycle.

2. Tiny Worked Example — Counting Bits in n = 0b1011_0100

Let n = 0b1011_0100 = 180. The set bits are at positions 2, 4, 5, 7 — four 1-bits in total.

Iteration 1

  • n = 0b1011_0100
  • n - 1 = 0b1011_0011
  • n & (n-1) = 0b1011_0000 — the lowest set bit (position 2) was cleared.
  • count = 1, n = 0b1011_0000

Iteration 2

  • n = 0b1011_0000
  • n - 1 = 0b1010_1111
  • n & (n-1) = 0b1010_0000 — position 4 cleared.
  • count = 2, n = 0b1010_0000

Iteration 3

  • n = 0b1010_0000
  • n - 1 = 0b1001_1111
  • n & (n-1) = 0b1000_0000 — position 5 cleared.
  • count = 3, n = 0b1000_0000

Iteration 4

  • n = 0b1000_0000
  • n - 1 = 0b0111_1111
  • n & (n-1) = 0b0000_0000 — position 7 cleared.
  • count = 4, n = 0

Termination

  • n == 0, exit loop. Total count: 4, matching popcount(180) = 4. ✓

The loop ran exactly 4 times — once per set bit. A naïve “check bit k for k = 0..7” would have run 8 times. Kernighan’s win: half the work for this 8-bit example, more dramatic for sparser inputs (e.g., n = 0b1 only iterates once, naïve does 32 or 64 bit-checks).

3. Pseudocode

PopCount(n):
    # Count the number of 1-bits in non-negative integer n.
    count := 0
    while n != 0:
        n = n & (n - 1)    # clear the lowest set bit
        count = count + 1
    return count

The entire algorithm is three lines of body. Its elegance is part of why it became a canonical introductory bit-hack.

To iterate over the set bits themselves (the most common modern use):

ForEachSetBit(n, action):
    # Call action(k) for each k such that bit k of n is set.
    while n != 0:
        lowbit_value = n & (-n)         # isolate the lowest set bit (also called "lowbit")
        k = log2(lowbit_value)          # position of that bit
        action(k)
        n = n & (n - 1)                 # clear it and continue

The pairing n & (-n) (isolate lowest set bit) and n & (n - 1) (clear lowest set bit) is fundamental in Bit Manipulation Tricks: one extracts the bit’s value, the other removes it. Together they let you walk the set bits of n without touching the cleared bits.

4. Python Implementation

def popcount_kernighan(n: int) -> int:
    """Count the number of 1-bits in non-negative n using Brian Kernighan's algorithm.
 
    Loop runs popcount(n) times — proportional to the number of set bits,
    not the bit-width.
 
    Args:
        n: Non-negative integer.
    Returns:
        Number of 1-bits in the binary representation.
    """
    if n < 0:
        raise ValueError("Kernighan's algorithm assumes non-negative input")
    count = 0
    while n != 0:
        n &= n - 1
        count += 1
    return count
 
 
# Sanity checks against Python's built-in.
assert popcount_kernighan(0) == 0
assert popcount_kernighan(1) == 1
assert popcount_kernighan(180) == 4    # 0b10110100
assert popcount_kernighan(0xFFFF) == 16
assert popcount_kernighan((1 << 1000) - 1) == 1000  # huge sparse input still works
 
 
def iterate_set_bits(n: int):
    """Yield the indices of set bits in n, lowest first.
 
    Combines lowbit isolation (n & -n) with Kernighan's clear (n & (n-1)).
    Each iteration is O(1); total runtime is O(popcount(n)).
    """
    while n != 0:
        low = n & -n          # isolate lowest set bit (a power of 2)
        yield low.bit_length() - 1  # position k such that 2^k == low
        n &= n - 1            # clear that bit; advance to the next set bit
 
 
# Iterate over set bits of 0b10110100 (positions 2, 4, 5, 7).
print(list(iterate_set_bits(0b10110100)))   # [2, 4, 5, 7]

Two design notes:

  1. Negative inputs are rejected. Two’s-complement representation makes n & (n-1) meaningless for negative n (in Python, integers are arbitrary-precision; the bit pattern of a negative integer is conceptually infinite leading 1s, so the loop would not terminate). Always pre-validate the sign in production code.
  2. n.bit_length() - 1 recovers the position. n & -n returns the value of the lowest set bit (a power of 2, like 0b10000); to convert to the bit index (the exponent), use bit_length() - 1. An alternative is int.bit_count() of low - 1 (if the bit is at position k, then low - 1 has k set bits in positions 0..k-1), but bit_length() - 1 is clearer and equally fast.

5. Complexity — Why It’s O(popcount(n)) and What That Buys You

The loop body runs once per iteration of n != 0 in the while. Each iteration clears exactly one set bit (proved in §1). Therefore the loop runs exactly popcount(n) times, where popcount(n) is the number of 1-bits in n.

Each iteration does a constant number of arithmetic operations (one subtraction, one AND, one increment, one comparison) — O(1) work per iteration on machine-word-sized integers. Total: O(popcount(n)) time, O(1) space.

For an m-bit integer:

  • Worst case (n = 2^m - 1, all bits set): O(m) iterations.
  • Best case (n is a power of 2 or 0): 0 or 1 iteration.
  • Average (uniformly random n): m/2 iterations on average — same asymptotic as worst case.

5.1 Comparison with Naïve “Check Each Bit”

def popcount_naive(n):
    count = 0
    for k in range(64):
        if (n >> k) & 1:
            count += 1
    return count

This always runs 64 iterations regardless of n. So Kernighan’s wins whenever popcount(n) < 64 — almost always in practice, since random 64-bit integers average 32 set bits. Even in the worst case (all bits set), Kernighan’s matches the naïve method. Kernighan’s is never worse than the naïve loop and is strictly better for any n with fewer than 64 set bits.

5.2 Comparison with Hardware popcnt

Modern CPUs have a dedicated popcnt instruction:

  • Intel x86-64: popcnt (added in SSE4.2, ~2008; available on Nehalem and later).
  • AMD x86-64: ABM (Advanced Bit Manipulation) extension, ~2007.
  • ARM: NEON cnt instruction (counts bits in each byte; reduce with addv).
  • RISC-V: cpop in the B extension.

These execute in 1–3 clock cycles for a 64-bit integer regardless of the bit pattern. For a 64-bit input with k set bits:

MethodCyclesNotes
Hardware popcnt1–3Single cycle on most modern x86
16-entry SWAR lookup table4–8Portable, no special instruction
Brian Kernighan’s~3 * kLoop overhead per set bit
Naïve (n >> k) & 1 loop~3 * 64 = ~192Worst-case bound

For k = 1 (one set bit), Kernighan’s takes ~3 cycles, the same as popcnt. For k = 32 (average random input), Kernighan’s is 96 cycles vs popcnt’s 1 cycle — popcnt is ~30x faster.

So why is Kernighan’s still taught? Because:

  1. Not all targets have popcnt (embedded systems, ancient hardware, certain JIT environments).
  2. Compilers don’t always emit popcnt for __builtin_popcount unless you target the right CPU (-march=nehalem or later for x86, -mfpu=neon for ARM, etc.).
  3. Kernighan’s is the inner loop for iterating over set bits, not just counting them. When the action per set bit is non-trivial (e.g., updating a Bitmask DP state or enumerating subset masks), Kernighan’s clear-the-lowest-bit pattern is the cleanest portable way to walk those bits.

5.3 In Python Specifically

Python’s int.bit_count() (added in Python 3.10, October 2021) is the language-level equivalent: it computes popcount and uses the underlying C implementation, which can call __builtin_popcountll (GCC) and ultimately the hardware popcnt. So in modern Python:

n.bit_count()           # Python 3.10+; uses hardware popcnt under the hood
bin(n).count('1')       # universal but slow; converts to string first
popcount_kernighan(n)   # portable; O(popcount(n)); pure-Python

For arbitrary-precision integers (Python’s native int is unlimited), Kernighan’s still works but bit_count() is implemented as a per-limb popcount and is much faster for very large n (e.g., 1000-bit integers).

6. Variants and Use Cases

6.1 Iterating Over Set Bits in Bitmask DP

In Bitmask DP / Subset Enumeration with Bitmasks, you often need to enumerate the set bits of a mask. Kernighan’s clear-lowest-bit trick is the standard inner loop:

mask = 0b1010_0110
while mask:
    bit = mask & -mask          # isolate lowest set bit (value)
    pos = bit.bit_length() - 1  # convert to index
    # ... use pos in the DP transition ...
    mask &= mask - 1            # clear it

The runtime is O(popcount(mask)) per iteration — strictly better than O(n) for sparse masks.

6.2 Power-of-Two Detection

n & (n - 1) == 0 (with n != 0) iff n is a power of two. Reason: powers of two have exactly one set bit; clearing it gives 0. This is a one-line idiom in C, Java, Rust:

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

This is the single most common use of the n & (n-1) identity in production code (allocators, hash tables, Fenwick Tree preprocessing).

6.3 Fenwick Tree / Binary Indexed Tree Updates

The Fenwick tree’s update and query operations use the pattern i += i & -i (isolate lowest bit and add) and i -= i & -i (clear lowest bit by subtraction). The complementary n & (n-1) clear is structurally equivalent — both peel off the lowest set bit. This is why the Fenwick tree’s loops have O(log n) complexity: each iteration removes one set bit from the index, and a log n-bit number has at most log n set bits.

6.4 Hamming Distance Between Two Bitmasks

The number of differing positions between bitmasks a and b is popcount(a XOR b). With Kernighan’s:

def hamming_distance(a: int, b: int) -> int:
    diff = a ^ b
    count = 0
    while diff:
        diff &= diff - 1
        count += 1
    return count

Used in error-correcting codes (Hamming Code family), nearest-neighbor search on binary feature vectors, and DNA sequence comparison.

6.5 Determining the Number of Bits to Flip

When transforming bitmask a into bitmask b, the minimum number of single-bit flips required is popcount(a XOR b). Same algorithm as Hamming distance.

6.6 Cardinality of Set Membership Encoded as a Bitmask

For small universes (≤ 64 elements), a subset is naturally encoded as a 64-bit integer. The cardinality is the popcount. Kernighan’s gives O(|S|) iteration where |S| is the cardinality.

6.7 SWAR Variants — Faster But Less Pedagogical

For pure counting (not iteration), the SIMD-Within-A-Register (“SWAR”) algorithm — popularized in Hacker’s Delight §5.1 — counts bits in O(log m) operations regardless of popcount, using parallel reduction:

def popcount_swar64(n: int) -> int:
    n = (n & 0x5555_5555_5555_5555) + ((n >> 1) & 0x5555_5555_5555_5555)
    n = (n & 0x3333_3333_3333_3333) + ((n >> 2) & 0x3333_3333_3333_3333)
    n = (n + (n >> 4)) & 0x0F0F_0F0F_0F0F_0F0F
    return (n * 0x0101_0101_0101_0101) & 0xFFFF_FFFF_FFFF_FFFF) >> 56

This is O(1) for fixed-width integers and faster than Kernighan’s when popcount(n) is large. Less pedagogically transparent (the constants encode “count pairs, then nibbles, then bytes, then a multiplication-based final reduction”). Used in libraries that need portable popcount but can’t assume hardware popcnt.

Attribution. The SWAR / divide-and-conquer popcount family is documented at length in Warren’s Hacker’s Delight §5.1, which gives the algorithm itself but does not pin down a single inventor — by the 1970s the idea was already folklore. Stanford’s Bit Twiddling Hacks credits Andrew Shapira (October 2005) for surfacing the specific 64-bit AMD-Athlon-tuned variant from the Software Optimization Guide for AMD Athlon 64 and Opteron Processors (pages 187–188), with subsequent operation-count reductions by Charlie Gordon (December 2005) and Don Clugston (December 2005). Wikipedia’s Hamming weight article credits Wegner 1960 only for the separate n & (n-1) clear-lowest-bit method (i.e. this note’s algorithm), not for the SWAR variant. The “Wilkes-Wheeler-Gill 1957” attribution sometimes circulated for SWAR popcount appears to be apocryphal — it does not show up in Hacker’s Delight, Stanford bithacks, Wikipedia, or the Wegner CACM note, so this note declines to assert it.

6.8 Fast Subset Enumeration via Repeated (s - 1) & mask

A different but related bit trick — enumerating all subsets of a mask m:

s = m
while s > 0:
    # s is a subset of m
    process(s)
    s = (s - 1) & m
# Don't forget s = 0 (the empty subset).

This iterates over all 2^popcount(m) subsets of m in O(2^popcount(m)) total. Different identity from Kernighan’s ((s - 1) & m, not s & (s-1)), but related family. Used heavily in Subset Enumeration with Bitmasks.

7. Pitfalls

7.1 Negative Inputs

In Python, integers are arbitrary-precision and negative numbers have a conceptually infinite sequence of leading 1s in two’s-complement. The loop while n != 0: n &= n - 1 does not terminate for negative n — n stays negative forever. Always validate n >= 0 or apply a mask: popcount_kernighan(n & ((1 << 64) - 1)) if you want only the low 64 bits.

In C/C++/Java/Rust with fixed-width integers, the bit pattern of a negative number is well-defined and Kernighan’s works correctly on the bit pattern. But the popcount of the bit pattern of -1 is the full word width (64 for 64-bit), which is rarely what the caller wants. Be explicit about whether you want signed-magnitude popcount or two’s-complement bit-pattern popcount.

7.2 Integer Overflow on n - 1 (in Fixed-Width Languages)

n = 0 makes n - 1 = -1 (or UINT_MAX for unsigned), and 0 & -1 = 0. The loop guard while n != 0 handles this safely (we exit before computing n - 1 for n = 0). But if a careless implementation computes n - 1 before the guard, it can produce subtle bugs. Stick to the standard while (n) { n &= n - 1; count++; } form.

7.3 Confusing n & (n-1) with n & (-n)

These are different operations, both useful, easy to mix up:

  • n & (n - 1) = n with its lowest set bit cleared.
  • n & -n = the value of the lowest set bit (a power of 2).

Examples: for n = 0b1100 (12):

  • n & (n - 1) = 0b1100 & 0b1011 = 0b1000 (8 — n with lowest bit cleared).
  • n & -n = 0b1100 & 0b...11110100 = 0b100 (4 — the lowest bit’s value).

To iterate over set bits, you typically want both: isolate the lowbit (for what to do with it), then clear it (for advancing). Mixing them up gives wrong results.

7.4 Off-By-One in bit_length() - 1

To convert a power-of-two value low = n & -n to its bit position:

pos = low.bit_length() - 1   # correct
pos = low.bit_length()       # WRONG: off-by-one (returns position+1)

For low = 4 = 0b100, bit_length() = 3 (number of bits to represent 4 in binary), and the bit position of the single 1 is 3 - 1 = 2. Easy mistake.

7.5 Forgetting That Hardware popcnt Exists

In modern Python (3.10+), n.bit_count() is a one-liner that uses the hardware popcount. In modern C/C++, __builtin_popcountll(n) (GCC/Clang) or std::popcount(n) (C++20) does the same. Hand-rolling Kernighan’s when these exist is a code-smell unless you have a portability or pedagogical reason. Use the built-in; reach for Kernighan’s only when you need to iterate over set bits or when targeting platforms without popcnt.

7.6 Believing Kernighan’s Is Always the Fastest

For n with many set bits (e.g., uniformly random 64-bit integers, average 32 set bits), Kernighan’s takes ~96 cycles, while hardware popcnt is 1 cycle and SWAR is ~12 cycles. Kernighan’s wins only when both (a) hardware popcnt is unavailable AND (b) popcount(n) is small. In practice, for sparse bitmasks (e.g., a 1024-element bitmap representing a small set of selected items), Kernighan’s is often the right choice; for dense bitmaps, prefer hardware or SWAR.

7.7 Treating n & (n-1) == 0 as the Power-of-Two Test Without n != 0

0 & (-1) = 0 — so n = 0 would falsely register as a power of two by the simple test. Always add the n > 0 (or n != 0) guard:

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

A surprising number of competitive-programming submissions miss this and fail on the n = 0 edge case.

7.8 Misunderstanding the O(popcount) Bound for Adversarial Inputs

For all-ones inputs (n = 2^64 - 1), Kernighan’s runs 64 iterations — same as naïve. The O(popcount(n)) bound is better than naïve only for sparse inputs. If your problem statement guarantees dense inputs, the naïve loop is no worse and may be faster due to better branch prediction. Always benchmark for the actual input distribution.

7.9 Using n.bit_count() on Pre-3.10 Python

int.bit_count() was added in Python 3.10 (October 2021). On Python 3.9 and earlier, the call raises AttributeError. Portable Python code should fall back to:

try:
    from sys import version_info
    if version_info >= (3, 10):
        popcount = int.bit_count
    else:
        raise ImportError
except (ImportError, AttributeError):
    def popcount(n: int) -> int:
        count = 0
        while n:
            n &= n - 1
            count += 1
        return count

or simply use bin(n).count('1') (slower but always available since Python 2.6+).

8. Diagram — One Iteration of Kernighan’s Algorithm

flowchart TB
    Start["n = ...XYZ 1 0...0<br/>(some prefix XYZ, then a 1, then k zeros)"]
    Sub["Compute n - 1<br/>= ...XYZ 0 1...1<br/>(borrow propagates through the trailing zeros<br/>and flips the lowest 1 to 0)"]
    And["Compute n AND (n - 1)<br/>= ...XYZ 0 0...0<br/>(prefix XYZ unchanged;<br/>lowest 1 and the trailing zeros all become 0)"]
    Result["Result: n with its lowest set bit cleared.<br/>The popcount has decreased by exactly 1."]

    Start --> Sub
    Sub --> And
    And --> Result

What this diagram shows. The bit-level mechanics of one iteration of Brian Kernighan’s algorithm. We start with n, depicted as some arbitrary prefix XYZ, followed by the lowest 1-bit, followed by k >= 0 trailing zeros. Subtraction step: n - 1 flips the lowest 1 to a 0 and turns all the trailing zeros into 1s — this is the borrow-propagation rule of binary subtraction. The prefix XYZ is untouched because the borrow stops at the first 1 it encounters (the lowest 1-bit, which it consumes). AND step: bitwise AND of n and n - 1 matches in the prefix (both are XYZ); at the lowest-1 position, 1 AND 0 = 0; and below it, 0 AND 1 = 0. The result is n with exactly one bit cleared — the lowest 1-bit. Key insight: every iteration of the loop guarantees a strict decrease in the popcount (by exactly 1), so the loop terminates after exactly popcount(n_initial) iterations and the runtime is proportional to the number of set bits. The diagram also clarifies why naïve “check each bit” is wasteful when the input is sparse: Kernighan’s algorithm “fast-forwards” through runs of zeros via the borrow propagation in n - 1, skipping them in O(1) per cleared bit, whereas naïve iteration visits every bit position regardless.

9. Common Interview / Competitive-Programming Problems

ProblemSourceWhat’s tested
Number of 1 BitsLC 191Direct application of Kernighan’s
Power of TwoLC 231n > 0 && (n & (n-1)) == 0 idiom
Hamming DistanceLC 461popcount of XOR — combine with Kernighan’s
Counting BitsLC 338DP on bit-count using Kernighan’s recurrence: bits[n] = bits[n & (n-1)] + 1
Subset Sum / Bitmask DP problemsvariousIterate over set bits of mask using n & (n-1) clear
Single Number IIILC 260Use n & -n to isolate a distinguishing bit; complementary trick
Maximum Product of Word LengthsLC 318Bitmask over alphabet; AND for disjointness check
Minimum Number of K Consecutive Bit FlipsLC 995Sliding-window with bitmask; Kernighan’s for popcount
Total Hamming DistanceLC 477O(n * 32) direct or O(n) per bit position; Kernighan’s not the right tool here

In FAANG-style interviews, Kernighan’s is a likely follow-up to the basic “count bits in an integer” question — interviewers often ask for the O(popcount) improvement after seeing the naïve O(bit_width) solution. It’s the canonical bit-trick interview question, alongside n & -n lowbit isolation. Knowing the K&R reference and its precedence by Wegner 1960 is a positive signal of “I read primary sources.”

10. Open Questions

  • Is there an algorithm that beats O(popcount) for iterating set bits (not just counting them)? On hardware, BMI extensions like tzcnt (count trailing zeros) plus blsr (clear lowest set bit, the hardware version of n & (n-1)) give a 2-cycle iteration per bit, which is essentially optimal. There’s no known asymptotic improvement; the bound is tight up to constants.
  • How does Kernighan’s compare to rank/select data structures for very large bitmaps? For static bitmaps, succinct rank/select structures (Jacobson 1989, Clark 1996) give O(1) rank queries with o(n) extra space. Iterating set bits via Kernighan’s on the underlying word is still the inner-loop primitive within these structures.
  • Can the borrow-propagation insight be generalized to higher radix representations (base 4, base 16, etc.) for similar tricks? Yes — the analogous identity n & (n - r) for radix-r “lowest unit” detection works in some niche contexts (e.g., counting trailing zero digits in decimal), but loses the elegance because the AND is no longer the right operator across radixes.
  • Is there a theoretical lower bound for popcount in the cell-probe model? Yes — Omega(log w / log log w) for a w-bit input under polylog space, but with O(w) space the bound is O(1) (a lookup table of all 2^w inputs). For w = 64 that’s a 16 GB lookup table — impractical, hence Kernighan’s / SWAR / hardware popcnt.

11. Historical Note — Wegner vs Kernighan

The n & (n - 1) identity is universally credited as “Brian Kernighan’s algorithm” in interview prep and CS-folklore contexts because of its appearance in Kernighan & Ritchie’s The C Programming Language (1988, 2nd ed., Exercise 2-9). However, the trick was published 28 years earlier:

Wegner, P. (1960). “A technique for counting ones in a binary computer.” Communications of the ACM 3(5): 322.

Wegner’s 1-page CACM note describes the same algorithm, with a hand-traced example. By 1988 the trick was “folklore” enough that K&R could include it as an exercise without citing Wegner; the modern attribution to “Kernighan” is a function of K&R’s massive readership rather than original discovery.

For correct attribution in a paper or thesis, cite Wegner 1960 as the primary source and K&R 1988 as the popularizer. In an interview, calling it “Brian Kernighan’s algorithm” is universally understood and not strictly wrong — the name is the social fact, even if the history is more nuanced.

12. See Also

Graph View

Backlinks