获取两个（二进制）数字不同的位数

Question

我有两个数字（无论是二进制还是其他进制，都没有任何影响），它们只在一位上不同，例如（伪代码）

a = 11111111
b = 11011111

我需要一个简单的Python函数，该函数返回不同位的位置（在给定示例中为“5”，从右到左）。我的解决方案是（Python）

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

但我想知道有没有更优雅的方法来解决这个问题（而不使用浮动等）。

谢谢 Alex

- Alex

---

尝试使用按位异或（bitwise XOR）代替 abs(a-b)。 - LeeNeverGup

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 )

- Andy Hayden

---

使用(a^b).bit_length() - 1代替字符串长度。(适用于Python2.7+)。 - Bakuriu

一行代码的解决方案是最好的。谢谢！ - Alex

@Alex (a^b).bit_length()-1 :) @Alex (a^b).bit_length()-1 :) - Andy Hayden

Answer 2

使用(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

了解如何从这里隔离出最右边的设置位

- Noor Jahan Mukammel

---

我已经测试了我的答案的结果，它正常工作。 - Noor Jahan Mukammel

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

- Lev Levitsky

Answer 4

除非我漏掉了什么...

这应该可以工作：

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

可能不太优雅，但很容易理解，而且能完成任务。

- Inbar Rose