Number of 1 Bits

For Number of 1 Bits, the key idea is to count set bits without checking every decimal value or rebuilding the number. The strongest interview answer uses bit manipulation: repeatedly apply n &= n - 1 to remove the lowest set bit, and count how many removals happen. That directly matches the Hamming weight definition and avoids the common mistake of mixing decimal digits with binary bits.

Problem Statement

You are given a positive integer n and need to return how many 1s appear in its binary representation. This count is called the Hamming weight, so the task is not about the decimal digits of n, but about the bits that are turned on.

For example, n = 11 becomes binary 1011, which contains three set bits, so the answer is 3. Likewise, 128 has only one set bit because its binary form is 10000000. The main interview challenge is choosing a bit-based counting strategy that stays correct across sparse and dense binary patterns.

Examples

Example 1

Input: n = 11

Output: 3

The input binary string 1011 has a total of three set bits.

Example 2

Input: n = 128

Output: 1

The input binary string 10000000 has a total of one set bit.

Example 3

Input: n = 2147483645

Output: 30

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints

• 1 <= n <= 231 - 1

Solution Approach

Start with direct bit inspection

A straightforward way to solve Number of 1 Bits is to inspect the least significant bit, add it to the answer, then shift the number right until nothing remains. This works because each step exposes one binary position, making the count explicit. It is easy to explain, but it touches every bit position, even when the number contains very few 1s.

Use low-bit clearing for the best practical solution

The strongest approach for this problem is repeated low-bit removal: each time you do n &= n - 1, the rightmost set bit disappears. Count how many times that operation runs before n becomes 0. For n = 11, binary 1011 becomes 1010, then 1000, then 0000, so the answer is 3. This is the cleanest bit manipulation pattern because the loop runs once per set bit, not once per bit position.

Connect the divide and conquer angle carefully

If an interviewer mentions divide and conquer, frame the binary representation as something you can break apart by bit structure instead of decimal arithmetic. You can view low-bit clearing as reducing the problem into a smaller subproblem after removing one confirmed 1, or describe recursive splitting over bit ranges, but in code the bit manipulation version is usually preferred. The important trade-off is clarity versus overengineering: for LeetCode 191, recursive splitting is possible, but low-bit clearing is simpler and faster to execute under pressure.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The right-shift method runs in O(k) time where k is the number of processed bit positions, with O(1) extra space. The n &= n - 1 method runs in O(s) time where s is the number of set bits, also with O(1) extra space. That makes low-bit clearing especially good when the binary representation is sparse, because it skips zero bits entirely.

What Interviewers Usually Probe

• The interviewer wants bit-level reasoning, not string conversion or decimal digit counting.
• A follow-up about optimization usually points toward n &= n - 1 instead of checking every position.
• If divide and conquer appears in the topic list, explain how each bit-clearing step shrinks the remaining subproblem.

Common Pitfalls or Variants

Common pitfalls

• Counting decimal 1s in the number instead of set bits in the binary representation.
• Using string conversion first, which hides the bit manipulation pattern this problem is testing.
• Forgetting that n &= n - 1 removes exactly one set bit, not one arbitrary bit.

Follow-up variants

• Return whether the number has exactly one set bit, which turns the problem into a power-of-two style check.
• Count set bits for every number from 0 to n, which leads to a dynamic programming bit-count array.
• Handle negative values in a fixed-width language, where unsigned interpretation matters for bit operations.

FAQ

What is the fastest way to solve Number of 1 Bits?

The best interview answer is usually to use n &= n - 1 in a loop. Each iteration removes one set bit, so the number of loop runs equals the Hamming weight.

Why does n &= n - 1 work for this problem?

Subtracting 1 flips the lowest set bit to 0 and turns any trailing 0 pattern below it appropriately. ANDing that result with the original number clears exactly the rightmost 1, which makes counting removals equal counting set bits.

Should I use divide and conquer for Number of 1 Bits?

You can mention a divide and conquer interpretation, but the practical coded solution is bit manipulation. For LeetCode 191, recursive splitting is usually less direct than clearing one set bit at a time.

Is shifting right also acceptable?

Yes. Repeatedly checking n & 1 and shifting right is correct and easy to explain, but it may examine more positions than necessary compared with low-bit clearing.

What is the main failure mode in this bit manipulation pattern?

The most common failure is understanding the operation too vaguely and not knowing what bit disappears each round. In this problem, the disappearing bit is always the lowest set bit, and that exact property is why the count stays correct.