The O(n) Club: How Many 1’s? Hamming Weight and Your Bitwise Showdown

⚡ TL;DR

You want to count the number of 1 bits in an integer. You could check each bit like a tired robot in a lightbulb factory, but that’s slow and boring. The smart way uses n & (n-1): flip off the rightmost ‘on’ switch, count, repeat, go home early. Java makes it a snap:

🧠 How Devs Usually Mess This Up

Classic blunders: assuming the input is a binary string (nope, it’s a number—put down the split("1")), or using right-shift and checking every bit, which is basically the slow cooker approach. Others try converting to a binary string, then counting ‘1’s by hand. That’s legal, but in interviews, it’s the code equivalent of bringing a butter knife to a laser tag fight.

🔍 What’s Actually Going On

Picture a row of lights—on/off. You’re supposed to count how many are on. The n & (n-1) move is like a janitor who can switch off the rightmost lit bulb in a single sweep. Each time you do it, poof—one less ‘1’. When they’re all out, you know how many there were by counting your sweeps. This trick doesn’t care how many bulbs you have, just how many were on. Chef’s kiss for performance!

🛠️ PseudoCode

Return the answer:

return ans;

Take the rest of the day off—you’ve earned it.

Count the flip:

ans++;

You did work, so reward yourself with a count.

ZAP the lowest 1:

n = n & (n - 1);

This turns off the lowest ‘on’ bit. Super-efficient janitor move.

While n is not zero:

while (n != 0) { ... }

Keep flipping switches as long as there’s light in your life.

Initialize the answer:

int ans = 0;

Always start at zero, because math.

💻 The Code

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

⚠️ Pitfalls, Traps & Runtime Smacks

Stop with Strings: Don’t convert the number to a binary string—you’re here to impress, not regress.
Input Isn’t Binary: It’s a normal integer, not “10110111”.
Signed vs Unsigned Blues: Java’s int is signed. For counting bits, just pretend it’s unsigned, unless your interviewer starts waving their arms.
Beware the Infinite Loop: If you don’t check n != 0, well, enjoy your new career as a stuck process.
Complexity Reality Check: This runs in O(k), where k is number of ‘1’s. If they’re all on, that’s O(32), but usually way faster than the O(32) naive approach.