Maintained by Vikas Dulgunde, 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.
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.
Visible test cases
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.
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.
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.
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.
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.