1. Until cleared
Keep going while any set bit remains.
while (n !== 0)Typorithm · medium
Count Set Bits
▷ Interactive algorithm labcount-set-bitsbit-manipulationkernighanlowest-bitand-mask
Saved on this device
Full lesson · 8 learning steps Open any exercise for focused practice
10%
Step 1 of 8 · intro card
Learn Count Set Bits
Bit Manipulation
Brian Kernighan's trick: n & (n-1) clears the lowest set bit, so loop until n is zero.
Counting bits one shift at a time always takes 32 steps; Kernighan's trick only iterates per set bit.
Subtracting 1 flips the lowest set bit and all zeros below it; ANDing with n clears just that bit.
The loop runs once per set bit, so it is fast on sparse numbers.
Preparing algorithm lab…
01
n & (n-1) clears the lowest set bit.
02
Loop runs once per set bit.
03
No fixed 32-step scan.
function countSetBits(n) {
let count = 0;
while (n !== 0) {
n = n & (n - 1);
count += 1;
}
return count;
}Read the implementation
Connect each part of the code to the concept before you type.
2. Clear lowest bit
n & (n-1) removes exactly the lowest set bit each step.
n = n & (n - 1)3. Tally it
Each cleared bit is one more set bit counted.
count += 1A complete learning loop
01
Understand
Read the concept map and follow the code breakdown.
02
Reconstruct
Type the implementation, repair mistakes and work through every recall exercise.
03
Verify
Use the final check without hints; revisit weak concepts in short practice sessions.