获取两个(二进制)数字之间不同的位号

Question

我有两个数字（二进制与否，不发挥任何作用），它们仅在一位上有所不同，例如（伪代码）

a = 11111111
b = 11011111

我想要一个简单的 python 函数，它返回不同的位位置（在给定的示例中，从右到左看时为"5"）。我的解决方案是（蟒蛇）

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

但我想知道是否有更优雅的方法可以做到这一点（不使用浮动等）。

谢谢 Alex

Answer 1

您可以使用二进制独占：

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

Answer 2

除非我错过了什么......

这应该有效：

>>> 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

也许不是那么优雅，但它很容易理解，并且可以完成工作。

Answer 3

如果不使用按位运算，您可以执行以下操作：

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

Answer 4

使用 (a^b).bit_length()-1 非常适合只有一个差分位的数字。前任：

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

但是对于具有多个差分位的数字，它给出了最左边差分位的索引。前任：

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

因此，为了解决这个问题，我们需要隔离正确的最设置位，然后获取其索引。因此，使用 ((a^b) & (-(a^b))).bit_length()-1 最适合所有输入：

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

从此处了解如何隔离最右边的设置位