Python Program to Count number of bits to be flipped to convert A to B

Problem: Write a function to determine the number of bits you would need to flip to convert integer A to integer B.

For Example,

Given A = 10 (or: 1010), B = 14 (or: 1110)

Output: 1

The solution is pretty straightforward. Remember, 1 XOR 0 = 1, and 0 XOR 1 = 1. We will follow exactly the same methodology here. Note it, if you perform A XOR B, you will get the number of 1s you need to flip (because each 1 in the XOR result represents a bit that is the difference between A and B.).

Visit Also: Find the next largest and previous numbers that has same number of 1 bits

Code

def bitSwapRequired(A, B):
    XOR = A^B

    count = 0
    while XOR:
        count += XOR & 1
        XOR >>= 1
    
    return count

if __name__ == "__main__":
    A = 4
    B = 14

    print("Bit required to flip: ", bitSwapRequired(A, B))

Output

Bit required to flip:  2

Time Complexity

Assuming, the number of bits N then,

Time Complexity: O(N)

Space Complexity: O(1), No extra spaces needed.