Count Set Bits

Brian Kernighan's algorithm counts 1-bits in O(set bits) time by repeatedly clearing the lowest set bit with n & (n−1).

Time: O(set bits)Space: O(1)Bit Clearing

Input Number (1–255)

Binary: 00010111

Set bits: 4

Binary Register

current n (23)

Set bits cleared so far

FastSlowStep 1 / 0

Active Recall Quiz

Question 1/3

Why does n & (n−1) always clear the lowest set bit of n?

Current State

Original n23

Current n23

Bits cleared0

Iteration1 / 0

Why n & (n−1)?

Subtracting 1 flips the rightmost 1-bit to 0 and turns all trailing 0s to 1s. AND-ing with the original n zeroes out exactly that one set bit, leaving all higher bits untouched.

Example: n = 12 (1100)

n−1 = 11 (1011)

AND → 8 (1000) ✓

DSAverse

Bit Manipulation

Loading Bit Manipulation...

Binary Register

bit 15bit 0