What is the brute force approach and complexity for Number of 1 Bits?

Check each of the 32 bit positions and count the 1s with time complexity O(32) and space complexity O(1).

What is the optimal approach and complexity for Number of 1 Bits?

n & (n − 1) removes the lowest 1 bit; count the removals until n is 0 with optimal time complexity O(k) and space complexity O(1).

How do you identify the pattern for Number of 1 Bits?

Look for key signals in the prompt: "number of set bits" indicates The answer is a count of 1 bits, so each 1 bit must be counted once.; "binary representation" indicates Work on the bits directly with `&` and shifts, not on the decimal digits.; "positive integer, up to 2^31 − 1" indicates The width is fixed at 32 bits, so the bit tricks never run past the end..

Number of 1 Bits

Easy·LeetCode #191Basic Anchor

LeetCode

Jump:

30-Second Mental ModelBit Counting — clear the lowest set bit

Complexity:O(32)→O(k)

Key Insight

n & (n − 1) clears the lowest set bit of n and keeps every other bit. So each loop pass removes exactly one 1 bit and skips the zeros entirely. The number of passes is the number of 1 bits.

Core Validity Invariant

The loop is correct because each pass removes exactly one 1 bit and no other bit changes. So when n reaches 0, the count equals the number of 1 bits that were in the original n.

Problem

Given a positive integer n, count how many of its bits are 1 when it is written in binary. This count is also called the Hamming weight.

Follow-up: if this function is called many times, how would you speed it up?

Input

A positive integer n.

Output

The number of 1 bits in the binary form of n.

Example 1

Input: n = 11

Output: 3

11 is 1011 in binary. It has three 1 bits.

Example 2

Input: n = 128

Output: 1

128 is 10000000. Only one bit is set.

Example 3

Input: n = 2147483645

Output: 30

The binary form is 31 digits long, and only one of them (the second from the end) is a 0. So there are 30 ones.

Constraints

• 1 ≤ n ≤ 2^31 − 1

First, think yourself

Before opening any solution, try to answer these on paper. Use hints only when stuck — each hint is counted.

1.
To count the 1 bits, how can I look at one bit at a time?
2.
Which operation tests the lowest bit of a number? Which one removes it?
3.
Does the loop need 32 steps every time, or can it depend on the number itself?
4.
Does a number with only two 1 bits need to look at all of its 0 bits?
5.
What does n − 1 change in the bits of n? Try it on a small number first.

Brute force approach

Idea

Look at each of the 32 bit positions in turn. For position i, the bit is (n >> i) & 1. Add one to the count whenever it is 1.

Thinking process

1
The answer is a count of 1 bits, so the simplest plan is to look at every bit once.
2
An int has 32 bit positions, numbered 0 to 31. Shift n right by i and keep only the lowest bit with & 1.
3
Example with n = 12 = 1100: bits 2 and 3 are 1, and bits 0 and 1 are 0. Bits 4 to 31 are all 0. The count is 2.
4
The loop still checks positions 4 to 31 even though they are all zero. That is the waste.

Visual

Each step tests one bit with (n >> i) & 1. Green = a 1 bit that is counted; the zeros still cost a step.

Check every bit positionn = 182 (shown as 8 bits: 10110110)step 1/9

▲i

Check

i: 0
(n >> i) & 1: 0
count: 0

Bit 0 is 0 → nothing to add

Test bit 0 of 182: (n >> 0) & 1 = 0. A zero adds nothing, but it still cost a check.

Code & Implementation

brute.cpp

class Solution {
public:
    int hammingWeight(int n) {
        uint32_t x = (uint32_t)n;   // unsigned, so every shift is a plain bit shift

        // Look at all 32 bit positions, one at a time.
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((x >> i) & 1) count++;
        }
        return count;
    }
};

Complexity

Time O(32)Space O(1)

An int has exactly 32 bit positions, so this always does 32 checks, even for n = 1. It is constant time, but it spends the same effort on the zero bits as on the one bits.

Optimized approach

Idea

n & (n − 1) clears the lowest set bit of n and keeps every other bit. So each loop pass removes exactly one 1 bit and skips the zeros entirely. The number of passes is the number of 1 bits.

Start from brute force

The brute force checks all 32 positions. Most of them are 0 for a typical number, so most checks add nothing.

Find the repeated work

Every 0 bit is looked at and thrown away. The number of checks depends on the width of int, not on how many 1 bits there are.

Define the state — what variables do I need?

n: The number we still have to count. Each loop pass removes its lowest 1 bit.
count: How many 1 bits have been removed so far.

Define validity

The loop is correct because each pass removes exactly one 1 bit and no other bit changes. So when n reaches 0, the count equals the number of 1 bits that were in the original n.

Define the transitions — when does each pointer move, and why is it safe?

n is not 0 (at least one 1 bit is left)

n = n & (n − 1); count++

n − 1 turns the lowest 1 bit into 0 and turns the zeros below it into 1s. The & keeps the bits above that position, which are the same in both numbers, and clears the rest.

n is 0

return count

No 1 bits are left, so there is nothing more to remove.

What does the current window add to the answer?

Each pass adds one to count for the 1 bit it removed. So count is the number of 1 bits in the original n.

Code & Implementation

optimal.cpp

class Solution {
public:
    int hammingWeight(int n) {
        uint32_t x = (uint32_t)n;

        // x & (x - 1) clears the lowest set bit. Repeat until no set bit is left.
        int count = 0;
        while (x != 0) {
            x &= x - 1;
            count++;
        }
        return count;
    }
};

Complexity

Time O(k)Space O(1)

k is the number of 1 bits in n. The loop runs exactly k times and never looks at a 0 bit on its own. Each pass removes one 1 bit, so no method can do fewer than k passes with this idea. Table lookups on bytes (the usual answer to the follow-up) only make each step faster by a constant factor.

Why does this algorithm work?

Dry run

All approaches compared

Approach	Idea	Time	Space
Brute Force	Check each of the 32 bit positions and count the 1s	O(32)	O(1)
Optimal	n & (n − 1) removes the lowest 1 bit; count the removals until n is 0	O(k)	O(1)

Why does this belong to this pattern?

Clues in the problem statement

“number of set bits”The answer is a count of 1 bits, so each 1 bit must be counted once.
“binary representation”Work on the bits directly with `&` and shifts, not on the decimal digits.
“positive integer, up to 2^31 − 1”The width is fixed at 32 bits, so the bit tricks never run past the end.

count the 1 bits+n & (n − 1) clears the lowest 1 bit+loop until n is 0→Bit Counting — clear the lowest set bit

This is the anchor for the counting sub-pattern. The key move is n & (n − 1): it removes the lowest 1 bit in one step. Do not confuse it with n & 1, which only tests the lowest bit. Power of Two uses the same move to check for a single 1 bit.

Don't make this mistake

Confusing n & 1 with n & (n − 1)

✗ while (n != 0) { count += n & 1; // tests the lowest bit n = n & (n - 1); // removes the lowest 1 bit }

✓ while (n != 0) { n = n & (n - 1); count++; }

This is the pattern-confusion trap. n & 1 only looks at the bottom bit, and the wrong loop checks it before removing a bit. On n = 182 = 10110110 the bottom bit is 0, and clearing a 1 bit never makes it 1. So the wrong loop only ever sees 0s and returns 0, not 5.

Typo: n + 1 instead of n − 1

✗ n = n & (n + 1);

✓ n = n & (n - 1);

n + 1 does not clear the lowest 1 bit. For n = 182, 182 & 183 is still 182, so n never changes and the loop never ends.

Shifting right instead of removing the lowest bit, with a negative n

✗ while (n != 0) { count += n & 1; n >>= 1; }

✓ uint32_t x = (uint32_t)n; while (x != 0) { x &= x - 1; count++; }

This works for positive n, but it always takes one step per bit position. It is also a trap for negative numbers: >> on a signed int copies the sign bit down, so -8 >> 1 is -4, then -2, then -1, and it never reaches 0. LeetCode's constraints say n is positive, but the unsigned copy avoids the trap.

Want to implement this?

Write it yourself on LeetCode, then come back and compare your code with the solutions above.

Open coding workspace

How did it go?

Beyond The LeetCode Problem

How this concept connects to System Design & C++ Systems

Bridge DSA with production engineering

Top engineering interviews test whether you understand how algorithms like Bit Manipulation translate into production architectures and low-level memory mechanics.

LLD Architecture