python - Get the bit number that differs between two (binary) numbers

Question

I have two numbers (binary or not, does not play any role) which differ in just one bit, e.g. (pseudocode)

a = 11111111
b = 11011111

I want a simple python function that returns the bit position that differs ('5' in the given example, when seen from right to left). My solution would be (python)

math.log(abs(a-b))/math.log(2)

but I wonder if there is a more elegant way to do this (without using floats etc.).

Thanks Alex

score 7 · Accepted Answer

バイナリ排他を使用できます：

a = 0b11111111
b = 0b11011111

diff = a^b  # 0b100000
diff.bit_length()-1 # 5 (the first position (backwards) which differs, 0 if a==b )

score 0 · Accepted Answer

Without using bitwise operations you could do something like this:

In [1]: def difbit(a, b):
   ...:     if a == b: return None
   ...:     i = 0
   ...:     while a%2 == b%2:
   ...:         i += 1
   ...:         a //= 2
   ...:         b //= 2
   ...:     return i
   ...: 

In [2]: difbit(0b11111111, 0b11011111)
Out[2]: 5

score 0 · Accepted Answer

unless i am missing something...

this should work:

>>> def find_bit(a,b):
    a = a[::-1]
    b = b[::-1]
    for i in xrange(len(a)):
        if a[i] != b[i]:
            return i
    return None

>>> a = "11111111"
>>> b = "11011111"
>>> find_bit(a,b)
5

maybe not so elegant, but its easy to understand, and it gets the job done.

score 0 · Accepted Answer

Using (a^b).bit_length()-1 is perfect for numbers which have only one difference bit. EX:

a = 1000000
b = 1000001
(a^b).bit_length()-1
Output: 0

But for numbers which have multiple difference bits, it gives the index of left most difference bit. EX:

a = 111111111111111111111111111111
b = 111111110111011111111111111111
c = a^b   # 1000100000000000000000
c.bit_length()-1
Output: 21  # Instead of 17. 21 is the left most difference bit

So to solve this problem we need to isolate the right most set bit and then get its index. Thus, using ((a^b) & (-(a^b))).bit_length()-1 works best for all inputs:

c = (a^b) & (-(a^b))   # 100000000000000000 - Isolates the rightmost set bit
c.bit_length()-1
Output: 17
(a^b) & (-(a^b))).bit_length()-1
Output: 17

Learn about isolating right most set bit from here

python - Get the bit number that differs between two (binary) numbers

4 に答える 4

Related

Reference