LeetCode · #191
Number of 1 Bits Solution
Return the number of set bits (1s) in the binary representation of an unsigned integer.
01
Section One · Problem
Problem Statement
Example
Input: n = 11 // binary: 1011 Output: 3
02
Section Two · Approach 1
Shift and Mask — O(32)
Check each of the 32 bits: if (n & 1) count++; n >>>= 1;. Always 32 iterations.
Java — Shift & mask
class Solution {
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
count += n & 1;
n >>>= 1;
}
return count;
}
}
Python — Shift & mask
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0 while n:
count += n & 1
n >>= 1 return count
03
Section Three · Approach 2
Brian Kernighan's Trick — O(k) where k = # of 1 bits
n & (n-1) clears the lowest set bit. Count how many times until n becomes 0. Only iterates k times (number of set bits).
💡 Mental model: Imagine n as a row of light switches.
n-1 flips all bits from the rightmost ON switch down. AND-ing with n turns off that rightmost switch. Each operation kills exactly one light. Count the kills.🎯 When to recognize this pattern: "Count set bits" or "is power of two" (check
n & (n-1) == 0). Brian Kernighan's trick is faster than iterating all 32 bits when few are set.04
Section Four · Trace
Visual Walkthrough
Brian Kernighan's — n=11 (1011₂)
05
Section Five · Implementation
Code — Java & Python
Java — Brian Kernighan
class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n &= (n - 1); // clear lowest set bit
count++;
}
return count;
}
}
Python — Brian Kernighan
class Solution:
def hammingWeight(self, n: int) -> int:
count = 0 while n:
n &= n - 1
count += 1 return count
06
Section Six · Analysis
Complexity Analysis
| Approach | Time | Space |
|---|---|---|
| Shift & mask | O(32) | O(1) |
| Brian Kernighan ← optimal | O(k) k=set bits | O(1) |
07
Section Seven · Edge Cases
Edge Cases & Pitfalls
| Case | Input | Why It Matters |
|---|---|---|
| Zero | 0 | No set bits → 0. |
| All ones (32-bit) | 0xFFFFFFFF | 32 set bits. |
| Power of two | 16 = 10000₂ | Exactly 1 set bit → 1. |
⚠ Common Mistake: In Java, using
>> (arithmetic right shift) instead of >>> (unsigned right shift). For negative numbers (high bit set), >> fills with 1s → infinite loop. Always use >>> for unsigned right shift, or use Brian Kernighan's trick (no shifting needed).