Skip to main content
CodePeetCodePeet
CodePeet 250

Number of 1 Bits

EASYProblemSolveExternal Links

Description

Given a positive integer n, write a function that returns the number of set bits (1-bits) in its binary representation.

This count is also known as the Hamming weight — a measure of how many bits are "on" when the number is expressed in base 2.

For example, the number 11 in binary is 1011, which has three 1-bits. The number 128 in binary is 10000000, which has exactly one 1-bit.

Examples

Example 1

Input: n = 11

Output: 3

Explanation: The binary representation of 11 is 1011. Reading from right to left: the 1s place is 1, the 2s place is 1, the 4s place is 0, and the 8s place is 1. There are three 1-bits in total.

Example 2

Input: n = 128

Output: 1

Explanation: The binary representation of 128 is 10000000. Only the 128s place (bit 7) is set. All other bits are 0. So there is exactly one 1-bit.

Example 3

Input: n = 2147483645

Output: 30

Explanation: The binary representation of 2147483645 is 1111111111111111111111111111101 (31 bits). Every bit is 1 except the second bit from the right. That gives us 30 set bits out of 31.

Constraints

  • 1 ≤ n ≤ 2³¹ - 1

Editorial

Brute Force

Intuition

The most straightforward way to count 1-bits is to inspect every single bit position in the number, one by one.

A 32-bit integer has 32 bit positions (numbered 0 through 31). We can check each position by looking at the last bit of the number (using a bitwise AND with 1), counting it if it's 1, and then shifting the number one position to the right to bring the next bit into the last position.

Think of it like reading a binary number digit by digit from right to left. At each step, you ask: "Is this digit a 1?" If yes, you add one to your tally. Then you cross out that digit and move to the next one. You keep going until you've checked all 32 digits.

This always examines exactly 32 bits regardless of how many are set — even if only one bit is 1, you still check all 32 positions.

Step-by-Step Explanation

Let's trace through with n = 11 (binary: 1011):

Step 1: Initialize count = 0. n = 11 (binary: 1011).

Step 2: Check last bit: 11 & 1 = 1. It's a 1-bit! count = 1. Shift right: n = 11 >> 1 = 5 (binary: 101).

Step 3: Check last bit: 5 & 1 = 1. Another 1-bit! count = 2. Shift right: n = 5 >> 1 = 2 (binary: 10).

Step 4: Check last bit: 2 & 1 = 0. This bit is 0, skip. count stays 2. Shift right: n = 2 >> 1 = 1 (binary: 1).

Step 5: Check last bit: 1 & 1 = 1. A 1-bit! count = 3. Shift right: n = 1 >> 1 = 0 (binary: 0).

Steps 6-33: n is 0 for the remaining 28 iterations. Every check gives 0. count stays 3.

Result: count = 3.

Bit-by-Bit Inspection — Checking All 32 Positions — Watch how we examine each bit from right to left using AND with 1 and right shift. We show only the significant bits of n = 11 (binary 1011) as the number shrinks with each shift.

Algorithm

  1. Initialize count = 0
  2. Loop 32 times (once per bit position):
    a. If n & 1 == 1, increment count
    b. Right shift n by 1: n = n >> 1
  3. Return count

Code

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (n & 1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
};
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        for _ in range(32):
            if n & 1:
                count += 1
            n >>= 1
        return count
class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                count++;
            }
            n >>= 1;
        }
        return count;
    }
}

Complexity Analysis

Time Complexity: O(32) = O(1)

We always loop exactly 32 times, once for each bit in a 32-bit integer. Each iteration performs a constant-time AND and shift. Since the loop count is fixed and does not depend on the input size, this is O(1).

Space Complexity: O(1)

We use only a single counter variable. No additional data structures are needed.

Why This Approach Is Not Efficient

While the brute force is already O(1) in terms of time (fixed 32 iterations), it does unnecessary work. For a number like 128 (binary 10000000), there is only a single 1-bit, yet we still check all 32 positions. For 2147483645 with 30 set bits, checking all 32 is nearly unavoidable — but for sparse numbers, we waste 31 out of 32 iterations.

The key question is: can we skip the 0-bits entirely and only visit the 1-bits?

The answer is yes. There is a clever bit manipulation trick — Brian Kernighan's algorithm — that turns off exactly one set bit per iteration. Instead of always looping 32 times, it loops exactly k times, where k is the number of 1-bits. For sparse numbers, this is a significant improvement.

The trick relies on the operation n & (n - 1), which clears the lowest set bit of n. Subtracting 1 from a number flips all bits from the lowest 1-bit downward, and ANDing with the original cancels that lowest 1-bit while preserving everything above it.

Optimal Approach - Brian Kernighan's Algorithm

Intuition

Brian Kernighan's algorithm is based on a beautiful observation about binary numbers:

When you subtract 1 from a number, the lowest set bit (the rightmost 1) becomes 0, and all the bits below it flip from 0 to 1. For example:

  • 12 in binary is 1100. Subtract 1 → 1011. Notice the lowest 1-bit (bit 2) turned off, and bits below it flipped.
  • 10 in binary is 1010. Subtract 1 → 1001. The lowest 1-bit (bit 1) turned off.

Now, if we AND the original number with (number - 1), the lowest set bit is cleared, and everything else stays the same:

  • 12 & 11 = 1100 & 1011 = 1000. The lowest 1-bit was removed.
  • 10 & 9 = 1010 & 1001 = 1000. Again, one 1-bit removed.

Each time we perform n = n & (n - 1), exactly one set bit disappears. We count how many times we can do this before n becomes 0 — and that count is the number of 1-bits.

Think of it like blowing out candles on a birthday cake. Each operation extinguishes exactly one candle (the lowest-positioned one). You count how many breaths it takes to extinguish all candles.

Step-by-Step Explanation

Let's trace through with n = 11 (binary: 1011):

Step 1: Initialize count = 0. n = 11 (binary: 1011). n is not 0, so enter the loop.

Step 2: Compute n - 1 = 10 (binary: 1010). The lowest 1-bit (bit 0) and everything below it flipped.

Step 3: Compute n & (n - 1) = 1011 & 1010 = 1010 = 10. The lowest 1-bit is now cleared. n = 10. count = 1.

Step 4: n = 10 (binary: 1010). Compute n - 1 = 9 (binary: 1001). The lowest 1-bit (bit 1) flipped.

Step 5: Compute n & (n - 1) = 1010 & 1001 = 1000 = 8. Another 1-bit cleared. n = 8. count = 2.

Step 6: n = 8 (binary: 1000). Compute n - 1 = 7 (binary: 0111). The lowest (and only) 1-bit flipped.

Step 7: Compute n & (n - 1) = 1000 & 0111 = 0000 = 0. The last 1-bit is cleared. n = 0. count = 3.

Step 8: n = 0. Exit loop.

Result: count = 3. We looped exactly 3 times — once per set bit.

Brian Kernighan's Algorithm — Clearing Lowest Set Bit — Watch how n & (n-1) eliminates exactly one 1-bit per iteration, counting set bits in just k steps where k is the number of 1-bits.

Algorithm

  1. Initialize count = 0
  2. While n is not 0:
    a. Perform n = n & (n - 1) — this clears the lowest set bit
    b. Increment count
  3. Return count

Code

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n) {
            n = n & (n - 1);
            count++;
        }
        return count;
    }
};
class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n = n & (n - 1)
            count += 1
        return count
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 in n

The loop runs exactly k times — once for each 1-bit. Each iteration performs one subtraction and one AND, both O(1). In the worst case (all 31 bits set), k = 31, so this is O(31) = O(1). But in practice, for sparse numbers like powers of 2, the loop runs only once.

Space Complexity: O(1)

We use only a single counter variable. No additional space is required.

Compared to the brute force (always 32 iterations), this approach adapts to the input: fewer set bits means fewer iterations. For a number like 128 (one set bit), brute force does 32 iterations while Brian Kernighan's does just 1.