mediumCodingConceptEntryMidSenior
Count the set bits in a 32-bit integer. Now tell me what your loop does when I hand it a negative number.
4 min readUpdated 2026-08-15Target archetype: Big Tech, Enterprise Captive, Product Startup
Answer
Short answer
Shifting and masking works only if the shift does not sign-extend, so a signed right shift on a negative value never terminates. Either shift with the unsigned operator or clear the lowest set bit with n and n minus 1, which terminates for every input including the minimum value.
Was this answer helpful?
Likely follow-ups
- Count the set bits for every integer from 0 to n. Can you beat calling this n times?
- Return the index of the lowest set bit instead. What does n and minus n give you, and what does it give you at the minimum value?
- Do the same for a 64-bit value in a language where the default integer is 32 bits.
- Count the bits with no loop at all, using only masks, shifts and adds. What is the idea?
Related questions
- Every number in the array appears three times except one. Find the single number in O(1) extra space, and make sure it works for negatives.mediumAlso on bit-manipulation and twos-complement5 min
- Every value in an array appears twice except one. Find it, and tell me when bit tricks are worth reaching foreasyAlso on bit-manipulation5 min
- Assign n tasks to n workers at minimum cost, with n up to 20. Why a bitmask, and what does it cost?hardAlso on bit-manipulation4 min
- You need a random number from 1 to 6 and you wrote rand() % 6. What is wrong with that, and when does it stop being merely wrong and become a vulnerability?mediumSame kind of round: concept4 min