◄ WORLD V · SONNY 5DART 411 · a helldive at the net

KERNIGHAN’S COUNT n & (n−1) drops the lowest 1-bit — loop once per set bit

There is a two-character spell that clears the lowest set bit of any integer: n & (n−1). Subtracting one flips the lowest 1 to 0 and all the zeros below it to 1; ANDing with the original wipes that whole tail. Repeat until you hit zero, counting the steps, and you have the population count — but the loop runs only once per set bit, not once per bit. For sparse words that is a large win, and the identity itself is a small marvel of two’s-complement.

THE TECHNIQUE n & (n−1) clears the lowest set bit; count the steps

The demo counts the 1-bits of 23 (10111) by clearing the lowest set bit each step, showing the word shrink to zero in four steps: live demo







  
HISTORY & CREDIT Wegner 1960 · Kernighan popularized

  
“Counting bits means looking at every bit.” — only at the set ones: n & (n−1) skips straight to the next 1. cited

  
the identity · n−1 flips the lowest 1 and the zeros under it; n & (n−1) erases that tail — one set bit gone.
the loop · iterate to zero, counting — steps = number of set bits (sparse-word fast).
1960 · Peter Wegner published the technique; popularized in Kernighan & Ritchie.

  
The lowest 1 struck off with a single AND — a bit-count that visits only what is set. resource






  
RECOMMEND FOR I-13 clear-lowest-bit, on the compiler

  
On the canonical compiler, clearing the lowest set bit of 23 four times reaches zero — 23 has four 1-bits:

  
$ i13 run tk_kernighan.i13   # loop: n = n & (n-1)
RUN OK · 82 step(s) · peak stack 4 · call depth 5
n = 23        -- 10111
bits = 4      -- four clears to reach 0
same = 1      -- matches popcount(23)

  
Recommend as a NULL, paired with the-popcount (dart 412). Kernighan’s count computes the very same Hamming weight as the naive shift-and-sum — i13 prints 4 both ways — but loops once per set bit instead of once per bit. Pure resource (B40): a data-dependent speedup on an identical output. The n & (n−1) identity is lovely, but loveliness is not an axis. NULL; its value is as the sharp, minimal instance of “fewer iterations, same answer.”