LeetCode 191: Number of 1 Bits Explained | Java | Bit Manipulation | Blind 75

Learn the intuition behind Number of 1 Bits using visuals, dry runs, multiple approaches, and interview tips

Have you ever wondered how your computer knows exactly how many bits are turned ON inside an integer?

Surprisingly, companies like Google, Microsoft, Amazon, and Meta frequently ask questions based on this simple concept because it tests your understanding of bit manipulation rather than memorization.

In this article, we’ll build the intuition behind the Number of 1 Bits problem from the Blind 75 list.

**What You ‘ ll Learn

**By the end of this article you’ll know

✅ What are Set Bits?

✅ Why this problem is asked

✅ Two optimal approaches

✅ Dry Run

✅ Time Complexity

✅ Interview Tips

✅ Related Problems

Problem Statement:

Given a 32-bit integer,

return the number of bits whose value is 1.

Example

Input

101101

Output

4

Real World Analogy :

Imagine your room has 32 light bulbs.

Some are ON.

Some are OFF.

Your job is simply counting how many lights are ON.

Important Concepts :

0 AND 0 = 0

0 AND 1 = 0

1 AND 1 = 1

Right Shift >>

Unsigned Right Shift >>>

Left Shift <<

Approach 1: Bit-by-Bit Traversal :

The simplest way to solve this problem is to inspect each bit of the given integer one by one.

We repeatedly check whether the least significant bit (LSB) is set (i.e., equals 1). If it is, we increment our counter. Then we shift the number one position to the right to process the next bit.

Since an integer consists of 32 bits, we’ll perform this operation until all bits have been examined.

Algorithm:

Initialize a variable count = 0.

Repeat while the number is not equal to 0:

Check whether the last bit is 1 using (n & 1).

If it is, increment count.

Perform an unsigned right shift (>>>) by one position.

3. Return count.

Java Code:

class Solution {
    public int hammingWeight(int n) {

        int count = 0;

        while (n != 0) {

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

            n >>>= 1;
        }

        return count;
    }
}

⏱️ Complexity Analysis

Time Complexity: O(32)

• A 32-bit integer contains exactly 32 bits.
• In the worst case, we inspect every bit once.

Space Complexity: O(1)

• We use only a few extra variables regardless of the input size.

Can We Do Better?

Yes.

Notice that in the brute-force approach, we examine every bit, even if most of them are 0.

Can we skip those unnecessary checks and process only the set bits?

Yes! That’s exactly what Brian Kernighan’s Algorithm does. It removes one set bit in every iteration, making it much more efficient when the number contains only a few 1s.

Approach 2: Brian Kernighan’s Algorithm (More Efficient):

In the previous approach, we examined every bit of the integer, even if most of them were 0.

Brian Kernighan’s Algorithm takes a smarter approach. Instead of checking each bit individually, it removes one set bit (1) in every iteration.

The key observation is:

***n & (n - 1) always clears the rightmost set bit of n.***

This means the loop runs only as many times as there are set bits, making it more efficient when the number contains only a few 1s.

Algorithm

1. Initialize count = 0.

2. Repeat while n is not equal to 0:

Replace n with n & (n - 1).

Increment count.

3. Return count.

Each iteration removes exactly one set bit from the number.

Java Code :

class Solution {
    public int hammingWeight(int n) {

        int count = 0;

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

        return count;
    }
} 

⏱️ Complexity Analysis

Time Complexity: O(k)

• Where k is the number of set bits (1s) in the integer.
• Each iteration removes exactly one set bit.

Space Complexity: O(1)

• Only a constant amount of extra memory is used.

Why Is This Better?

Compared to the bit-by-bit traversal approach:

• It skips all the 0 bits.
• The loop executes only once for each set bit.
• If the integer has very few 1s`, this approach performs fewer iterations.

For example: 10000000000000000000000000000000

The first approach checks all 32 bits.

Brian Kernighan’s Algorithm finishes in just one iteration, because there is only one set bit.

💡 Key Takeaway

Whenever you need to count the number of set bits in an integer, Brian Kernighan’s Algorithm is one of the most elegant and widely used techniques. It demonstrates a deep understanding of bit manipulation and is a favorite topic in coding interviews at companies like Google, Amazon, and Microsoft.

Conclusion

Although Number of 1 Bits is a simple problem, it teaches one of the most important concepts in bit manipulation.

We explored two approaches:

• Bit-by-Bit Traversal for building intuition.
• Brian Kernighan’s Algorithm for a more efficient solution.

Understanding the reasoning behind these techniques will make many other bit manipulation problems much easier to solve.

This article is part of my Blind 75 in Java series.

➡️ Next: Counting Bits (LeetCode 338)

If you found this article helpful, consider following me for more beginner-friendly Java interview solutions. Happy coding! 🚀