Number of 1 Bits — DSA

Problem

Given a 32-bit integer n, return the number of 1 bits in its binary representation (its Hamming weight, or population count).

n = 11          (binary 00000000000000000000000000001011)   →   3
n = 128         (binary 00000000000000000000000010000000)   →   1
n = -3          (binary 11111111111111111111111111111101)   →   31   (treated as unsigned bits)

In Java, the input arrives as a signed int, but you must count its bits as if it were unsigned. So use the unsigned shift >>>, or loop a fixed 32 times. A signed >> on a negative number never reaches zero.
Follow-up: if this function is called many times, how would you optimize it? Integer.bitCount and lookup tables are both fair answers.

Examples

Example 1

Input: n = 11 (binary 1011)

Output: 3

Explanation: Three set bits.

Example 2

Input: n = 128 (binary 10000000)

Output: 1

Explanation: One set bit.

Constraints

•The input is a 32-bit unsigned integer

Hints

Hint 1

The brute force checks all 32 bit positions individually (n & 1, then n >>>= 1, repeated 32 times) — correct, but does the same fixed amount of work regardless of how many bits are actually set.

Hint 2

n & (n-1) clears exactly the LOWEST set bit of n — what does repeating this until n becomes 0 tell you?

Hint 3

The number of iterations until n reaches 0 via n &= (n-1) is exactly the number of set bits — no need to check all 32 positions if only a few are set.

Solutions

public int hammingWeightBruteForce(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        if ((n & (1 << i)) != 0) count++;
    }
    return count;
}

Time: O(32) = O(1), but always the full 32 checks · Space: O(1)