LeetCode 191 - Number of 1 Bits

LeetCode Problem 191

Difficulty: 🟢 Easy
Topics: Divide and Conquer, Bit Manipulation

Solution

Problem Understanding

The problem asks us to count how many bits are set to 1 in the binary representation of a positive integer n. A set bit is simply a bit whose value is 1.

For example, the number 11 in binary is:

1011

This binary representation contains three 1 bits, so the answer is 3.

The input is a single positive integer. The output should be the total number of 1 bits that appear when the number is written in binary form. This quantity is also known as the Hamming weight.

The constraints tell us that:

1 <= n <= 2^31 - 1

This means the input always fits within a 32-bit signed integer range. The value is guaranteed to be positive, so we do not need to worry about negative numbers or two's complement behavior in this problem.

Even though the constraint size is small enough that several approaches would work efficiently, the problem is designed to test understanding of bit manipulation techniques. A naive approach works, but there is a more elegant and efficient method that removes set bits one at a time.

There are several important edge cases to keep in mind:

• A number with only one set bit, such as 128, should correctly return 1.
• A number where almost every bit is set, such as 2147483645, should still be handled efficiently.
• The smallest valid input, 1, should return 1.
• Powers of two are useful test cases because they contain exactly one set bit.

Approaches

Brute Force Approach

The most straightforward solution is to examine every bit position individually.

We can repeatedly check the least significant bit using:

n & 1

If the result is 1, then the current bit is set. After checking the current bit, we shift the number one position to the right:

n >>= 1

This process continues until the number becomes 0.

This approach is correct because every iteration inspects exactly one bit of the binary representation. Since a 32-bit integer has at most 32 bits, the algorithm finishes after examining all of them.

Although this approach is already fast enough for the given constraints, it still performs work for every bit position, even when many bits are 0.

Optimal Approach

The key observation is that the expression:

n & (n - 1)

removes the lowest set bit from a number.

For example:

n      = 101100
n - 1  = 101011
----------------
AND    = 101000

The rightmost 1 disappears.

This means that instead of checking every bit individually, we can repeatedly remove one set bit at a time. Every iteration corresponds directly to one 1 bit in the number.

Therefore, the number of iterations equals the number of set bits.

This is more efficient because the runtime depends only on how many 1 bits exist, not on the total number of bits.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(32) or O(log n)	O(1)	Checks every bit individually using shifts
Optimal	O(k)	O(1)	Removes one set bit per iteration, where k is the number of set bits

Here, k represents the number of 1 bits in the binary representation.

Algorithm Walkthrough

Optimal Algorithm Using n & (n - 1)

1. Initialize a counter variable to 0.

This variable will store how many set bits we have found. 2. Continue looping while n is greater than 0.

Each iteration removes exactly one set bit from the number. 3. Inside the loop, apply:

n = n & (n - 1)

This operation clears the rightmost set bit in n. 4. Increment the counter.

Since one set bit was removed, we increase the answer by 1. 5. Repeat until n becomes 0.

Once the number becomes zero, there are no remaining set bits. 6. Return the counter.

The counter now equals the total number of 1 bits in the original number.

This algorithm is elegant because it directly connects the loop count to the number of set bits.

Python Solution

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0

        while n > 0:
            n = n & (n - 1)
            count += 1

        return count

The implementation begins by initializing count to 0. This variable keeps track of how many set bits have been removed.

The while loop continues as long as n is not zero. Inside the loop, the expression:

n = n & (n - 1)

removes the lowest set bit from the current number.

After removing a set bit, the code increments count because exactly one 1 bit disappeared.

Eventually, all set bits are removed and n becomes 0. At that point, the loop terminates and the function returns the total count.

This implementation is concise, efficient, and directly reflects the mathematical property of the bit operation.

Go Solution

func hammingWeight(n int) int {
    count := 0

    for n > 0 {
        n = n & (n - 1)
        count++
    }

    return count
}

The Go implementation follows the exact same logic as the Python solution.

The main difference is syntax. Go uses:

count := 0

for variable declaration and uses a for loop instead of Python's while loop.

Since the problem guarantees a positive integer within 32-bit range, integer overflow is not a concern here. The algorithm uses only constant extra memory and modifies the input value directly during computation.

Worked Examples

Example 1

Input

n = 11

Binary representation:

1011

Step-by-Step Trace

Iteration	Current n (Binary)	Operation	Result After Operation	Count
1	1011	1011 & 1010	1010	1
2	1010	1010 & 1001	1000	2
3	1000	1000 & 0111	0000	3

The loop stops because n becomes 0.

Final answer:

3

Example 2

Input

n = 128

Binary representation:

10000000

Step-by-Step Trace

Iteration	Current n (Binary)	Operation	Result After Operation	Count
1	10000000	10000000 & 01111111	00000000	1

The loop terminates immediately after one iteration.

Final answer:

1

Example 3

Input

n = 2147483645

Binary representation:

1111111111111111111111111111101

This number contains thirty 1 bits.

Each iteration removes one set bit, so the loop runs exactly thirty times.

Final answer:

30

Complexity Analysis

Measure	Complexity	Explanation
Time	O(k)	The loop runs once for each set bit
Space	O(1)	Only a few variables are used

The runtime depends on the number of set bits rather than the total number of bits in the integer. This makes the algorithm especially efficient when the number contains relatively few 1 bits.

The space complexity is constant because no additional data structures are allocated.

Edge Cases

Edge Case 1: Smallest Valid Input

Consider:

n = 1

Binary representation:

1

This is the smallest valid input and contains exactly one set bit. The algorithm correctly performs one iteration, removes the bit, and returns 1.

Edge Case 2: Power of Two

Consider:

n = 128

Binary representation:

10000000

Powers of two contain exactly one set bit. This can expose bugs in incorrect implementations that count bit positions rather than actual set bits. The n & (n - 1) operation immediately reduces the value to zero, so the implementation correctly returns 1.

Edge Case 3: All or Nearly All Bits Set

Consider:

n = 2147483645

This number contains many set bits. A naive implementation that manipulates strings or uses unnecessary data structures could become inefficient. The bit manipulation approach handles this efficiently by removing one set bit per iteration.

Edge Case 4: Numbers With Alternating Bits

Consider:

n = 10

Binary representation:

1010

The set bits are separated by zero bits. The algorithm still works correctly because it removes only the rightmost set bit each time, regardless of the surrounding bit pattern.