88. Number of 1 Bits · DSA Practice

Return how many 1 bits the binary representation of the positive integer n has (its Hamming weight).

Example 1

Input: n = 11

Output: 3

Explanation: 11 is 1011 in binary.

Example 2

Input: n = 128

Output: 1

Hint 1

n & (n − 1) removes the lowest 1 bit.

Bit Manipulation

Approach 1: Check every bit

Shift 32 times.

⏱ Time O(32)💾 Space O(1)

Approach 2: Brian Kernighan ✅

Loop once per set bit.

⏱ Time O(bits set)💾 Space O(1)

Reference solution for Brian Kernighan (time O(bits set), space O(1)). Each solution passes every test in all four languages.

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

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) { n &= n - 1; count++; }   // clear the lowest set bit
        return count;
    }
}

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        while (n) { n &= n - 1; count++; }        // clear the lowest set bit
        return count;
    }
};

function hammingWeight(n) {
  let count = 0;
  while (n) { n &= n - 1; count++; } // clear the lowest set bit
  return count;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Bit Manipulation.