Skip to content

Practice Number of 1 Bits

Read the task, work through the examples, and check your approach against the constraints. Use the original LeetCode task for coding and submissions.

Easy#191
LeetCode Problem

Number of 1 Bits

Problem Statement

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Source: Number of 1 Bits on LeetCode. Use the original task for its coding environment and submissions.

Examples

# Example 1

Input
n = 11
Output
3

# Example 2

Input
n = 128
Output
1

# Example 3

Input
n = 2147483645
Output
30

Constraints

1 <= n <= 2^31 - 1

How to solve Number of 1 Bits

Original notes for interview preparation, written for this problem. Reviewed .

Key insight

Subtracting one from a number flips its lowest set bit to zero and all lower zeros to ones, so AND-ing a number with itself minus one erases exactly one set bit. Repeating until zero counts set bits in as many steps as there are ones.

Why brute force is not enough

Checking each of the 32 bit positions with a mask is already constant time, so the issue is not asymptotic speed but wasted work on sparse inputs and the signed-shift traps it invites. Converting to a binary string and counting characters allocates needlessly.

Approach

  1. Start a counter at zero.
  2. While the number is nonzero, replace it with the bitwise AND of itself and itself minus one. This clears the lowest set bit and nothing else.
  3. Increment the counter after each clearing.
  4. When the number reaches zero, the counter equals the number of set bits.
  5. Alternatively, a byte-wise lookup table or a parallel-count bit trick computes the answer in a fixed handful of operations; mention these if asked about hot loops.

Walkthrough of Example 1

n = 11 → 3

  1. 11 in binary is 1011.
  2. 11 AND 10 (1011 AND 1010) gives 1010, which is 10; counter 1.
  3. 10 AND 9 (1010 AND 1001) gives 1000, which is 8; counter 2.
  4. 8 AND 7 (1000 AND 0111) gives 0; counter 3.
  5. The number is zero, so the answer is 3.

Time and space

Time O(k) · Space O(1). k is the number of set bits, at most 32 for a 32-bit input, so the loop is bounded by a constant; only the counter and the shrinking number are stored.

Interview pitfalls

  • In languages with signed 32-bit integers, a loop over bits using a signed right shift never terminates on negative inputs; use the n AND n minus one trick or an unsigned shift.
  • Looping a fixed 31 times instead of 32 and dropping the top bit.
  • Confusing this with counting zero bits, or counting bits of the absolute value when the input is treated as signed.
  • Incrementing the counter in the wrong place relative to the zero check and reporting one fewer.
  • For the extreme input 2^31 minus 1, which has 31 set bits, verify your mask handles the full width.

Follow-up questions interviewers ask

  • Count set bits for every integer from 0 to n efficiently using a recurrence.
  • Compute the Hamming distance between two integers using this primitive.
  • Why does a number with exactly one set bit indicate a power of two, and how does this trick test that?

Further reading on the technique: Hamming weight

Related LeetCode Problems

Practice more problems similar to Number of 1 Bits.

Review your practice with PhantomCodeAI

After trying the problem yourself, use the app to discuss your approach, complexity, and edge cases.