Number of 1 Bits

You are given a non-negative integer n that fits in 32 bits as an unsigned value (so it is between 0 and 2³² − 1). Return how many bits are set to 1 in its binary representation. This count is also known as the number's Hamming weight or population count.

For example, 13 is 1101 in binary, which contains three ones.

Solve it with bit operations rather than converting the number to a string or calling a built-in popcount function.

Example 1

Example 2

Example 3

Constraints

• 0 <= n <= 232 - 1

Pattern Path · Math, Bits & Strings · problem 30 of 169

Start simple

Check each of the 32 bit positions with a mask or shift: O(32) operations regardless of how many bits are set.

The key idea

The key identity is that n & (n - 1) removes exactly the lowest 1 bit of n. Subtracting 1 from a binary number turns its lowest 1 into 0 and every 0 below it into 1, leaving higher bits unchanged. For example n = 10100 gives n - 1 = 10011. AND-ing the two keeps the shared high bits and zeroes out everything from the lowest set bit downwards: 10000.

So repeatedly replace n with n & (n - 1) and count the steps until n is 0. Each step deletes one set bit, so the loop runs exactly as many times as there are ones. That is never more than 32, and much less for sparse numbers. This is known as Brian Kernighan's trick.

In JavaScript, bitwise operators work on signed 32-bit integers, so apply >>> 0 to keep the value unsigned when the top bit is set.

Complexity

• Time: O(k), where k is the number of set bits (at most 32)
• Space: O(1)

Python

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n:
            n &= n - 1      # clear the lowest set bit
            count += 1
        return count

JavaScript

var hammingWeight = function(n) {
  let count = 0;
  while (n !== 0) {
    n = (n & (n - 1)) >>> 0;  // clear the lowest set bit, keep it unsigned
    count++;
  }
  return count;
};

What the interviewer is checking

It probes comfort with bitwise operators and whether you know (or can derive) why n & (n - 1) clears the lowest set bit.

Mistakes to avoid

• Using an arithmetic right shift on a signed type, which can loop forever on numbers with the top bit set.
• In JavaScript, letting the result of a bitwise operation turn negative for values at or above 2³¹.
• Looping while n > 0 in a language where a 32-bit value with the top bit set reads as negative.

Follow-ups to expect

• Count bits for every number from 0 to n. (DP: ans[i >> 1] + (i & 1).)
• Hamming distance between two integers. (Popcount of x XOR y.)
• Check whether n is a power of two. (n > 0 and n & (n - 1) == 0.)

In real software

Population counts are used to size bitmap sets, compute Hamming distance between hashes for near-duplicate detection, and evaluate positions in bitboard-based game engines; CPUs even provide a dedicated instruction for it.

Practice next