Number of 1 Bits

Examples

Input: n = 11 (binary: 00000000000000000000000000001011)
Output: 3

The binary form has three 1 bits, at the positions worth 8, 2, and 1.

Input: n = 128 (binary: 00000000000000000000000010000000)
Output: 1

128 is a power of two, so it has exactly one 1 bit.

Input: n = 0
Output: 0

Zero has no 1 bits at all.

Constraints

• The input is an unsigned integer represented using 32 bits.

• 0 <= n <= 2^32 - 1

Approach

A number's binary form has 32 fixed positions (for an unsigned 32-bit integer), each either a 0 or a 1. The direct way to count the 1s is to check every single one of those 32 positions - shift the number right by each amount from 0 to 31, look at just the last bit each time, and add up how many were 1.

A faster approach skips straight past the 0 bits instead of checking every position. It relies on a small trick: for any number n, computing n & (n - 1) always clears out exactly its lowest 1 bit, leaving every other bit exactly as it was (subtracting 1 flips all the trailing 0s to 1s and the lowest 1 to a 0, and ANDing with the original number keeps only the bits that agree). Repeating that operation and counting how many times it takes to reach 0 gives the number of 1 bits directly - doing exactly as much work as there are 1 bits, rather than 32 checks every time.

Solutions

Brute Force - Check Every Bit Position

Shift the number right by each amount from 0 to 31 (using an unsigned shift, so the sign of the underlying value never matters), and check whether the last bit at that shifted position is a 1.

function hammingWeight(n) {
  let count = 0;

  for (let i = 0; i < 32; i++) {
    if ((n >>> i) & 1) {
      count++;
    }
  }

  return count;
}

Time: O(1) - always exactly 32 checks · Space: O(1)

Optimal - Clear the Lowest Set Bit Repeatedly

Repeatedly replace n with n & (n - 1), which always clears out exactly its lowest 1 bit. Count how many times this can be done before n reaches 0 - that count is exactly the number of 1 bits n started with.

function hammingWeight(n) {
  let count = 0;

  while (n !== 0) {
    n = n & (n - 1);
    count++;
  }

  return count;
}

Time: O(k), where k is the number of 1 bits in n (at most 32) · Space: O(1)