// Number of 1 Bits

task

Given a 32-bit unsigned integer n, return the number of 1 bits it has (its Hamming weight / popcount). LeetCode #191 types the parameter as uint specifically so sign bits never enter the picture.

n = 182 = 0b10110110  →  5

how to think

The obvious approach shifts n right 32 times, checking n & 1 at each step — always exactly 32 iterations, whether n has one set bit or thirty-one. That’s correct but wasteful: most of those iterations do nothing useful when the bits are sparse.

n & (n - 1) does better. Subtracting 1 from n flips every trailing 0 bit to 1 and flips the lowest 1 bit to 0 — think of it as borrowing across the trailing zeros the way decimal subtraction borrows across trailing nines. ANDing that against the original n keeps every bit where both agree, and they only disagree at the one bit that flipped from 1 to 0. Net effect: n & (n - 1) is n with its lowest set bit cleared, nothing else touched. Loop until n hits 0, counting iterations — that’s exactly the popcount, and it takes as many steps as there are set bits, not 32 regardless.

solution

public int HammingWeight(uint n)
{
    int count = 0;
    while (n != 0)
    {
        n &= n - 1;    // clears the lowest set bit
        count++;
    }
    return count;
}

trace

n = 182 = 0b10110110:

Loop exits when n reaches 0. Final count = 5 — matches the five 1s in 10110110.

Before the first clear, the rightmost 1 (weight 2) is next in line:

After that single AND, only that bit changed:

why it works

Write n as ...1 followed by z trailing zero bits — that trailing 1 is the lowest set bit. Subtracting 1 needs to borrow from that bit: the z trailing zeros become z trailing ones, and the lowest 1 becomes 0. Every bit above the trailing zeros is untouched by the borrow. So n - 1 agrees with n on every bit above the lowest set bit, disagrees at the lowest set bit itself (1 vs 0), and disagrees on the trailing zeros (0 vs 1 — but those are 0 in n, so ANDing keeps them 0 regardless). AND the two together and only the lowest set bit changes, from 1 to 0. Repeat once per set bit, and the loop terminates exactly when none remain.

common bugs

• Using int and a signed right shift (>>) if you rewrite this as the shift-and-count brute force — arithmetic shift sign-extends negative numbers, so the loop can run forever on a negative value. C#’s uint parameter sidesteps this entirely; if you need it on a signed type, the unsigned right-shift operator >>> (C# 11+) is the fix.
• Looping the shift-and-mask version with n > 0 instead of n != 0 — for an unsigned type this particular bug is harmless, but the habit transfers badly to signed code where n > 0 misses negative values entirely.
• Reaching for for (int i = 0; i < 32; i++) and checking each bit — correct, just always 32 iterations instead of popcount(n); fine to mention as the baseline, worth upgrading from.
• On the job, System.Numerics.BitOperations.PopCount(n) is the one-liner — but an interviewer asking this question wants to see you derive the n & (n - 1) identity yourself.

variants you can now solve

• Counting Bits (LC 338) — apply this exact identity across every integer 0..n at once, reusing smaller answers instead of recomputing each popcount from scratch.
• Power of Two (LC 231) — n > 0 && (n & (n - 1)) == 0: a power of two has exactly one set bit, so clearing it must reach zero in a single step.
• Hamming Distance (LC 461) — XOR two numbers first (the differing bits become 1s), then run this exact loop on the result.