The following function determines the number of bits you would need to flip to convert integer A to integer B. I have solved it by a different method, but when I read this solution I don't understand it. It clearly works, but my question is why?
def bit_swap_required(a: int, b: int) -> int:
count, c = 0, a ^ b
while c:
count, c = count + 1, c & (c - 1)
return count
I understand why we do a^b. It gives us a '1' at every place we need to flip. But, How does doing c & (c-1) repeatedly give you the EXACT number of '1's in the number?
c - 1 unsets the least significant bit in the binary representation of c and sets all the unset bits to the right of that bit.
When you binary and c - 1 with c you effectively unset all the bits to the right of the least significant set bit and also the least significant set bit. In other words the least significant set bit in c and everything to its right become zeros.
You count this as one, and rightly so. Because it was just one set bit fomr a ^ b.
Now, you continue this operation until c becomes zero and the number of operations is the number of set bits in c which is the number of different bits between a and b.
To give you an example for what c - 1 does to the binary representation of c:
c = 6, in binary 110
c-1 = 5, in binary 101
(c-1) & (c) = 110 & 101 = 100
The above is one iteration of the loop
Next iteration
c = 4, in binary 100
c-1 = 3, in binary 011
(c-1) & (c) = 100 & 101 = 0
The above successfully counts the number of set bits in 6.
This optimization helps you to improve the algorithm compared to when you right shift the number at each iteration and check whether the least significant bit is set. In the former case you operate in the number of positions where the most significant set bit is. Say for a power of 2 number, 2^7, you iterate 8 times until the number becomes zero. While with the optimized method you iterate according to the number of set bits. For 2^7 it would be just one iteration.