BitsBit Manipulation

Count Set Bits (Kernighan)

Count the 1-bits of an integer with Kernighan's loop, a byte lookup table, a hardware popcount, or a DP over all numbers up to n.

Learn Count Set Bits (Popcount) →
n
1
7
0
6
1
5
1
4
0
3
1
2
0
1
0
0
= 180
1/14n = 180 (10110100). Instead of testing all 8 bits, Kernighan's trick loops once per set bit.
Lowest set bit about to be clearedBit cleared by n & (n-1)Set bits still remaining
PseudocodeLearn Count Set Bits (Popcount) →
1count = 0
2while n != 0:
3  n = n & (n - 1)   # clears the lowest set bit
4  count += 1
5return count
Variables
n180
count0
Complexity
best O(1)
avg O(k)
worst O(w)
space O(1)
Speed