Differing Bit Count
Problem
Write two non-negative whole numbers in binary, one above the other and aligned on the right. Count the positions where their binary digits disagree. Missing digits on the left of the shorter number count as zeros.
Examples
Input: a = 1, b = 4
Output: 2
Why: 001 against 100 disagrees in the first and last positionsInput: a = 7, b = 10
Output: 3
Why: 0111 against 1010 disagrees everywhere except the second position from the rightInput: a = 5, b = 5
Output: 0
Why: edge case, a number never disagrees with itselfHints
0 / 3
Comparing the two numbers digit by digit works, but a single bitwise operation can do all the comparisons at once.
There is an operator that produces a 1 exactly where two digits differ and a 0 where they agree. After applying it, the question becomes a counting one.
XOR the two numbers, then count the ones in the result. A fast way to count is to repeatedly clear the lowest one with the value ANDed with itself minus one, adding one to a counter each time until the value reaches zero.
Solution
XOR sets a bit exactly where its inputs disagree, so the answer is simply the number of ones in a XOR b. Counting them with the clear-the-lowest-one trick costs one loop round per one rather than per digit, because subtracting one flips the lowest one and everything below it, and the AND then wipes that one out. The loop therefore runs as many times as the answer. Time is O(number of differing bits), at most O(log of the larger input), and space is O(1).
def differing_bits(a, b):
x = a ^ b # a 1 wherever the two numbers disagree
count = 0
while x:
x &= x - 1 # clear the lowest remaining 1
count += 1
return count
print(differing_bits(1, 4)) # -> 2
print(differing_bits(7, 10)) # -> 3
print(differing_bits(5, 5)) # -> 0Stuck on the idea rather than the code? Counting Set Bits covers it.