Math & Bit Manipulation · LC #191
Number of 1 Bits
Count the number of set bits (1s) in a 32-bit unsigned integer - the Hamming weight - using bit-shift or the Brian Kernighan trick.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Return the number of set bits (1s) in the binary representation of the given positive integer.
Sample I/O
Input: n = 11 (binary: 1011) Output: 3 Input: n = 128 (binary: 10000000) Output: 1
Intuition
How to Think About It
Intuition
Each bit is either 0 or 1. Extracting and summing the LSB after each right-shift counts all set bits in O(32) = O(1) time. The Brian Kernighan trick `n &= n-1` clears the lowest set bit each iteration, so the loop runs in exactly popcount iterations - faster when the number is sparse.
Core Concept
Method 1 - bit-shift: loop 32 times, add `n & 1`, then `n >>>= 1` (unsigned). Method 2 - Brian Kernighan: while `n != 0`, do `n &= n-1`, increment count. `n-1` flips the lowest set bit and all trailing zeros, so ANDing clears exactly that bit.
When to use
Counting set bits for flags, permissions bitmasks, parity checks, population count in dense bitmaps, Hamming distance.
When NOT to use
When the language provides a built-in popcount (`Integer.bitCount` in Java, `__builtin_popcount` in C++, `bin(n).count("1")` in Python) - prefer them in production for clarity and potential POPCNT hardware instruction use.
Key Insights
What to Know Cold
- Use unsigned right-shift (`>>>` in Java/TS, `uint32_t` in C++) to avoid sign-extending negative numbers.
- Brian Kernighan: `n & (n-1)` clears the lowest set bit - loop runs exactly popcount(n) times.
- On modern hardware, a single POPCNT x86 instruction computes this in one cycle - always prefer `Integer.bitCount` in Java.
- Hamming weight of `n` equals the number of steps in Kernighan's bit-clearing loop.
- For 64-bit integers, the same approach works - just change the loop bound to 64 or use `long`.
1 example
Worked Examples
Kernighan trick trace on n=12 (1100)
n=12 has 2 set bits
n=12 (1100) → n&=n-1 → 12&11=8 (1000) → 8&7=0; count=2
// Brian Kernighan
function hammingWeightBK(n: number): number {
let count = 0;
while (n !== 0) { n = (n & (n-1)) >>> 0; count++; }
return count;
}
hammingWeightBK(12); // 2Kernighan runs in popcount iterations, not 32 - optimal for sparse bitmasks.