A control panel has up to 63 switches. Its state is stored as one non-negative integer: switch i is on when the digit worth 2^i in the binary form of the number is 1.
Write count_on(state: int) -> int that returns how many switches are on, i.e. how many 1 digits the binary form of state has.
count_on(13) # 3 (13 is 1101 in binary)
count_on(0) # 0
count_on(256) # 1 (100000000)
count_on(2**63 - 1) # 63
Constraints:
0 <= state <= 2^63 - 1.
Do it with integer operations only (no converting to a string). Aim for a loop that runs once per switch that is on, not once per digit.
Show hint
compare state with state - 1 in binary: the lowest 1 and everything after it flip. Combining the two can make exactly one 1 disappear per step.