Count the set bits in a 32-bit integer. Now tell me what your loop does when I hand it a negative number.

The obvious loop, and where it stops being obvious

The shape everyone writes first is to test the low bit, add it to a running total, shift right, and repeat until the value is zero. For any non-negative input that is correct and it runs in as many iterations as there are bits below and including the highest set bit.

The moment the input can be negative, the loop's termination condition depends on what the right shift does with the sign. In Java, >> is an arithmetic shift: it replicates the sign bit into the vacated high position, so shifting a negative value right forever gives you minus 1 forever, and the loop never reaches zero. >>> is the logical shift, which feeds in zeros, and that version terminates after 32 iterations. In C the behaviour of right-shifting a negative signed value is implementation-defined, which is a worse position to be in than either Java option, and the standard answer there is to do the work on an unsigned type.

So the first thing to establish is the type. "Is this a signed 32-bit int, and do I need to handle negative inputs?" is a ten-second question that decides which operator you write, and asking it is scored.

Working minus 8 through by hand

Two's complement makes this concrete. Minus 8 in 32 bits is the bitwise complement of 7, which is 0xFFFFFFF8. Seven has three set bits, so its complement has 32 minus 3, that is 29. Minus 1 is all ones and has 32. The minimum value has exactly one set bit, the sign bit.

Run the arithmetic-shift version on minus 8. The first iterations peel off zeros and then ones, but once the value has degraded to all ones it is minus 1, and shifting minus 1 arithmetically right gives minus 1 again. The count grows without bound and the function never returns. Run the logical-shift version and you get 29 after 32 iterations. The bug is not a wrong answer, it is a hang, which is why it shows up in production as a pinned core rather than as a failed assertion.

Clearing the lowest set bit, and why it always terminates

The better loop does not shift at all:

int countBits(int n) {
    int count = 0;
    while (n != 0) {
        n &= n - 1;   // clears the lowest set bit, whatever the sign
        count++;
    }
    return count;
}

The identity is worth being able to derive rather than quote. Subtracting one from a value flips its lowest set bit to zero and turns every zero below it into a one, leaving all higher bits untouched. ANDing the original with that result therefore keeps every higher bit, clears the lowest set bit, and clears the newly created low ones. Each iteration removes exactly one set bit, so the loop runs once per set bit and terminates for any input at all.

Check it at the minimum value, which is the input that breaks naive sign handling. The minimum 32-bit value is the sign bit alone. Subtracting one gives the maximum positive value, all ones below the sign bit and a zero at the top. The AND of the two is zero, so the loop performs one iteration and returns 1, which is correct. Notice that this version never negates the input, so it never has to reason about the fact that the minimum value has no positive counterpart.

Which cost you are actually quoting

Both loops are constant time for a fixed width, which is a true but useless statement, so give the useful one. The shifting version runs in a number of iterations proportional to the position of the highest set bit. The clearing version runs once per set bit, so it is faster on sparse values and identical on the highest-bit-only case, and slower on nothing. For a dense value both do 32 iterations.

In real code you should call the library. Java exposes Integer.bitCount, and on hardware that has a population-count instruction the JIT can compile it to that single instruction, which no hand-written loop will match. Saying this unprompted signals that you know the difference between demonstrating you can derive the loop and recommending it. The reason interviewers still ask for the loop is that the derivation is where two's complement, shift semantics and range boundaries all show up at once.

What this failure looks like in the wild

In 1996, the first flight of Ariane 5 was lost because inertial reference software reused from Ariane 4 converted a 64-bit floating-point value into a 16-bit integer, and the larger trajectory values of the new vehicle overflowed the conversion. It is the standard reference for why width and range matter as much as the operation itself: the code was correct for the range it had been written against, and nothing in the new range was checked. Any answer involving packing, masking or fixed-width arithmetic should say what happens at the top of the range.

The two inputs worth checking on any bit-level routine are minus 1 and the minimum value; between them they catch sign extension, negation overflow and off-by-one width assumptions.