计算 python 中两个带符号的 64 位整数之间的 XOR 时出现意外行为

Question

我需要计算两个整数之间的汉明距离，方法是计算它们的二进制表示之间的不同位数。

这是我为此目的使用的函数：

def hamming(a, b):
    # compute and return the Hamming distance between the integers
    return bin(int(a) ^ int(b)).count("1")

我开始对这个函数进行一些简单的测试以确保它能正常工作，但我几乎立即发现它不能正常工作，我试图了解原因。

我用这两个数字测试了函数：

a = -1704441252336819740
b = -1704441252336819741

python给出的这些数字的二进制表示是：

bin(a): -0b10111 10100111 01100100 01001001 11011010 00001110 11011110 00011100 
bin(b): -0b10111 10100111 01100100 01001001 11011010 00001110 11011110 00011101

如您所见，它们的二进制表示除第一个数字外是相同的，因此汉明距离应为 1。但是，函数的 returned 汉明距离是 3，我似乎不明白为什么。

当我将这两个数字之间的 XOR 计算为 a ^ b returns 7（因此计算 3 个“1”位）时出现问题，而我期望它是 return 1（并计数 1 个“1”位）。

我认为这与 XOR 值似乎被存储为具有最少可能位数的无符号整数这一事实有关，而我需要将其存储为

我怎么会误解 XOR 运算符以及如何更改我的函数以按我希望的方式工作？

Answer 1

实际上，误导的是bin函数：
它不显示存储的实际二进制值，而是显示 |x| （绝对值）并在其前面打印负号表示负数。

但是，这并不是实际存储值的方式。

XOR 对存储在 two's compliment 中的实际二进制值进行运算，这就是为什么您得到比预期更大的位差的原因。

作为一个简单的例子，让我们取两个 4 位数：

-10 = 0b0110
-11 = 0b0101
  ^ = 0b0011

如您所见，在这种表示中，这两个数字之间有两位的差异，而如果它们是正数，则只有一位的差异。

计算 python 中两个带符号的 64 位整数之间的 XOR 时出现意外行为

Unexpected behavior when computing the XOR between two signed 64-bit integers in python

python

bitwise-operators

xor