AlgoViz
HomeBit Manipulation

Count the Number of Set Bits

Easy

Brian Kernighan: clear the lowest set bit

Problem

Count the number of 1-bits in the binary representation of a number (Hamming weight).

In simple words

Repeatedly clear the lowest set bit (n & n-1) and count how many times until zero.

The idea

`n & (n - 1)` removes the lowest set bit, so counting how many times you can do that before reaching zero counts the ones. It loops once per set bit rather than once per bit position, which is much faster on sparse numbers.

The trick

  • Loops set-bit times, not 32 times.
  • Built-ins do it in one instruction: __builtin_popcount, Integer.bitCount, bin(x).count('1').
1
0
1
1
0
1
0
0
0
1
2
3
4
5
6
7
n180
count0

Step 1 of 6. Trick: n & (n − 1) erases the lowest set 1-bit. Count how many times we can do that. Values: 1, 0, 1, 1, 0, 1, 0, 0. n 180, count 0.

1/6
Optimal
timeO(bits set)spaceO(1)

One iteration per set bit.

1// clear the lowest set bit each step2let count = 0;3while (n !== 0) {4  n &= n - 1;5  count++;6}7return count;

Input

array
[1, 0, 1, 1, 0, 1, 0, 0]

Memory

n
180
count
0

Output

count
0
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
n = 5
Output:
2
Explanation:
5 is 101 → two 1s.

Example 2

Input:
n = 7
Output:
3
Explanation:
7 is 111 → three 1s.

Example 3

Input:
n = 16
Output:
1
Explanation:
16 is 10000 → one 1.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.