Python中的按位取反操作（Bitwise Not），不考虑二进制补码。

Question

我需要在Python中执行一个“~”操作，但不考虑2的补码。我通过使用XOR来完成了这个操作，你知道另一种更高效的方法吗？

a = 0b101
b = 0b10101

print bin(a ^ (2 ** a.bit_length() - 1)) #0b10
print bin(b ^ (2 ** b.bit_length() - 1)) #0b1010

- Leandro Moreira

---

请问为什么？可能是bin表示法让您感到困惑。~确实会反转位，但它只是反转了无限数量的位，因此无法以文本形式表示。 因此，bin对-进行了一些处理以使其正常工作，但最终隐藏了所有位都被反转的事实。 - Veedrac

如果这是一个虚拟机，你可能知道寄存器的宽度，因此可以通过将表达式硬编码为a ^ 0xFFFF来简化代码。 - Bill Lynch

(1 << b.bit_length() - 1) 比 (2 ** b.bit_length() - 1) 更快 - 如果可以的话，硬编码一个掩码而不是调用 bit_length。 - roippi

@roippi 我尝试执行 print bin(1 << b.bit_length() - 1)，但输出结果为 0b10000。 - Leandro Moreira

我错过了一些括号，应该是 ((1 << b.bit_length()) - 1)。 - roippi

Answer 1

这正是~所做的事情。棘手的部分是Python拥有无限长度的整数，因此当你反转一个数时，它会被符号扩展，至少在概念上是带有无限数量的1。这意味着你会得到负数。

>>> bin(~0b101)
'-0b110'
>>> bin(~0b10101)
'-0b10110'

要将这些转换为无符号数字，您需要确定关心多少位。也许您正在使用8位字节。然后，您可以将它们与一个字节的1位值AND：

>>> bin(~0b101 & 0xFF)
'0b11111010'
>>> bin(~0b10101 & 0xFF)
'0b11101010'

如果你想匹配输入数字的确切位长度，那么你的解决方案是合理的。为了提高效率，你可以将指数换成左移操作。使用~和&可能会更清晰，而不是使用^。

>>> bin(~a & ((1 << a.bit_length()) - 1))
'0b10'
>>> bin(~b & ((1 << b.bit_length()) - 1))
'0b1010'

我怀疑像& 0xFFFF这样的硬编码掩码将是实际上正确的解决方案。我想不出一个好的真实世界用例来使用基于bit_length()的答案。

- John Kugelman

---

谢谢，你知道 bit_length 是使用数学还是字符串操作吗？ - Leandro Moreira

bit_length 不适用于字符串。 - simonzack

在CPython上，bit_length 函数的时间复杂度大致是常数级别的，并且似乎非常快，因此我认为它只是返回一个内部缓存的值。 - Veedrac

你是对的，一个简单的 ~b & 0xFFFF 就解决了问题。https://github.com/leandromoreira/python_chip16/commit/319063e771d162ae53cc962a76f6a6ae60037f05 - Leandro Moreira

Answer 2

另一种方式，尽管有些人（包括我自己）可能会质疑它是否更好，但是：

tbl = str.maketrans("01","10")

int(bin(42)[2:].translate(tbl),2)

第一部分只是设置了一个翻译表，用于反转字符串中的1和0位。

第二部分获取二进制表示形式（42 -> 0b101010），去掉前面的0b，并通过翻译反转位。然后，您只需使用int(,2)将该二进制字符串转换回数字即可。

---

如果您可以将其限制在特定宽度而不是使用数字本身的宽度，那么这只是一个简单的问题（以32位为例）：

val = val ^ 0xffff

- paxdiablo