Python整数的位反转

Question

Python整数的位反转

46

给定一个十进制整数（例如65），如何在Python中反转底层位？即执行以下操作：

65 → 01000001 → 10000010 → 130

看起来这个任务可以分成三步:

将十进制整数转换为二进制表示
反转位
再次转换为十进制

第2和第3步似乎非常简单（参见与步骤2相关的此问题和此问题），但我卡在了第1步。问题在于如何获取带有零填充的完整十进制表示（即65 = 01000001，而不是1000001）。

我搜索了一下，但好像找不到任何有用的东西。

- David Chouinard

2

对于第一步，您可以使用str(bin(65))[2:].zfill(8)。现在懒得再深入研究了。但是您应该按照larsmans的建议去做。 - BrtH

第一步的问题在于检索具有填充零的完整十进制表示（即65 = 01000001，而不是1000001）。为什么应该是01000001而不是1000001？为什么不应该是32位的00000000000000000000000001000001或任意其他位数呢？ - Karl Knechtel

13个回答

15

如果您想获得更快的速度，可以使用在http://leetcode.com/2011/08/reverse-bits.html中描述的技术。

def reverse_mask(x):
    x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1)
    x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2)
    x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4)
    x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8)
    x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16)
    return x

- Bruce

请注意：该链接已失效。此函数是否仅限于整数，还是可以在大数字类型上使用？ - Daniel Henry

1

由于链接已经失效，您可以在此处找到相同的过程，并提供更多信息：https://dev59.com/CHE85IYBdhLWcg3wzm5p#30002555 - charelf

11

最好的方法是逐位移位操作。

def reverse_Bits(n, no_of_bits):
    result = 0
    for i in range(no_of_bits):
        result <<= 1
        result |= n & 1
        n >>= 1
    return result
# for example we reverse 12 i.e 1100 which is 4 bits long
print(reverse_Bits(12,4))

- Sudip Ghimire

8

def reverse_bit(num):
    result = 0
    while num:
        result = (result << 1) + (num & 1)
        num >>= 1
    return result

其实在Python中，我们不需要将整数转换成二进制，因为整数本质上就是二进制的。

反转的思想就像对整数进行空间内的反转一样。

def reverse_int(x):
    result = 0
    pos_x = abs(x)
    while pos_x:
        result = result * 10 + pos_x % 10
        pos_x /= 10
    return result if x >= 0 else (-1) * result

对于每个循环，原始数字会去掉最右边的位（二进制）。当新位被添加时，在下一个循环中我们获取该最右位并乘以2（<<1）。

- Jay Wong

2

你必须考虑要反转的位数。例如，你想要反转一个字节中的位。你期望0x1会被翻译成0x80（0b00000001 -> 0b10000000）。但是使用当前的实现，你仍然会得到输出0x1。 - rusxg

3

您可以使用移位和掩码来测试数字的第i位。例如，65的第6位是(65 >> 6) & 1。您可以通过将1向左移相应次数来类似地设置一个位。这些见解为您提供了以下代码（将x在'n'位字段中反转）：

def reverse(x, n):
    result = 0
    for i in xrange(n):
        if (x >> i) & 1: result |= 1 << (n - 1 - i)
    return result

print bin(reverse(65, 8))

- Paul Hankin

3

没有必要也没有办法“将十进制整数转换为二进制表示”。所有Python整数都以二进制表示；只是在打印时为了方便而转换为十进制。

如果您想遵循this solution的反转问题，您只需要找到适当的numbits。您可以手动指定此选项，也可以使用n.bit_length()（在Python 2.7和3.1中新增）计算表示整数n所需的位数。

但是，对于65，这将给您7，因为没有理由认为65需要更多的位数。（您可能希望将其四舍五入到最接近8的倍数...）

- Fred Foo

并不完全正确，因为您可以获取表示位的字符串（bin(n)或'{:b}'.format(n)）。此外，您可以使用.bit_length()来查找表示数字所需的确切位数。 - nneonneo

@nneonneo：鉴于提供的链接，我认为OP想要处理整数本身而不是字符串表示。但感谢您提供bit_length方法，我之前不知道。 - Fred Foo

3

你也可以使用查找表（可以使用上述方法之一生成一次）：

LUT = [0, 128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240,
       8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120,
       248, 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180,
       116, 244, 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60,
       188, 124, 252, 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50,
       178, 114, 242, 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218,
       58, 186, 122, 250, 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214,
       54, 182, 118, 246, 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94,
       222, 62, 190, 126, 254, 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81,
       209, 49, 177, 113, 241, 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89,
       217, 57, 185, 121, 249, 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85,
       213, 53, 181, 117, 245, 13, 141, 77, 205, 45, 173, 109, 237, 29, 157,
       93, 221, 61, 189, 125, 253, 3, 131, 67, 195, 35, 163, 99, 227, 19, 147,
       83, 211, 51, 179, 115, 243, 11, 139, 75, 203, 43, 171, 107, 235, 27,
       155, 91, 219, 59, 187, 123, 251, 7, 135, 71, 199, 39, 167, 103, 231, 23,
       151, 87, 215, 55, 183, 119, 247, 15, 143, 79, 207, 47, 175, 111, 239,
       31, 159, 95, 223, 63, 191, 127, 255]

def reverseBitOrder(uint8):
    return LUT[uint8]

- theb33k

3

一个效率低下但简洁的方法，适用于Python 2.7和Python 3：

def bit_reverse(i, n):
    return int(format(i, '0%db' % n)[::-1], 2)

以你的例子为例：

>>> bit_reverse(65, 8)
130

- personal_cloud

2

经常需要对数字数组进行此操作，而不是单个数字。

为了提高速度，最好使用NumPy数组。

有两种解决方案。

第一种方案比第二种方案快x1.34。

import numpy as np
def reverse_bits_faster(x):
  x = np.array(x)
  bits_num = x.dtype.itemsize * 8
  # because bitwise operations may change number of bits in numbers
  one_array = np.array([1], x.dtype)
  # switch bits in-place
  for i in range(int(bits_num / 2)):
    right_bit_mask = (one_array << i)[0]
    left_bit = (x & right_bit_mask) << (bits_num - 1 - i * 2)
    left_bit_mask = (one_array << (bits_num - 1 - i))[0]
    right_bit = (x & left_bit_mask) >> (bits_num - 1 - i * 2)
    moved_bits_mask = left_bit_mask | right_bit_mask
    x = x & (~moved_bits_mask) | left_bit | right_bit
  return x

更慢，但更易于理解（基于Sudip Ghimire提出的解决方案）：

import numpy as np
def reverse_bits(x):
  x = np.array(x)
  bits_num = x.dtype.itemsize * 8
  x_reversed = np.zeros_like(x)
  for i in range(bits_num):
    x_reversed = (x_reversed << 1) | x & 1
    x >>= 1
  return x_reversed

- Sof

2

你所需要的就是numpy。

import numpy as np
x = np.uint8(65)
print( np.packbits(np.unpackbits(x, bitorder='little')) )

性能:

py -3 -m timeit "import numpy as np; import timeit; x=np.uint8(65); timeit.timeit(lambda: np.packbits(np.unpackbits(x, bitorder='little')), number=100000)"
1 loop, best of 5: 326 msec per loop

- kimstik

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- nneonneo · Accepted Answer

67

int('{:08b}'.format(n)[::-1], 2)

您可以在8的位置指定任何填充长度。如果您想变得更高级，

b = '{:0{width}b}'.format(n, width=width)
int(b[::-1], 2)

这让您可以以编程方式指定宽度。

- nneonneo

2

我需要将格式字符串更改为'{:08b}'以按规定工作。 - Shane Holloway

啊，是的，他想要填充零。我会进行修正。 - nneonneo

如果我执行 int('{:b}'.format(65)[::-1], 2)，输出结果只是 65。但是使用 {:08b} 而不是 {:b} 就可以得到正确的结果，所以这是一个优雅的解决方案，加一分。 - BrtH

@nneonneo和Shane，感谢你们两位。我查阅了format()的相关资料，这确实很有道理。毫无疑问，这是最优雅的解决方案。 - David Chouinard

1

这是列表切片，它会导致以相反的顺序迭代列表。 - Emilien

显示剩余2条评论