Sweaty Imposter

Number of 1 Bits

EasyBitwise XORBlind 75JuniorOpen on LeetCodeUpdated

You're given a positive integer n. Return how many 1 bits appear in its binary representation, a count also known as the Hamming weight or population count.

Examples

n = 13 returns 3

13 is 1101 in binary, which has three 1 bits.

n = 64 returns 1

64 is a power of two, 1000000 in binary, so it has a single 1 bit.

n = 2147483647 returns 31

The largest 32-bit signed integer is thirty-one 1 bits in a row.

Constraints

  • 1 <= n <= 2^31 - 1

Hints

Hint 1

You could test every bit, but is there a way to jump straight from one 1 bit to the next?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

n & (n - 1) clears the lowest set bit of n: subtracting 1 flips that bit to 0 and every bit below it to 1, and the AND keeps only the bits above it. Apply it until n reaches 0 and count the rounds. The loop runs once per 1 bit, at most 32 times. Shifting right and testing n & 1 also works, but always takes as many rounds as the highest set bit's position.

Time

O(1)

Space

O(1)

Pitfall

Shifting a Java int with >> when the input can have its top bit set. Arithmetic shift copies the sign bit, so n never reaches 0. Use >>> or the n & (n - 1) trick, which works for any bit pattern.

Solutions

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= n - 1;
            count++;
        }
        return count;
    }
}
Drill This