Module 25 · Bit Manipulation, Mathematics, and Designed Data Structures

243. Count Set Bits

Foundation · Download this solution · All solutions and shared helpers

Problem

Return the number of one bits in the binary representation of a nonnegative integer n. Zero has zero set bits. Negative integers are outside this unbounded-width contract; a fixed-width interpretation would require an explicit mask.

Examples

Example 1

count_set_bits(44)
=> 3

Binary 101100 contains three one bits.

Example 2

count_set_bits(0)
=> 0

No loop iteration is needed.

Example 3

count_set_bits(16)
=> 1

A power of two has one set bit.

Reveal the worked solution and reasoning

Why this mechanism works

Subtracting one flips the lowest set bit to zero and all lower zero bits to one. ANDing that result with the original removes exactly the lowest set bit and leaves all higher set bits unchanged. Count how many such removals are needed to reach zero.

State and boundaries

count is the number of original set bits removed. The current n contains exactly the remaining original set bits.

Protocol

Initialize count to zero.
While n is nonzero, assign n=n AND (n-1).
Increment count.
Return the number of removals.

Visualization

n     = 101100
n-1   = 101011
AND   = 101000
the lowest one bit was removed

Python implementation

def count_set_bits(n):
    count = 0
    while n:
        n &= n - 1
        count += 1
    return count

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

count_set_bits(44)

L2 count_set_bits: count = 0
n=44; count=0

L4 count_set_bits: n &= n - 1
n=40; count=0

L5 count_set_bits: count += 1
n=40; count=1

L4 count_set_bits: n &= n - 1
n=32; count=1

L5 count_set_bits: count += 1
n=32; count=2

L4 count_set_bits: n &= n - 1
n=0; count=2

L5 count_set_bits: count += 1
n=0; count=3

Result: 3. Binary 101100 contains three one bits.

count_set_bits(0)

L2 count_set_bits: count = 0
n=0; count=0

Result: 0. No loop iteration is needed.

Why the solution is correct

For every positive n, the AND identity clears exactly one one-bit. Thus the invariant is preserved and the number of remaining set bits strictly decreases. When n reaches zero, every original one-bit has been removed exactly once, so count is correct.

Time and space

O(k) bitwise operations for k set bits, using a constant number of integer variables. For arbitrary b-bit Python integers, each operation may cost O(b), giving O(k*b) coarse bit work.

Common mistakes

Right-shifting a negative Python integer preserves the sign indefinitely; negative-width assumptions also break this loop. Counting decimal digits does not measure binary set bits.

Reasoning card

State: count is the number of original set bits removed. The current n contains exactly the remaining original set bits.

Invariant: Each iteration removes exactly one set bit.

Decision to rehearse: Repeatedly clear the lowest set bit with n &= n-1.

Finish: Return the number of removals

Transfer exercise

Count bits of a signed 32-bit value by first masking with (1<<32)-1, and explain the resulting representation.