Count Set Bits
Maintained by Vikas D, software engineer
Every whole number has a unique representation as a string of binary digits, each one either a 0 or a 1. Your task is to count the digits that are 1 and return that count as a plain integer.
For instance, the number 13 is written as 1101 in binary, which holds three 1 bits, so the answer for 13 is 3. The positions of those 1 bits do not matter, only how many there are.
The input is never negative and fits inside a signed 32-bit range, so you are working with at most 31 meaningful bits. The number 0 has no 1 bits at all, so it returns 0.
The aim is to read off the bit count efficiently. A naive loop over a fixed 32 positions is fine, but a sharper trick lets you do work proportional only to the number of 1 bits that are actually present.
Examples
7 in binary is 111, which has three 1 bits, so the count is 3.
255 in binary is 11111111, eight 1 bits in a row, so the answer is 8.
Zero has no 1 bits in its binary form, so the count is 0.
Constraints
- 0 <= n <= 2^31 - 1
- n is a non-negative integer that fits in a signed 32-bit range
- The answer is the number of 1 bits, between 0 and 31 inclusive
Visible test cases
- countSetBits(0) == 0
- countSetBits(1) == 1
- countSetBits(7) == 3
- countSetBits(255) == 8
- countSetBits(1023) == 10
- countSetBits(2147483647) == 31
Hints
Hint 1
Think about how to inspect one bit at a time. The lowest bit of a number is just n & 1, and shifting right by one drops that bit and brings the next into place.
Hint 2
You can loop while the number is still non-zero, add the lowest bit to a running total, then shift right. That visits every bit position up to the highest 1.
Hint 3
There is a faster pattern: n & (n - 1) clears the lowest set bit. Count how many times you can apply it before the number becomes 0, and that is your answer.
Approaches
Shift and mask
Time O(b) where b is the number of bits, at most 31 here · Space O(1)Read the number bit by bit from the bottom, adding each lowest bit to a total and shifting the number right until it reaches 0.
- Start a counter at 0.
- While the number is not 0, add its lowest bit (number & 1) to the counter.
- Shift the number right by one position to expose the next bit.
- Once the number becomes 0, every bit has been seen, so return the counter.
Brian Kernighan bit clearing
Time O(k) where k is the number of 1 bits · Space O(1)The expression n & (n - 1) always removes the lowest 1 bit, so repeating it until the number is 0 takes exactly as many steps as there are 1 bits.
- Start a counter at 0.
- While the number is not 0, replace it with number & (number - 1), which drops one set bit.
- Increment the counter once for each such step.
- When the number reaches 0, no set bits remain, so return the counter.
Common mistakes
- In JavaScript, bitwise operators treat operands as 32-bit signed integers, which is fine here since the input fits in 31 bits, but be aware that the sign bit can surprise you on larger values.
- Using an arithmetic right shift on a value whose top bit is set can loop forever in some languages because the sign bit keeps refilling; this input range stays non-negative, so a plain shift is safe.
- Forgetting to advance the number inside the loop (no shift and no bit clear) gives an infinite loop, since the stopping condition never changes.
- Counting down a fixed 32 iterations works but always does full work even for small numbers; the bit-clearing trick stops as soon as the 1 bits run out.
Follow-up variations
- How would you count set bits for every integer from 0 up to n, reusing earlier answers instead of recomputing each one?
- What changes if the input can be a 64-bit value or an arbitrary-precision big integer?
- Could you compute the count without any loop, using a parallel bit-counting trick that folds the bits with masks and shifts?
- How is this related to the Hamming distance between two numbers, which counts the differing bits of their XOR?