Approach Summary
Brian Kernighan: n &= (n-1) clears the lowest set bit. Count iterations until n = 0.
Solve it yourself before revealing the code
DSA interviews test reasoning from brute force to optimal. Think through the constraints first.
Solution Progression (Brute Force → Most Optimized)
Understand the architectural evolution from naive baseline to optimal complexity.
| Approach | Time | Space | Core Strategy / Trade-off |
|---|---|---|---|
| 1 Approach 1: Bit Shift & Mask (Check All 32 Bits) | O(1) [always 32 iterations] | O(1) | Loop through all 32 bit positions and increment count whenever (n & 1) equals 1. |
| 2 Approach 2: Brian Kernighan's Algorithm (Optimal) | O(k) where k <= 32 is number of set bits | O(1) | Clear the lowest set bit using n & (n - 1) on each iteration, looping only as many times as set bits. |
Approach 1: Bit Shift & Mask (Check All 32 Bits)
Inspect the least significant bit with n & 1. If it is 1, increment the counter. Then shift n to the right by 1 position (using unsigned right shift >>> in JavaScript and Java to avoid sign-extension). Repeat this process 32 times. This baseline guarantees correctness but always executes 32 loop cycles even if n is 1.
Approach 1: Bit Shift & Mask (Check All 32 Bits) Implementation
Approach 1: Bit Shift & Mask (Check All 32 Bits)
public class Solution {
public int hammingWeight(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
count += (n & 1);
n >>>= 1;
}
return count;
}
}class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
for (int i = 0; i < 32; i++) {
count += (n & 1);
n >>= 1;
}
return count;
}
};class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
for _ in range(32):
count += (n & 1)
n >>= 1
return countfunction hammingWeight(n) {
let count = 0;
for (let i = 0; i < 32; i++) {
count += (n & 1);
n >>>= 1;
}
return count;
}Approach 2: Brian Kernighan's Algorithm (Optimal)
Subtracting 1 from binary number n flips the lowest set bit to 0 and all trailing 0s to 1s. Bitwise ANDing n with n - 1 leaves all bits to the left of the lowest set bit unchanged while setting that lowest bit and all trailing bits to 0. Thus, each iteration drops exactly one 1-bit. If n has only 3 set bits, the loop executes exactly 3 times.
Approach 2: Brian Kernighan's Algorithm (Optimal) Implementation
Approach 2: Brian Kernighan's Algorithm (Optimal)
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
}class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
while (n != 0) {
n = n & (n - 1);
count++;
}
return count;
}
};class Solution:
def hammingWeight(self, n: int) -> int:
count = 0
while n:
n &= (n - 1)
count += 1
return countfunction hammingWeight(n) {
let count = 0;
while (n !== 0) {
n = n & (n - 1);
count++;
}
return count;
}Edge Cases to Watch
- n is 0 (has zero 1 bits, loop terminates immediately)
- n has only a single bit set (e.g., powers of 2 like 1, 2, 4, 1024; finishes in 1 iteration)
- n is 0xFFFFFFFF (all 32 bits set, maximum count of 32)
- High order bit set (n >= 2^31; requires unsigned right shift in Java using >>>)
Master the Bit Manipulation Pattern
Study the core invariant, step-by-step decision framework, and common interview traps for the Bit Manipulation pattern.
How to Recognize This Pattern
- "Hamming weight / popcount"
- n & (n-1) strips the rightmost 1 bit each iteration
Complexity Analysis
Time Complexity
O(1)
Space Complexity
O(1)