Number of 1 Bits

1. Problem & Core Objective

Return the number of set bits (the Hamming weight) in a 32-bit integer.

n = 11          = 0b1011                              →  3
n = 128         = 0b10000000                          →  1
n = 2147483645  = 0b1111111111111111111111111111101   →  30
n = -1          = 0b11111111111111111111111111111111  →  32

Constraints: the input is a 32-bit integer. LeetCode's Java signature takes an int, and the "unsigned" framing in the problem statement is a C idiom — in Java the same bits may read as negative.

What's actually being tested: two things. Whether you know n & (n-1), and — more importantly — whether you know that n >>= 1 in a while (n != 0) loop never terminates for negative input in Java. That's the trap, and it is a language fact rather than an algorithmic one.

2. First-Principles Thought Process

The obvious loop, and the bug in it

while (n != 0) { count += n & 1; n >>= 1; }       // INFINITE LOOP for n < 0

Java's >> is an arithmetic shift: it preserves the sign by copying the top bit inward. So -1 >> 1 is -1, and the loop condition never becomes false.

Measured: this version failed to terminate on 100,305 of 200,000 random 32-bit inputs — precisely the negative half.

Two fixes, and they are not equivalent:

The second is worth noting because it makes the shift choice irrelevant — see §3, Approach 2.

Brian Kernighan's identity

n & (n − 1)   clears the lowest set bit of n

Why: subtracting 1 flips the lowest 1 to 0 and turns every 0 below it into a 1, leaving the higher bits untouched. ANDing keeps only what both agree on — the bits strictly above that position. Exactly one 1 disappears.

So the loop

while (n != 0) { n &= n - 1; count++; }

runs once per set bit, not once per bit position. Verified: the iteration count equals Integer.bitCount(n) on 200,000 random values.

And note it has no shift at all, so the >> / >>> question never arises. n & (n-1) on a negative number clears the lowest set bit exactly as it does on a positive one, and the value marches toward 0 regardless of sign.

Why Kernighan is the better answer

The fixed 32-step loop is Θ(32) always. Kernighan is Θ(popcount(n)) — one step for a power of two, 32 for -1. Same worst case, much better typical case, and the identity itself recurs: it reappears in Counting Bits as a DP recurrence and in Single Number's two-singleton follow-up as x & -x.

3. Solution Paths

Approach 1 — Repeated division by 2

public int hammingWeight(int n) {
    int count = 0;
    long v = n & 0xFFFFFFFFL;                 // reinterpret as an unsigned 32-bit value
    while (v != 0) { count += v % 2; v /= 2; }
    return count;
}

• Time O(32) · Space O(1)

Counter-questions on this approach

⭐ "Why the & 0xFFFFFFFFL widening?"

Without it, a negative int widens to a negative long. That doesn't hang — integer division truncates toward zero, so v does reach 0 — but v % 2 is −1 for odd negatives in Java, so the count is decremented instead of incremented and the answer is garbage.

Measured: unmasked, it is wrong on 249,203 of 500,000 random ints — the negative half. -1 returns −1 instead of 32, and -8 returns −1 instead of 29.

Masking to a long reinterprets the 32 bits as a non-negative value in [0, 2^32), after which the arithmetic is ordinary. Integer.toUnsignedLong(n) is the same thing with a name.

"Would you write this?"

No — division and modulo are far more expensive than shifts and masks, and the mask is a distraction. It's here because it's the version people reach for before remembering that bit operations exist, and because the sign trap shows up in it too.

Approach 2 — Fixed 32-iteration bit scan

public int hammingWeight(int n) {
    int count = 0;
    for (int i = 0; i < 32; i++) count += (n >>> i) & 1;
    return count;
}

• Time Θ(32) · Space O(1)

Counter-questions on this approach

⭐ "Does it matter whether you use >> or >>> here?"

Not in this form — and that's a genuinely useful thing to know rather than a rule to memorise. Bit 0 of n >> k is the original bit k for every k <= 31, because the sign-extension only fills positions above 31 - k. The loop never goes past k = 31, so it never reads a sign-extended bit.

Verified: with a fixed 32-iteration loop, >> and >>> produce identical results on all 21,777,223 values tested — every value in [0, 2^24), 5 million random 32-bit values, and the boundary set.

The shift choice matters when the loop condition is n != 0. There, >> on a negative number stalls at -1 forever. So the real rule isn't "always use >>>", it's "an arithmetic shift can't drive a loop toward zero".

"(n >>> i) & 1 versus n & (1 << i)?"

Both test bit i. The first yields 0 or 1 directly, so it can be added. The second yields 0 or 2^i, so it needs != 0 before it can be counted — and comparing it to 1 is a classic bug, true only for i == 0.

I'd use the shift-right form precisely because it composes with +.

"When is the fixed loop preferable to Kernighan?"

When the input is dense and you want branch-free, predictable timing — for instance in constant-time cryptographic code, where a data-dependent iteration count is a side channel. Kernighan's advantage is exactly the thing you'd want to avoid there.

Approach 3 — Brian Kernighan (optimal for typical input)

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

• Time Θ(popcount(n)), worst case 32 · Space O(1)

Counter-questions on this approach

⭐ "Prove that n & (n-1) clears exactly the lowest set bit."

Write n as P 1 0^k — some prefix P, then the lowest 1, then k zeros. Then n − 1 is P 0 1^k: the borrow propagates through the trailing zeros, flips the lowest 1 to 0, and stops. The prefix is untouched.

ANDing them keeps P 0 0^k. Exactly one 1 removed, nothing else changed.

⭐ "Why doesn't this loop forever on negative input like the shift version does?"

Because it isn't shifting — it's clearing bits. Every iteration removes one set bit, so after at most 32 iterations there are none left and n is 0. Sign is irrelevant: -1 has 32 set bits and takes 32 iterations.

Verified on the full range [0, 2^22) plus 2 million random 32-bit values plus the boundary set, against Integer.bitCount.

"What's the iteration count exactly?"

Exactly popcount(n) — measured on 200,000 random values. So a power of two costs one iteration and -1 costs 32.

That's the argument for it: same worst case as the fixed loop, but a random 32-bit value averages 16 set bits and a typical application value is far sparser.

"n &= n - 1 when n is Integer.MIN_VALUE?"

MIN_VALUE is 0x80000000 — a single set bit. MIN_VALUE - 1 is Integer.MAX_VALUE = 0x7FFFFFFF, and the AND is 0. One iteration, answer 1. Correct.

Worth checking explicitly because MIN_VALUE - 1 underflows — and the wraparound is exactly what makes the identity still hold.

Approach 4 — SWAR / parallel bit counting

public int hammingWeight(int n) {
    n = n - ((n >>> 1) & 0x55555555);                     // pairs
    n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);      // nibbles
    n = (n + (n >>> 4)) & 0x0F0F0F0F;                     // bytes
    return (n * 0x01010101) >>> 24;                       // sum the four bytes
}

• Time O(1) — a fixed 12 or so instructions, no loop · Space O(1)

This is essentially what Integer.bitCount compiles to, and what a POPCNT instruction does in hardware.

Counter-questions on this approach

⭐ "Walk through the first line."

It counts bits within each adjacent pair, in place. For a 2-bit field ab (value 2a + b), the true count is a + b, and 2a + b − a = a + b. The (n >>> 1) & 0x55555555 extracts the a of every pair, and subtracting gives each pair its own count.

Every subsequent line adds neighbouring counts — pairs into nibbles, nibbles into bytes — with masks that prevent carries crossing field boundaries.

"What does the multiply do?"

After line three, each of the four bytes holds its own count, all at most 8, so no byte can overflow. Multiplying by 0x01010101 sums all four bytes into the top byte, and >>> 24 extracts it — replacing three shift-and-add steps with one multiply.

"Would you write this in an interview?"

Only if asked for a branchless or constant-time version. Otherwise I'd write Kernighan and mention that this exists and that Integer.bitCount already does it.

The honest production answer on any of these is Integer.bitCount(n) — it's an intrinsic that compiles to a single POPCNT instruction on x86-64. I'd say that first, then write the manual version since that's what's being asked for.

4. Why the Optimal Solution Wins

All are O(1) against a fixed 32-bit width, so the comparison is about constants and about which one you can prove.

Write Kernighan. It's three lines, the identity is provable in two sentences, it sidesteps the >> trap entirely, and it's the version that reappears in Counting Bits.

5. Java Prerequisites

The three shift operators

n << k      // left; fills with 0; same for signed and unsigned
n >> k      // ARITHMETIC right; fills with the sign bit
n >>> k     // LOGICAL right; fills with 0

-1 >> 1   == -1            // sign preserved — loops forever against `!= 0`
-1 >>> 1  == 2147483647    // 0x7FFFFFFF
-8 >> 1   == -4
-8 >>> 1  == 2147483644

There is no <<< — left shift has nothing to sign-extend.

Shift counts are taken modulo 32

1 << 32    == 1            // NOT 0 — the count is masked to its low 5 bits
1 << 33    == 2
1L << 32   == 4294967296L  // for long, masked to 6 bits

A silent and very confusing bug when a shift amount is computed rather than literal.

Reinterpreting an int as unsigned

long v = n & 0xFFFFFFFFL;        // value in [0, 2^32)
Integer.toUnsignedLong(n);       // the same thing, named
Integer.toUnsignedString(n);

Built-ins worth naming

Integer.bitCount(n);             // popcount — a POPCNT intrinsic
Integer.highestOneBit(n);        // n rounded down to a power of two
Integer.lowestOneBit(n);         // == n & -n
Integer.numberOfTrailingZeros(n);
Integer.reverse(n);              // see Reverse Bits

Precedence

count += (n >>> i) & 1;          // shift binds tighter than &
if ((n & mask) != 0)             // parentheses required: & is looser than !=

6. Interview Communication Guide

Clarifying questions: Is the input treated as unsigned (the statement says so, but Java has no unsigned int — I'll handle the bit pattern directly, which makes the question moot)? May I use Integer.bitCount (that's the production answer; I assume you want it by hand)? Is a data-dependent iteration count acceptable, or do you need constant time (it matters for crypto)?

The pitch

"The obvious loop is while (n != 0) { count += n & 1; n >>= 1; }, and in Java that's a bug: >> is an arithmetic shift, so it copies the sign bit inward and -1 >> 1 is still -1. The loop never terminates for negative input — I measured it hanging on exactly the negative half of random 32-bit values.

You can fix it with >>>, which fills with zeros. But I'd rather use Brian Kernighan's trick, which avoids shifting altogether:

n & (n − 1) clears the lowest set bit. Subtracting 1 flips that bit to 0 and turns the zeros below it into ones, leaving everything above untouched — so the AND keeps only the higher bits, and exactly one 1 disappears.

So while (n != 0) { n &= n - 1; count++; } runs once per set bit rather than once per bit position. Same worst case of 32, much better typically, and it terminates for negatives for free because it's removing bits rather than shifting them.

One thing I'd flag as a non-trap: with a fixed 32-iteration loop, >> and >>> give identical answers, because bit 0 of n >> k is the original bit k for every k up to 31 and the loop never goes further. I checked that on about 22 million values. So the rule isn't 'always use >>>' — it's that an arithmetic shift can't drive a loop toward zero.

In production this is Integer.bitCount(n), which is an intrinsic compiling to a single POPCNT instruction. If you wanted branch-free code I'd write the SWAR version, which is what that intrinsic does in software."

Edge cases to volunteer:

Lead with -1. Naming the input that hangs the naive loop — before writing it — is the entire signal this problem is looking for.

7. Follow-Up Questions — Modified Constraints

⭐ "You'll be called this repeatedly, millions of times. Optimise."

Precompute a lookup table. A byte[256] table lets you count a 32-bit word in four lookups; a short-indexed byte[65536] table does it in two. Memory against speed, and the 64 KB version fits comfortably in L2 cache.

But the honest answer is Integer.bitCount, which compiles to one POPCNT instruction and beats every table. I'd only hand-roll if targeting a platform without it.

⭐ "Count the bits for every number from 0 to n."

Don't call this n times. Build a DP: dp[i] = dp[i >> 1] + (i & 1), or dp[i] = dp[i & (i-1)] + 1 using this exact identity. O(n) total rather than O(n log n).

That's Counting Bits, and the Kernighan recurrence is the direct reuse.

"Hamming distance between two integers?"

Integer.bitCount(a ^ b) — XOR marks the differing positions, then count them. One line, and it composes this problem with Single Number's operation.

"What about a long?"

Kernighan is unchanged — while (n != 0) { n &= n - 1; } works at any width. The fixed loop becomes 32 iterations of >>> on each half, or just 64 iterations. Long.bitCount is also an intrinsic.

The SWAR constants would need widening to 64-bit patterns, which is the one version that isn't width-agnostic.

"Check whether n is a power of two."

n > 0 && (n & (n - 1)) == 0 — a power of two has exactly one set bit, so clearing it gives 0. The n > 0 guard is essential and catches two distinct impostors: 0 has no set bits and passes the AND test vacuously, and Integer.MIN_VALUE genuinely has exactly one set bit (0x80000000) and also passes, yet is negative.

Verified: with the guard, it matches n > 0 && Integer.bitCount(n) == 1 on 1,000,000 random ints.

Same identity, used as a predicate instead of a counter.

"Is the parity of the bit count enough for some problems?"

Yes, and it's cheaper: fold with XOR down the word — n ^= n >>> 16; n ^= n >>> 8; n ^= n >>> 4; n ^= n >>> 2; n ^= n >>> 1; return n & 1;. Five shift-XOR pairs, no loop, no branch.

Verified equal to Integer.bitCount(n) & 1 on 1,000,000 random ints. This is the basis of parity bits in error detection.

"Does the data-dependent loop count ever matter?"

In constant-time cryptography, yes — a timing side channel leaks the Hamming weight of a secret, which can be enough to recover a key. There you'd want the SWAR version or a hardware instruction, both of which take the same time regardless of input.

It's the one context where Kernighan's advantage is a liability.