Number of 1 Bits easy
Description
Write a function that takes an unsigned integer and returns the number of 1 bits it has (also known as the Hamming weight or population count).
Examples
> Case 1:
Input: n = 11 # binary 1011
Output: 3
> Case 2:
Input: n = 128 # binary 10000000
Output: 1
> Case 3:
Input: n = 4294967293 # binary 11111111111111111111111111111101
Output: 31Constraints
- The input is a 32-bit unsigned integer.
Approach 1: Check each bit (naive)
Loop 32 times, ask “is this bit set?” each time.
Time: O(32) = O(1) for fixed-width ints. Always 32 iterations, regardless of input.
Approach 2: Brian Kernighan’s trick
x & (x - 1) clears the lowest set bit of x. So if we keep doing it until x == 0, the number of iterations equals the number of set bits.
Time: O(number of set bits) — faster than the naive version whenever set bits are sparse. For n = 128 (one set bit), this runs once instead of 32 times.
Approach 3: Use the built-in (the real-world answer)
In any modern language, just call the library function. It compiles to a single CPU instruction (POPCNT on x86 / ARM).
In interviews, write Kernighan’s version first (to demonstrate understanding), and mention the built-in as the answer you’d ship.
There’s also a famous SWAR (SIMD Within A Register) trick that counts bits in 12 operations, no loop. It’s the algorithm behind hardware popcount and underpins the older __builtin_popcount software fallback. Not interview-relevant, but a fun rabbit hole if you’re curious.
Analysis
| Approach | Time | Space |
|---|---|---|
| Check each bit | O(32) = O(1) | O(1) |
| Kernighan’s trick | O(set bits) — faster on sparse inputs | O(1) |
| Built-in popcount | O(1) — one CPU instruction | O(1) |