在 python 中循环位

Question

出于好奇，我看到了在字符串域中将对象的 id 转换为其散列的操作，而不是使用像 ^、| 这样的通常的按位操作， &, ~.

class A:
    pass

def my_hash(a):
    bits = format(id(a), '064b')
    rot4 = bits[-4:] + bits[:-4]
    n = int(rot4, 2)
    return n

for _ in xrange(10):
    a = A()
    print hash(a) == my_hash(a), hash(a), my_hash(a)

但是正如您在下面看到的，下面的函数有时并不正确。我错过了什么？

>>> run /tmp/thing.py
True 272331835 272331835
False -9223372036582443978 9223372037127107638
True 272331835 272331835
False -9223372036582443978 9223372037127107638
True 272331835 272331835
False -9223372036582443978 9223372037127107638
True 272331835 272331835
False -9223372036582443978 9223372037127107638
True 272331835 272331835
False -9223372036582443978 9223372037127107638

Answer 1

哈希生成一个有符号整数，您的代码生成一个无符号整数。

对于您的第一个错误结果，id(a) 值为 4357309288；那是 64 位的 0000000000000000000000000000000100000011101101110100001101101000。最后 4 位是 1000，将它们移动到开头给出 1000000000000000000000000000000000010000001110110111010000110110 的二进制值，当解释为 2's complement signed integer 时，它是 --9223372036582443978，因为第一位，符号位，设置为 1.

另一方面，

int(rot4, 2) 始终将输入解释为 无符号 无限长度整数，因此您得到的是 9223372037127107638。

Python 没有任何 'easy' 选项来将包含二进制数的字符串解释为带符号的整数，您可以使用 bitstring 库来轻松实现：

>>> from bitstring import Bits
>>> bits = Bits(int=4357309288, length=64)
>>> bits[-4:]
Bits('0x8')
>>> bits[-4:] + bits[:-4]
Bits('0x80000000103b7436')
>>> (bits[-4:] + bits[:-4]).int
-9223372036582443978L
>>> (bits[-4:] + bits[:-4]).uint
9223372037127107638L

.int和.uint分别给你一个有符号和无符号整数的解释。

使用 bitstring 我得到正确的输出：

>>> def my_hash(a):
...     bits = Bits(int=id(a), length=64)
...     return (bits[-4:] + bits[:-4]).int
...
>>> for _ in xrange(10):
...     a = A()
...     print hash(a) == my_hash(a), hash(a), my_hash(a)
...
True -9223372036585854145 -9223372036585854145
True 268921659 268921659
True -9223372036585854145 -9223372036585854145
True 268921659 268921659
True -9223372036585854145 -9223372036585854145
True 268921659 268921659
True -9223372036585854145 -9223372036585854145
True 268921659 268921659
True -9223372036585854145 -9223372036585854145
True 268921659 268921659

如果你想坚持使用标准库，使用this Stack Overflow answer给自己一个twos_comp()函数：

>>> twos_comp(9223372037127107638, 64)
-9223372036582443978L

你的函数将是：

def my_hash(a):
    bits = format(id(a), '064b')
    rot4 = bits[-4:] + bits[:-4]
    n = twos_comp(int(rot4, 2), 64)
    return n

在 python 中循环位

Rotate bits in python

python

hash

bit-manipulation

bit-shift