Number of 1 Bits

Number of 1 Bits

What is this problem about?

The Number of 1 Bits problem asks you to count the number of '1' bits (set bits) in the binary representation of a given unsigned integer. Also known as the "Hamming weight" or "popcount," this is a fundamental bit manipulation operation. The Number of 1 Bits coding problem has several elegant solutions with different trade-offs.

Why is this asked in interviews?

Apple, Cisco, Microsoft, Meta, Nvidia, Google, Bloomberg, and Adobe ask this because counting set bits is a fundamental operation in computer science — used in checksum computation, cryptography, and low-level systems programming. The divide and conquer and bit manipulation interview pattern is directly tested, and knowing multiple approaches demonstrates depth.

Algorithmic pattern used

Multiple approaches:

• Brian Kernighan's trick: n = n & (n-1) removes the lowest set bit. Count iterations until n=0. O(number of set bits).
• Lookup table: Precompute counts for 8-bit chunks, sum four chunks. O(1).
• Built-in: bin(n).count('1') or __builtin_popcount(n).

Brian Kernighan's: each n & (n-1) clears exactly one set bit (the rightmost). Count iterations.

Example explanation

n=11 (binary: 1011). Apply Kernighan's:

• 11 & 10 = 1010 (10). Count=1.
• 10 & 9 = 1000 (8). Count=2.
• 8 & 7 = 0000. Count=3. Result: 3 set bits.

Common mistakes candidates make

• Repeatedly shifting right and checking the LSB (correct but slower if many leading zeros).
• Not handling the case where n has all 32 bits set (large unsigned integers).
• Using signed right shift (arithmetic shift) which propagates sign bit.
• Off-by-one in the count initialization.

Interview preparation tip

Know Brian Kernighan's trick cold: while n: count++; n &= n-1. This is the most elegant O(popcount) solution and is guaranteed to impress interviewers. The insight: n & (n-1) clears the lowest set bit because subtracting 1 from n flips the lowest 1-bit and all bits below it, so AND eliminates them. This trick generalizes: counting set bits, checking if n is a power of 2 (n & (n-1) == 0), and removing the lowest set bit iteratively.