Number of 1 Bits

The problem

You are given a positive whole number number. Write it in binary and count how many of its bits are 1. Return that count.

Example 1

Input: number = 180

Output: 4

180 in binary is 10110100. It has four 1 bits.

number = 180

10110100

1 bits

4

Example 2

Input: number = 1024

Output: 1

1024 is 2¹⁰, so its binary form is a 1 followed by ten 0s.

Example 3

Input: number = 2147483647

Output: 31

This is 2³¹ − 1, the largest value allowed. All 31 of its low bits are 1.

Constraints

• 1 ≤ number ≤ 2³¹ − 1
• Below, b is the number of bits in the type (32), and k is the number of 1 bits in number.

Clarifying questions

Do we count the bits of the decimal digits?

No. We count the 1s in the binary form of the whole number.

Can number be negative?

No, number is at least 1. Some versions pass a 32-bit pattern that can look negative in Java. Using the unsigned shift (>>>) handles that too.

Can we use a built-in like bin(number).count("1") or Integer.bitCount?

In real code, yes. In an interview, show the bit trick, then mention the built-in.

Spot the pattern

The question is about the bits of a number, not its value. That points to bit manipulation: number & 1 reads the lowest bit, number >> 1 drops it, and number & (number − 1) removes the lowest 1 bit in one step.

Solutions

Check every bitO(b)Drop the lowest 1O(k)

Show all

This problem has two approaches. Both use O(1) memory, and the second only skips the 0 bits.

Check every bit O(b)

The idea

Read the lowest bit with number & 1 and add it to the count. Then shift number right by one, so the next bit becomes the lowest. Stop when number is 0, because no 1 bits are left.

It is correct and simple, but it spends a run on every 0 bit below the highest 1.

Walkthrough

number

10110100

count

0

1. count = 0
2. while number:
3. count += number & 1
4. number >>= 1
5. return count

number = 180, which is 10110100 in binary. Look at the lowest bit, then shift number right by one, until number is 0.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Check every bit: read the lowest bit, then shift it away, until number is 0.
    // One run per bit up to the highest 1: O(b) time, O(1) memory.
    public int hammingWeight(int number) {
        int count = 0;
        while (number != 0) {
            count += number & 1;
            // >>> shifts in 0s, so a pattern with the top bit set still reaches 0.
            number >>>= 1;
        }
        return count;
    }
}

Big O

Time O(b)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines read one bit and shift number. That is 1 step. They sit inside one loop.

   1. count = 0
   2. while number:
   3. count += number & 1
   4. number >>= 1
   5. return count

2. 2 Count the runs on Example 1

   180 is 10110100, so its highest 1 is the 8th bit from the right. The loop runs once per bit up to there, 0s included.

   8 runs.

   run	1	2	3	4	5	6	7	8
   lowest bit	0	0	1	0	1	1	0	1

   total

   8 runs

3. 3 Write the count for any n

   The loop runs once for each bit up to the highest 1. The worst case is a 1 in the top bit:

   at most b runs, and b = 32

   Check it with Example 3: 2³¹ − 1 has its highest 1 at bit 31, so 31 runs.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is b. Since b is fixed at 32, you can also call it O(1). Saying O(b) shows how it would grow with a wider type.

   So the time is O(b).

5. S Space: count the extra memory the same way

   The code keeps count and number. The space is O(1).

   countnumber

Drop the lowest 1 O(k)

The idea

Subtracting 1 from number turns its lowest 1 bit into 0 and every 0 below it into 1. The bits above it do not change. So number & (number − 1) is number with its lowest 1 bit removed.

Repeat that until number is 0, and count the runs. Each run removes exactly one 1 bit, so the count is the answer.

Walkthrough

number

10110100

count

0

1. count = 0
2. while number:
3. number &= number - 1
4. count += 1
5. return count

number = 10110100. Each run wipes out the lowest 1 bit, so the loop runs once per 1 bit.

← BackStep →Play1 / 10

Code

JSolution.javaPysolution.pyC#Solution.csGosolution.goTSsolution.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

class Solution {
    // Drop the lowest 1: number & (number - 1) clears the lowest 1 bit.
    // One run per 1 bit: O(k) time, O(1) memory.
    public int hammingWeight(int number) {
        int count = 0;
        while (number != 0) {
            // number - 1 flips the lowest 1 and the 0s below it, so & keeps only the bits above it.
            number &= number - 1;
            count++;
        }
        return count;
    }
}

Big O

Time O(k)Space O(1)Here is how we get these from the code, in four steps.

1. 1 Find the work that repeats

   The lit lines do one subtract, one & and one add. That is 1 step. They sit inside one loop.

   1. count = 0
   2. while number:
   3. number &= number - 1
   4. count += 1
   5. return count

2. 2 Count the runs on Example 1

   180 has four 1 bits. Each run removes one, and the table shows number after each run.

   4 runs, against 8 for checking every bit.

   run	1	2	3	4
   number after	10110000	10100000	10000000	00000000

   total

   4 runs

3. 3 Write the count for any n

   Each run removes exactly one 1 bit, and the loop stops when none are left:

   k runs, where k ≤ b

   Check it with Example 2: 1024 has one 1 bit, so 1 run. Checking every bit would take 11.

4. 4 Keep only the part that grows fastest

   There is nothing to drop. The count is k. In the worst case, all bits are 1 and k = b, so the worst case matches the first approach. It wins on numbers with few 1 bits.

   So the time is O(k).

5. S Space: count the extra memory the same way

   The code keeps count and number. The space is O(1).

   countnumber

Common mistake

Shifting with >> in Java

If the input is a 32-bit pattern with the top bit set, Java sees a negative int. number >> 1 copies the sign bit in from the left, so number never reaches 0 and the loop never ends. Use number >>>= 1, which shifts in 0s. The number & (number − 1) version does not have this problem.

Tested at the limits

2,000 random numbers from 1 to 2³¹ − 1, with many powers of two and runs of ones. Check every bit and drop the lowest 1 gave the same answer every time, and matched a count of the 1s in the binary text.

Largest inputs	Result
2³¹ − 1 (the largest allowed), all 31 bits set, the most work for both. Drop the lowest 1.	Under 0.001 s, and under 0.001 MB of extra memory: just count and number.
Every power of two and every all-ones number up to 31 bits. Both approaches.	The right count for all 62 numbers.