Number of 1 Bits

Return the number of set bits (1s) in a 32-bit unsigned integer. A naive per-bit check works, but we can skip zero blocks efficiently.

Why this is worth learning

Subtracting one flips the lowest set bit to zero and every lower zero to one. AND with the original keeps higher bits and clears exactly that lowest set bit.

Before coding: one-minute experiment

For binary 101100, what is n&(n-1), and how many iterations will the complete count take?

Function signature

func HammingWeight(n uint32) int

Inputs / outputs

• n: 32-bit unsigned integer.
• Return: count of 1 bits.

Example

Input: 00000000000000000000000000001011
Output: 3

Constraints

• Input fits in 32 bits.

Core idea (near-solution)

Inspecting every one of the 32 positions is a valid constant-time baseline. If work should depend on how many ones exist, find an operation that removes exactly one without changing the others. Subtracting one changes the lowest 1 to 0 and all lower 0s to 1; AND with the original removes those temporary ones. Thus one iteration can be charged to one original set bit.

Use Brian Kernighan's trick: n &= n-1 clears the lowest set bit each step.

Invariant: each iteration removes exactly one set bit.

Algorithm (step-by-step)

1. Initialize count = 0.
2. While n != 0:
   • n &= n - 1.
   • count++.
3. Return count.

Correctness sketch

For nonzero n, write its low portion as a 1 followed by k zeroes. The same portion of n-1 is a 0 followed by k ones, while higher bits are unchanged. Their AND therefore removes exactly one set bit and changes no higher set bits. Each loop iteration increments count once and reduces the number of remaining ones by one. When n reaches zero, count equals the original population count. Starting at zero performs no subtraction, avoiding any need to reason about unsigned wrap in that branch.

Trace (hand walkthrough)

Example input:
Input: 00000000000000000000000000001011
Output: 3

Walk:
- 1011 & 1010 -> 1010 (count=1)
- 1010 & 1001 -> 1000 (count=2)
- 1000 & 0111 -> 0000 (count=3)

Pitfalls to avoid

• Using signed integers and relying on sign behavior.
• Looping a fixed 32 iterations unnecessarily.

Debugging lens

Test sparse inputs as well as dense masks. This loop counts set bits, not the position of the highest set bit. Keep the input unsigned and distinguish a fixed 32-bit bound from a variable-width analysis.

Complexity

• Time: O(k) where k is the number of set bits.
• Extra space: O(1).

Implementation notes (Go)

• Use uint32 to avoid sign extension on shifts.

Reconstruction checkpoint

For binary 101100, what is n&(n-1), and how many iterations will the complete count take?

Return to Bit Manipulation · Module quiz