Number of 1 Bits

Master this topic with zero to advance depth.

Number of 1 Bits

Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).

Easy

Examples

Input: n = 11
Output: 3
11 in binary is 1011, which has three '1' bits.

Approach 1

Level I: Brute Force (Iterate all 32 bits)

Intuition

The most straightforward way is to check each of the 32 bits one by one. We can do this by shifting the number right and checking the last bit using bitwise AND with 1.

Thought Process

Initialize a counter count = 0.
Loop 32 times (for a 32-bit integer):
- Check if the last bit is 1: (n & 1) == 1.
- If yes, increment count.
- Right shift $n$ by 1: n >>= 1.
Return count.

Pattern: Bitwise Iteration

⏱ O(1) - Always 32 iterations for a 32-bit integer.💾 O(1) - No extra space used.

java

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) != 0) count++;
            n >>= 1;
        }
        return count;
    }
}

Approach 2

Level II: Standard Library / Built-in

Intuition

Most modern programming languages provide highly optimized built-in functions to count set bits, often utilizing specific CPU instructions like POPCNT.

⏱ $O(1)$ - Usually a few machine instructions.💾 $O(1)$

java

public class Solution {
    public int hammingWeight(int n) {
        return Integer.bitCount(n);
    }
}

Approach 3

Level III: Optimal (Brian Kernighan's Algorithm)

Intuition

Instead of checking every bit, we can jump directly between set bits. The operation n & (n - 1) always clears the least significant set bit of $n$ .

Thought Process

While $n \neq 0$ $n \neq = 0$ :
- Set $n = n \text{ & } (n - 1)$ . This removes exactly one '1' bit.
- Increment count.
The number of iterations equals the number of set bits, which is more efficient for sparse numbers.

Pattern: Bit Manipulation Magic

⏱ O(1) - Specifically $O(\text{number of set bits})$, max 32 iterations.💾 O(1) - Constant space.

Detailed Dry Run

n = 12 (binary 1100)

Iteration	n (Before)	n-1	n & (n-1)	count
1	1100 (12)	1011 (11)	1000 (8)	1
2	1000 (8)	0111 (7)	0000 (0)	2
Result: 2

java

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);
            count++;
        }
        return count;
    }
}

← Previous QuestionBitwise AND of Numbers Range

Next Question →Reverse Bits

Found an issue or have a suggestion?

Help us improve! Report bugs or suggest new features on our Telegram group.