Bit Manipulation — Number of 1 Bits
↗ LeetCode: Number of 1 Bits · Easy · pattern chapter →
Asked atMetaAmazonAppleGoogleMicrosoft
Return the popcount (number of set bits) of an unsigned 32-bit integer.
Example 1 — n=00000000000000000000000000001011 → 3Example 2 — n=11111111111111111111111111111101 → 31
Constraints — 32-bit unsigned. Brute bit-shift loop is O(32) = 32 ops. Integer.bitCount is 1 hardware popcnt = ~1 CPU cycle → 10⁹ ops/sec.
Progressive Hints
Try to solve it yourself first. Reveal hints only when stuck — each hint is progressively more specific.
Interview timer00:00
Practice under interview pressure. Start when you begin reading; stop when you finish. Save best only when you had a full working solution.
Target for interview: Medium = 20-25 min · Hard = 30-40 min · Best time persists on this device only.
Approach 1 — Loop all 32 bits
java
int hammingWeight1(int n) {
int c = 0;
for (int i = 0; i < 32; i++) if ((n & (1 << i)) != 0) c++;
return c;
}O(32) always.
Approach 2 — Kernighan's trick (clear lowest set bit)
Insight. n & (n-1) clears the lowest set bit. Iterate until 0; count iterations.
java
int hammingWeight(int n) {
int c = 0;
while (n != 0) { n &= n - 1; c++; }
return c;
}Complexity — Time O(# set bits); Space O(1).
Approach 3 — Built-in
java
int hammingWeight3(int n) { return Integer.bitCount(n); }Uses hardware popcount when available.
Try it yourself
Complexity summary
| Approach | Time | Space | Grade |
|---|---|---|---|
| 32-bit scan | O(32) | O(1) | baseline |
| Kernighan | O(#set bits) | O(1) | canonical |
Integer.bitCount | O(1) HW | O(1) | production |
When to use which
- Interview → Kernighan for the "aha".
- Production →
Integer.bitCount. - Popcount many ints → SWAR parallel popcount for batches.
AI Study CompanionBeta
Related problems
- Counting Bits — 0..n via Kernighan DP
- Hamming Distance
- Reverse Bits
Was this page helpful?
📚 Related problems