Count Set Bits
Medium · rating 1100 · Math, Bit Manipulation
Read a non-negative integer n. Print the number of 1 bits in its binary representation.
Constraints: 0 ≤ n ≤ 1018
Editorial
Count Set Bits — the Hamming weight or population count — asks how many 1s appear in a number's binary representation, a staple bit-manipulation interview question.
Brian Kernighan's algorithm
The expression n & (n - 1) clears the lowest set bit. Repeat until n is 0, counting iterations, so you loop once per set bit instead of once per bit.
count = 0
while n:
n &= n - 1
count += 1
return countComplexity
Time: O(set bits). Space: O(1). Most languages also expose a built-in popcount (Integer.bitCount, __builtin_popcountll).
Related problems
- Trailing Zero Bits — Easy
- Power of Two — Medium
- Format a Video Length — Medium
- Greatest Common Divisor — Medium
- Single Number — Medium
- Binary to Decimal — Medium