Number of 1 Bits

EasyBit Manipulation🧩 Bit Manipulation LeetCode #191 ↗Updated Oct 30, 2026

Problem

Count how many bits are set to 1 in the 32-bit binary form of the integer n (its Hamming weight). Treat n as an unsigned pattern of bits, so a negative Java int such as -1 counts all 32 of its bits.

Inputn = 11 (binary 1011)Output3

Inputn = 128 (binary 10000000)Output1

Inputn = 2147483645Output30

n fits in 32 bits · Follow-up: the function is called many times — how would you speed it up?

Try it yourself

Java

class Solution {
    public int hammingWeight(int n) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

n & (n − 1) erases exactly the lowest set bit, so you can loop once per set bit. For heavy repeated use, precompute counts for every byte and answer with four table lookups.

PatternBit Manipulation

Instinct Pairs that cancel, counting 1s, powers of two, subsets as numbers, or 'no + or - allowed' - drop to binary and use XOR, AND, OR and shifts.

Memory hack XOR is a forgetful twin detector - see something twice and it vanishes; n & (n-1) snips off the last lit bulb.

Open the Bit Manipulation guide →

Approaches

Brute ForceCheck All 32 Positions

Time O(32)Space O(1)

Look at the lowest bit with n & 1, add it to the count, then shift with the unsigned >>> so the sign bit doesn’t get copied in. Repeat 32 times.

Java

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) {
        count += n & 1;
        n >>>= 1; // unsigned shift: works for negative n too
    }
    return count;
}

Always 32 iterations, even for n = 1.

BetterClear Lowest Set Bit (Kernighan)

Time O(k), k = set bitsSpace O(1)

Subtracting 1 turns the lowest 1 into 0 and the zeros below it into ones; ANDing with the original wipes all of those. Each iteration removes one set bit, so the loop runs exactly k times.

Java

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1; // remove lowest set bit
        count++;
    }
    return count;
}

Dry runn = 11 (binary 1011)

n lowest set bit changed

n=11
1

0

1

1
n
count=0
n=10
1

0

1
n
0

count=1
n=8
1
n
0

0

0

count=2
n=0
0

0

0

0

count=3 ✔

Fast for sparse numbers; still 32 steps for -1.

OptimalByte Lookup Table

Time O(1) per callSpace O(1) (256 entries)

Precompute once: bits[i] = bits[i >> 1] + (i & 1) for every byte value 0-255. Each call then splits n into four bytes and adds four table entries — no loop over bits at all.

Java

private static final int[] BITS = new int[256];
static {
    for (int i = 1; i < 256; i++) BITS[i] = BITS[i >> 1] + (i & 1);
}

public int hammingWeight(int n) {
    return BITS[n & 0xFF] + BITS[(n >>> 8) & 0xFF]
         + BITS[(n >>> 16) & 0xFF] + BITS[(n >>> 24) & 0xFF];
}

Best when called many times (the follow-up); tiny fixed table.

Pro tip

In production just call Integer.bitCount(n) — it compiles to a single CPU popcnt instruction on most JVMs.

At a glance

Level	Approach	Time	Space
Brute Force	Check All 32 Positions	`O(32)`	`O(1)`
Better	Clear Lowest Set Bit (Kernighan)	`O(k), k = set bits`	`O(1)`
Optimal	Byte Lookup Table	`O(1) per call`	`O(1) (256 entries)`

Common pitfalls

Using >> on a negative int — sign extension makes the loop never end.
Looping while (n > 0) — skips negative inputs entirely.
Forgetting the & 0xFF mask when indexing the table.

Interview tips

Explain why n & (n − 1) clears the lowest set bit with a 4-bit example.
Call out Java’s lack of unsigned ints and the need for >>>.
Answer the follow-up with the lookup table (or hardware bitCount).

Pattern

Lowest-set-bit trick → count, iterate or remove set bits in O(number of ones).

My notes saved in this browser