Number of 1 Bits

Share

Write a function that takes the binary representation of a positive integer and returns the number of set bits it has (also known as the Hamming weight).

Example 1
Input: n = 11 (binary: 00000000000000000000000000001011)
Output: 3
Explanation: The binary representation has three '1' bits.
Example 2
Input: n = 128 (binary: 00000000000000000000000010000000)
Output: 1
Explanation: Only one '1' bit at position 7.

Solution Approach

The trick n & (n-1) clears the lowest set bit of n. By repeatedly applying this until n becomes 0, we count exactly how many 1-bits n has: each iteration removes one 1-bit.

  • Initialize count to 0.
  • While n is not zero, perform n = n & (n-1) to clear the lowest set bit.
  • Increment count on each iteration.
  • Return count when n reaches 0.
Java
public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1); // clears lowest set bit
            count++;
        }
        return count;
    }
}
Complexity Analysis:

Time complexity: O(k) where k is the number of set bits. Each iteration removes one 1-bit.
Space complexity: O(1). Constant extra space.