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.

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)

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

• Invariant: each iteration removes exactly one set bit.
• Bitwise operations preserve the required per-bit invariant.
• Combining results across bits reconstructs the correct value.
• Therefore the final bit-accumulated result is correct.

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.

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.