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

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:

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

🧠 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

• Initialize the answer:

  int ans = 0;

  Always start at zero, because math.
• While n is not zero:

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

  Keep flipping switches as long as there’s light in your life.
• ZAP the lowest 1:

  n = n & (n - 1);

  This turns off the lowest ‘on’ bit. Super-efficient janitor move.
• Count the flip:

  ans++;

  You did work, so reward yourself with a count.
• Return the answer:

  return ans;

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

💻 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.

🧠 Interviewer Brain-Tattoo

“Counting 1’s the slow way is cute… if you like mediocrity. Bitwise magic? That’s how you make the CPU your sous chef.”