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 ≤ 10¹⁸

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 count

Complexity

Time: O(set bits). Space: O(1). Most languages also expose a built-in popcount (Integer.bitCount, __builtin_popcountll).

Open Count Set Bits in Code Arena →