Which modification to the Brian Kernighan's bit counting approach correctly handles this scenario?
hard🎤 Interviewer Follow-up Q15 of Q15
Bit Manipulation - Counting Bits (0 to N)
Suppose you want to count the number of set bits for all integers from 0 to n, but now n can be negative as well (e.g., from -n to n). Which modification to the Brian Kernighan's bit counting approach correctly handles this scenario?
AApply the same algorithm directly to negative numbers since bitwise operations work the same.
BSkip negative numbers because bit counting is undefined for them.
CConvert negative numbers to their two's complement 32-bit unsigned representation before counting bits.
DUse string conversion of the absolute value of negative numbers and count '1's.
Step-by-Step Solution
Solution:
Step 1: Understand bit representation of negatives
Negative integers are represented in two's complement form, so counting bits requires interpreting them as unsigned 32-bit integers.
Step 2: Modify algorithm accordingly
Convert negative numbers to their 32-bit unsigned equivalent before applying Kernighan's trick to count set bits correctly.
Final Answer:
Option C -> Option C
Quick Check:
Two's complement conversion ensures correct bit counting for negatives [OK]
