191. Number of 1 Bits

Counting the set bits in an integer — the Hamming weight — is the problem that gets you comfortable reading numbers as raw bits instead of decimal values. It sits in the bit manipulation pattern, and the one trick it teaches, n & (n - 1), quietly shows up in half the other bit problems you’ll see.

The problem

Given a positive integer, count how many of its bits are set to 1 — its Hamming weight. (The current constraints hand you a positive n; full statement on LeetCode.)

For n = 11 (binary 1011) the answer is 3. For n = 128 (binary 10000000) it’s 1. It’s still worth knowing how the bit tricks behave on a negative pattern, since Java has no unsigned int — the sign bit is just bit 31 — and that’s exactly where the >> versus >>> choice below bites.

Intuition: strip the lowest set bit at a time

The obvious approach is to look at each of the 32 bits in turn: mask the last bit with n & 1, add it to a running count, then shift right. That works, but it always does 32 iterations no matter how few bits are actually set.

Brian Kernighan’s trick is sharper. Subtracting 1 from a number flips its lowest set bit to 0 and turns every bit below it into 1. AND that back with the original and those lower bits cancel out — you’ve erased exactly one set bit and left the rest untouched:

$n \mathbin{\&} (n - 1) \;\Rightarrow\; \text{lowest set bit cleared}$

Concretely, take n = 12 (1100). Then n - 1 = 11 (1011), and 1100 & 1011 = 1000 — the lowest 1 is gone. Loop that until n hits 0, and the number of iterations is the number of set bits. So a value with three 1s costs three passes, not thirty-two.

Solution

The straight-line version first, since it reads exactly like the problem. In this fixed 32-step loop, >> and >>> both count correctly — over exactly 32 shifts you read each original bit once, and the sign bit is just bit 31. The reason to reach for >>>, the unsigned shift, is habit and safety: the moment you rewrite this as a drain-until-zero loop, arithmetic >> on a negative keeps refilling 1s from the top and never reaches 0.

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += n & 1;   // add the lowest bit (0 or 1)
            n >>>= 1;         // logical shift: fills with 0, never the sign bit
        }
        return count;
    }
}

Brian Kernighan’s version does less work and sidesteps the sign issue entirely, because it never shifts — it just keeps clearing the lowest set bit until nothing is left:

class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while (n != 0) {
            n &= (n - 1);   // erase the lowest set bit
            count++;        // ...and tally it
        }
        return count;
    }
}

Complexity

Approach	Time	Space
Bit-by-bit shift	$O(32)$	$O(1)$
Brian Kernighan	$O(k)$	$O(1)$

Both are constant space. The shift loop is a fixed 32 steps; Kernighan’s runs once per set bit, where $k$ is the number of 1s — so it’s never slower and often much faster.

In an interview

Write the shift loop first so you have something correct on the board, then say “but I can loop once per set bit instead of once per position” and pivot to n & (n - 1). Explaining why the AND clears the lowest bit — subtracting 1 borrows through the trailing zeros — is what separates knowing the trick from memorizing it.

The trap here is Java-specific: a while (n != 0) shift loop with arithmetic >> never terminates on a negative input, because the sign bit keeps refilling the top. The fixed 32-step loop sidesteps that, and Kernighan’s n & (n - 1) avoids shifting entirely — a fair reason to prefer it. If the follow-up asks about calling this millions of times, mention a precomputed lookup table over 8-bit chunks. From here, Counting Bits asks for the count of every value up to n and builds on this exact n & (n - 1) relationship, and Sum of Two Integers leans on the same bit-level thinking; the bit manipulation hub ties the family together.

References

• LeetCode 191 — Number of 1 Bits