Number of 1 Bits

Brian Kernighan's loop — `n &= n - 1` clears the lowest set bit each iteration.

Easy
Time O(popcount) Space O(1)
LeetCode
2 min read
bit-manipulation

Problem#

Return the number of 1 bits in the binary representation of an unsigned 32-bit integer.

Examples#

  • n=11 (1011) → 3.
  • n=1281; n=429496729331.

Constraints#

  • 0 <= n <= 2^32 - 1.

Approach#

Repeatedly clear the lowest set bit via n &= n - 1, counting iterations.

Solution#

Number of 1 Bits
class Solution {
public:
int hammingWeight(uint32_t n) {
int c = 0;
while (n) { n &= n - 1; ++c; }
return c;
}
};

Editorial#

n - 1 flips all bits at and below the lowest set bit of n; ANDing clears that bit. So the loop runs once per set bit, regardless of total bit width — O(popcount) rather than O(32). __builtin_popcount is the hardware-backed alternative.

Complexity#

  • Time: O(popcount(n)).
  • Space: O(1).

Concept revision#

Search ESC

Keyboard shortcuts

Shortcuts are disabled while typing in inputs.