Number of 1 Bits

Difficulty: Easy Source: NeetCode

Problem

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1: Input: n = 11 Output: 3 Explanation: 11 in binary is 1011, which has three 1s.

Example 2: Input: n = 128 Output: 1 Explanation: 128 in binary is 10000000, which has one 1.

Example 3: Input: n = 2147483645 Output: 30

Constraints:

• 1 <= n <= 2³¹ - 1

Prerequisites

Before attempting this problem, you should be comfortable with:

• Bitwise AND (&) — n & 1 isolates the least significant bit
• Right shift (>>) — n >> 1 divides by 2, dropping the last bit
• Bit masking — using a mask to check or clear individual bits

1. Brute Force

Intuition

The simplest approach: convert the number to its binary string representation in Python, then count the '1' characters. Python’s bin() built-in does the heavy lifting. This is readable but doesn’t teach you anything about how the bits actually work.

Algorithm

1. Convert n to a binary string using bin(n) — this produces something like '0b1011'.
2. Count the occurrences of '1' in that string.
3. Return the count.

Solution

def hammingWeight(n):
    return bin(n).count('1')


print(hammingWeight(11))          # 3  (1011 in binary)
print(hammingWeight(128))         # 1  (10000000 in binary)
print(hammingWeight(2147483645))  # 30

Complexity

• Time: O(log n) — proportional to the number of bits
• Space: O(log n) — the binary string length

2. Bit Shifting

Intuition

Instead of converting to a string, inspect the bits directly. The last bit of any number is n & 1 — AND with 1 isolates the rightmost bit. After reading it, right-shift n by 1 to discard that bit and expose the next one. Repeat until n becomes 0.

For n = 11 = 1011 in binary:

step 1: n & 1 = 1   →  count = 1,  n = 101  (5)
step 2: n & 1 = 1   →  count = 2,  n = 10   (2)
step 3: n & 1 = 0   →  count = 2,  n = 1    (1)
step 4: n & 1 = 1   →  count = 3,  n = 0
done

Algorithm

1. Initialize count = 0.
2. While n > 0:
   • Add n & 1 to count (this is 1 if the last bit is set, 0 otherwise).
   • Right-shift n by 1: n >>= 1.
3. Return count.

Solution

def hammingWeight(n):
    count = 0
    while n > 0:
        count += n & 1
        n >>= 1
    return count


print(hammingWeight(11))          # 3
print(hammingWeight(128))         # 1
print(hammingWeight(2147483645))  # 30

Complexity

• Time: O(log n)
• Space: O(1)

3. Brian Kernighan’s Algorithm

Intuition

Here’s a clever trick: n & (n - 1) clears the lowest set bit of n. That’s it. So instead of checking every bit one by one, we jump directly from one set bit to the next — the loop runs exactly as many times as there are 1-bits.

Why does n & (n - 1) work? Subtracting 1 from n flips the lowest set bit to 0 and turns all lower bits to 1. ANDing with the original n cancels all those lower bits, leaving everything above unchanged and the lowest set bit cleared.

For n = 12 = 1100 in binary:

step 1: n = 1100,  n-1 = 1011,  n & (n-1) = 1000  →  count = 1
step 2: n = 1000,  n-1 = 0111,  n & (n-1) = 0000  →  count = 2
n = 0, done

Two iterations for two set bits — elegant!

Algorithm

1. Initialize count = 0.
2. While n > 0:
   • Increment count.
   • Set n = n & (n - 1) to clear the lowest set bit.
3. Return count.

Solution

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


print(hammingWeight(11))          # 3
print(hammingWeight(128))         # 1
print(hammingWeight(2147483645))  # 30

Complexity

• Time: O(k) where k is the number of set bits — faster than O(log n) when bits are sparse
• Space: O(1)

Common Pitfalls

Using right shift on negative numbers. Python’s >> on negative integers does arithmetic shift (sign-extending), so n may never reach 0 if it starts negative. Always ensure n is non-negative, or mask with 0xFFFFFFFF if handling signed 32-bit input.

Confusing bin() output. bin(11) returns '0b1011', not '1011'. The '0b' prefix contains a '0' but no '1', so .count('1') still works correctly — but be aware the prefix is there.

Thinking Brian Kernighan’s is only a micro-optimization. For numbers with very few set bits across a large bit width, this approach is significantly faster than scanning every bit position one at a time.