Number of 1 Bits
Brian Kernighan's loop — `n &= n - 1` clears the lowest set bit each iteration.
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=128→1;n=4294967293→31.
Constraints#
0 <= n <= 2^32 - 1.
Approach#
Repeatedly clear the lowest set bit via n &= n - 1, counting iterations.
Solution#
class Solution {public: int hammingWeight(uint32_t n) { int c = 0; while (n) { n &= n - 1; ++c; } return c; }};func hammingWeight(n int) int { c := 0 for n != 0 { n &= n - 1 c++ } return c}class Solution: def hammingWeight(self, n: int) -> int: c = 0 while n: n &= n - 1 c += 1 return cfunction hammingWeight(n) { let c = 0; while (n !== 0) { n &= n - 1; c++; } return c;}class Solution { public int hammingWeight(int n) { int c = 0; while (n != 0) { n &= n - 1; c++; } return c; }}function hammingWeight(n: number): number { let c = 0; while (n !== 0) { 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#
Related#