AlgoScope

Count Set Bits

Clear the lowest 1 with n and (n - 1) until nothing is left, counting rounds.

Bit manipulation, algorithm, beginnerAlso called popcount, Hamming weight
Round 1 clears bit 1, leaving 176.0001020314150617bit
Round 1 clears bit 1, leaving 176.0001020314150617bit

Bit Manipulation: Count the 1s, Kernighan style

Decision, step 2 of 6

178 and 177 = 176. Subtracting 1 borrows through the trailing zeros, so the AND wipes exactly the lowest 1, at bit 1. That is round 1.

How bit manipulation works

Cost

Best
O(1)
Average
O(log n)
Worst
O(log n)
Space
O(1)

Before this

Leads to

Topics that need this one first.

Taught by the same lesson

Bit Manipulation covers these too, in the same run.