Number of 1 Bits

Problem Description

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

Examples

Constraints

• 1 ≤ n ≤ 2³¹ - 1

Clearing the Lowest Set Bit Recursively

The simple way to count set bits is shifting the number right 32 times, checking the last bit each time: count += n & 1; n = n >> 1. This always takes 32 iterations, even if the number only has one set bit (like 10000000).

To optimize, we can use Brian Kernighan’s Algorithm. The operation n & (n - 1) is a bitwise trick that always clears the lowest set bit of n to 0, leaving all other bits unchanged.

• For example, if n = 12 (1100):
  • n - 1 = 11 (1011)
  • n & (n - 1) = 1100 & 1011 = 1000 (8)
• We repeat this operation until n becomes 0, incrementing our counter on each step. The loop runs exactly as many times as there are set bits, which is much faster for sparse integers.

Solution 1: Shift and Check (Standard O(32))

Loop 32 times, shifting the integer and checking the least significant bit.

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if ((n & 1) == 1) {
                count++;
            }
            n = n >>> 1; // logical right shift (shifts sign bit)
        }
        return count;
    }
}

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        for _ in range(32):
            count += n & 1
            n = n >> 1
        return count

class Solution {
public:
    int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            if (n & 1) {
                count++;
            }
            n = (unsigned int)n >> 1; // cast to unsigned to avoid sign propagation
        }
        return count;
    }
};

Complexity Analysis:

• Time Complexity: O(1). The loop always runs 32 times.
• Space Complexity: O(1) auxiliary space.

Where it breaks: If you use arithmetic right shift >> instead of logical right shift >>> in Java, negative integers will propagate 1 into the sign bit, resulting in an infinite loop.

Solution 2: Brian Kernighan’s Algorithm (Set-Bit Proportional)

Iteratively clear the lowest set bit using n & (n - 1), incrementing count until the value is zero.

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

class Solution:
    def hammingWeight(self, n: int) -> int:
        count = 0
        while n != 0:
            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 & (n - 1); // clears the lowest set bit
            count++;
        }
        return count;
    }
};

Complexity Analysis:

• Time Complexity: O(k) where k is the number of set bits (Hamming weight). In the worst case (all bits set), this is O(32) = O(1).
• Space Complexity: O(1).

Where it breaks: Nothing breaks. It handles all integers correctly and is faster than Solution 1 on average.

Common Mistakes

• Using arithmetic shift >> in Java on negative numbers. In Java, int is signed. Shifting a negative number arithmetic-right >> inserts 1s on the left, causing the loop to run indefinitely. Use the unsigned logical shift >>>.
• Using while (n > 0) instead of while (n != 0). In languages with signed integers, a negative number is less than 0, but can still contain set bits. The condition must check n != 0.
• Forgetting parentheses around bitwise operations. Bitwise operators have lower precedence than comparison operators in many languages (e.g. n & 1 == 1 parses as n & (1 == 1)). Always write (n & 1) == 1.

Frequently Asked Questions

Why does n & (n - 1) clear the lowest set bit? Subtracting 1 from n flips all bits starting from the rightmost set bit up to the end. For example, 12 (1100) minus 1 is 11 (1011). When we run bitwise & with the original number, the matching higher bits remain, but the rightmost set bit (and everything to its right) is cleared to 0.

Are there built-in functions to count set bits? Yes. In Java, Integer.bitCount(n). In C++, __builtin_popcount(n). In Python, bin(n).count('1'). In interviews, you are expected to explain the underlying bitwise logic rather than using these built-in helpers.

What does this problem test in interviews? It tests your comfort with bitwise operations, understanding the difference between signed and logical right shifts, and your knowledge of bitwise arithmetic tricks.

← All Problems