Number of 1 Bits — Solution

Problem

Given an unsigned 32-bit integer, count how many of its bits are set to 1. This count is also called the Hamming weight of the number.

• Input: n = 11
• Output: 3
• Explanation: 11 in binary is 00000000000000000000000000001011, which has three 1-bits.

Counter-example: n = 128 → output 1, because 128 is 10000000 — only one bit set despite being a large number.

Intuition

Every integer is just a sequence of bits, and we want to count the ones that are "on." The key insight for the efficient solution is that n & (n - 1) always turns off exactly the lowest set bit — so instead of checking all 32 positions, we can hop directly from one set bit to the next, finishing in as many steps as there are 1s.

Approach 1 — Bit Shift

Check the lowest bit with n & 1, add it to the count, then shift the number right by one position. Repeat exactly 32 times to cover every bit position.

1. Initialize bit_count = 0.
2. Loop 32 times (one per bit position).
3. Add n & 1 to bit_count — this is 1 if the current lowest bit is set, 0 otherwise.
4. Shift n right by one position to expose the next bit.
5. Return bit_count.

1def hammingWeight(n: int) -> int:
2    bit_count = 0
3    for _ in range(32):
4        bit_count += n & 1       # lowest bit is 1 iff this bit position is set
5        n >>= 1                  # expose the next bit position
6    return bit_count

Time: O(1) — exactly 32 iterations regardless of the input value.

Space: O(1) — only a single counter variable.

Approach 2 — Brian Kernighan's Algorithm

Use the identity n & (n - 1) to clear the lowest set bit in one step, then count how many such operations it takes to reach zero.

Why does n & (n - 1) clear the lowest set bit? Subtracting 1 from n flips the lowest set bit to 0 and flips all bits below it to 1. ANDing with the original n cancels those flipped low bits and preserves everything above.

1. Initialize bit_count = 0.
2. While n != 0: clear the lowest set bit with n = n & (n - 1), increment bit_count.
3. Return bit_count.

1def hammingWeight(n: int) -> int:
2    bit_count = 0
3    while n:
4        n &= n - 1               # drop the lowest set bit; loop runs exactly popcount times
5        bit_count += 1
6    return bit_count

Time: O(1) — loops exactly k times where k is the number of set bits; at most 32 iterations.

Space: O(1) — only a single counter variable.

Complexity Summary

Common Mistakes

• Using >> instead of >>> in Java — Java's >> is an arithmetic right shift that sign-extends, turning a large unsigned number into an infinite loop of 1s. Always use >>> for unsigned right shift.
• Confusing n & (n - 1) with n & ~(n - 1) — n & (n - 1) clears the lowest bit; n & ~(n - 1) isolates it. These are opposites and easy to mix up under pressure.
• Assuming Python handles 32-bit overflow naturally — Python integers are arbitrary precision, so if a negative number is somehow passed, n >>= 1 won't terminate at 32 bits. The loop-32-times approach is safer.
• Counting the bits of the string representation — bin(n).count('1') works in Python but hides the bit manipulation insight entirely; interviewers expect you to work at the bit level.
• Off-by-one on loop bounds — a 32-bit integer has bits 0–31, so the loop should run exactly 32 times, not 31 or 33.

Related Problems

• Counting Bits — extends this problem by computing Hamming weight for every number from 0 to n using DP
• Reverse Bits — also operates bit-by-bit on a 32-bit integer, reversing the bit order
• Single Number — uses XOR bit manipulation to isolate the unique element in an array
• Power of Two — uses n & (n - 1) == 0 to check if exactly one bit is set, a direct application of Brian Kernighan's identity
• Bitwise AND of Numbers Range — requires understanding how bits shift and clear across a range of integers