Number of 1 Bits

Given a positive integer n, write a function that returns the number of set bits in its binary representation (also known as the Hamming weight).

Example 1:

Input: n = 11

Output: 3

Explanation:

The input binary string 1011 has a total of three set bits.

Example 2:

Input: n = 128

Output: 1

Explanation:

The input binary string 10000000 has a total of one set bit.

Example 3:

Input: n = 2147483645

Output: 30

Explanation:

The input binary string 1111111111111111111111111111101 has a total of thirty set bits.

Constraints:

• 1 <= n <= 231 - 1

Follow up: If this function is called many times, how would you optimize it?

Approach: n & (n - 1) Trick (Efficient)

Algorithm

1. Repeatedly clear the lowest set bit with n = n & (n - 1)
2. Count how many times this operation is performed
3. Each iteration removes exactly one 1 bit

Time & Space Complexity

• Time Complexity: O(number of set bits) - at most 32 iterations
• Space Complexity: O(1) - constant extra space

Java Implementation

public class NumberOf1Bits {

    /**
     * Return the number of 1 bits (Hamming weight) in n.
     * @param n Positive integer
     * @return Number of set bits
     */
    public static int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n = n & (n - 1); // clear the lowest set bit
            count++;
        }
        return count;
    }

    // Test method
    public static void main(String[] args) {
        System.out.println("Input: n = 11");
        System.out.println("Output: " + hammingWeight(11)); // Expected: 3

        System.out.println("Input: n = 128");
        System.out.println("Output: " + hammingWeight(128)); // Expected: 1

        System.out.println("Input: n = 2147483645");
        System.out.println("Output: " + hammingWeight(2147483645)); // Expected: 30
    }
}

Alternative Approach: Iterate All 32 Bits

public class NumberOf1BitsAllBits {

    public static int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += (n >> i) & 1;
        }
        return count;
    }
}

Example Walkthrough

For n = 11 (binary 1011):

1. n = 11 & 10 = 10, count = 1
2. n = 10 & 9 = 8, count = 2
3. n = 8 & 7 = 0, count = 3

Answer: 3.

Key Points

1. Lowest Bit Clearing: n & (n - 1) removes the rightmost set bit
2. Faster than Shifting: Only iterates once per set bit, not 32 times
3. Integer.MIN_VALUE Safe: Handles negative inputs correctly since n becomes 0 after 32 clears
4. Follow-up: For repeated calls, a lookup table of 256 entries can answer each byte’s popcount in constant time
5. Java’s Integer.bitCount: Java provides a built-in Integer.bitCount(n)