Number of 1 Bits

Problem

Given a non-negative integer n that fits in 32 bits, return how many bits are set to 1 in its binary representation (its Hamming weight).

• 0 <= n <= 2^32 - 1
• The input is to be treated as an unsigned 32-bit value; 2^32 - 1 has all 32 bits set.

Examples

• n = 25 → 3, since 25 = 0b11001.
• n = 64 → 1, since 64 = 0b1000000.
• n = 2^32 - 1 → 32; every bit of the unsigned 32-bit value is set.

Hints

1. You can inspect the lowest bit with n & 1 and discard it with n >> 1. What does looping over that give you?
2. Instead of visiting all 32 bit positions, can you jump directly from one set bit to the next?
3. n & (n - 1) clears the lowest set bit. Count how many times you can do that before reaching 0.