#191 Number of 1 Bits

frequently reported atApple Microsoft Google Amazon

the problem

In plain words

Given a positive integer n, return how many 1-bits are in its binary form (its Hamming weight). Older versions of the problem passed an unsigned 32-bit value, which arrives in Java as a possibly negative int, so make your code work for negatives too.

in n = 11

out 3

11 = 1011 in binary.

in n = 128

out 1

10000000.

in n = 2147483645

out 30

1 ≤ n ≤ 2³¹ − 1 (current version)
Older versions allowed any 32-bit pattern, i.e. negative ints in Java

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternBit tricks (shift, mask, lowest set bit)

n & (n − 1) erases the lowest 1-bit. Count how many times you can do that before n becomes 0.

solutions

From brute force to optimal

Shift right with >>> and test the last bit, 32 times.

For i in 0..31: if (n >>> i) & 1 is 1, count it.

timeO(32) = O(1)

Always 32 iterations, whatever the input.

spaceO(1)

A counter.

java

1class Solution {2    public int hammingWeight(int n) {3        int count = 0;4        for (int i = 0; i < 32; i++) {5            if (((n >>> i) & 1) == 1) count++;6        }7        return count;8    }9}

Each n &= n − 1 removes exactly one 1-bit, so loop until n is 0.

count = 0.
While n ≠ 0: n &= n − 1; count++.
Return count.

timeO(k)

k = number of 1-bits (≤ 32). Sparse numbers finish in a few steps.

spaceO(1)

A counter.

java

1class Solution {2    public int hammingWeight(int n) {3        int count = 0;4        while (n != 0) {5            n &= n - 1; // erase the lowest 1-bit6            count++;7        }8        return count;9    }10}

sim

Dry run

loading simulation…

java

1class Solution {2    public int hammingWeight(int n) {3        int count = 0;4        while (n != 0) {5            n &= n - 1; // erase the lowest 1-bit6            count++;7        }8        return count;9    }10}

The JDK's popcount. HotSpot may turn it into a single POPCNT instruction.

Return Integer.bitCount(n).

timeO(1)

A fixed sequence of about a dozen operations — or one POPCNT instruction when HotSpot intrinsifies it.

spaceO(1)

Nothing stored.

java

1class Solution {2    public int hammingWeight(int n) {3        return Integer.bitCount(n); // a HotSpot intrinsic: often one POPCNT instruction4    }5}

in the room

How to say it in the interview

talk track

Explain why n − 1 flips the lowest 1 and every 0 below it, so the AND clears exactly that one bit.
Point out that while (n != 0) also ends for negative n. A >> loop would never end.

traps

Using >> in the shift version: for negative n the loop condition n != 0 never becomes false.

what they ask next

Follow-ups

Called millions of times. How do you speed it up?

Precompute a 256-entry table of byte popcounts and add four lookups. Or just use Integer.bitCount, which is a hardware instruction.

before you submit

Edge cases to test

n = 1 → 1.
Integer.MAX_VALUE → 31.
A negative int (older versions): −1 → 32. A >> loop never ends, because −1 >> 1 is still −1.

practise next