Number of 1 Bits

bit-manipulation

Problem

Write a function that takes an unsigned integer and returns the number of 1 bits it has (the Hamming weight).

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)