python - 在 Python 中实现位交换黑客

Question

给定一个字节 b 8 位，以下公式返回 b 的位“交换”(交换 0 和 7，交换 1 和 6，等等):

(b * 0x0202020202 & 0x010884422010) % 1023

当我有一个实现这个 hack 的函数时，即

def reverseBits(b):
    return (b * 0x0202020202 & 0x010884422010) % 1023

然后我得到一个溢出:

OverflowError: cannot fit 'long' into an index-sized integer

如何在 Python 中实现位交换 hack？

Answer 1

这似乎按您的预期工作:

def sb(b):
    return (b * 0x0202020202 & 0x010884422010) % 1023

def harness(i):
    print '{:4}: {} -> {}'.format(i,bin(i)[2:].zfill(8),bin(sb(i))[2:].zfill(8))    

for i in range(256):
    harness(i)

打印:

   0: 00000000 -> 00000000
   1: 00000001 -> 10000000
   2: 00000010 -> 01000000
   3: 00000011 -> 11000000
   4: 00000100 -> 00100000
   5: 00000101 -> 10100000
   6: 00000110 -> 01100000
   ...
 248: 11111000 -> 00011111
 249: 11111001 -> 10011111
 250: 11111010 -> 01011111
 251: 11111011 -> 11011111
 252: 11111100 -> 00111111
 253: 11111101 -> 10111111
 254: 11111110 -> 01111111
 255: 11111111 -> 11111111

这个算法(和其他算法)被发现 here 。如前所述，此方法仅适用于 BYTE，因此您需要使用另一种方法来处理较大的位模式。

编辑

顺便说一句:您可以通过使用字符串操作来进行位反转，而不必担心溢出或数学问题以及更大的位域:

>>> w=32
>>> s=bin(1234567)[2:].zfill(w)
>>> rb=s[::-1]
>>> s
'00000000000100101101011010000111'
>>> rb
'11100001011010110100100000000000'

然后以这种方式转换回 int :

int(rb,2)