Number of 1 Bits
Problem
Write a function that takes an unsigned integer and returns the number of 1 bits it has (the Hamming weight).
Examples
Example 1
Input: n = 11 (binary 1011)
Output: 3
Explanation: Three set bits.
Example 2
Input: n = 128 (binary 10000000)
Output: 1
Explanation: One set bit.
Constraints
- •
The input is a 32-bit unsigned integer
Hints
Hint 1
The brute force checks all 32 bit positions individually (n & 1, then n >>>= 1, repeated 32 times) — correct, but does the same fixed amount of work regardless of how many bits are actually set.
Hint 2
n & (n-1) clears exactly the LOWEST set bit of n — what does repeating this until n becomes 0 tell you?
Hint 3
The number of iterations until n reaches 0 via n &= (n-1) is exactly the number of set bits — no need to check all 32 positions if only a few are set.
Solutions
public int hammingWeightBruteForce(int n) {
int count = 0;
for (int i = 0; i < 32; i++) {
if ((n & (1 << i)) != 0) count++;
}
return count;
}Time: O(32) = O(1), but always the full 32 checks · Space: O(1)