36

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

65 → 01000001 → 10000010 → 130

看来这个任务可以分解为三个步骤：

  1. 将十进制整数转换为二进制表示
  2. 反转位
  3. 转换回十进制

第 2 步和第 3 步看起来很简单（请参阅与第 2 步相关的这个和这个SO 问题），但我被困在第 1 步。步骤 #1 的问题是检索完整的十进制表示并填充零（即 65 = 01000001，而不是 1000001）。

我四处寻找，但我似乎找不到任何东西。

4

10 回答 10

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

您可以指定任何填充长度来代替 8。如果您想变得非常花哨，

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

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

于 2012-10-01T22:26:51.363 回答
9

如果你追求更快的速度，你可以使用 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
于 2014-01-04T08:04:32.627 回答
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

对于每个循环，原始数字正在删除最右边的位（二进制）。当添加新位时，我们得到最右边的位并<<1在下一个循环中乘以 2 ( )。

于 2016-06-01T22:07:34.170 回答
8

最好的方法是逐位执行

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))
于 2018-05-30T05:03:45.997 回答
3

没有必要也没有办法“将十进制整数转换为二进制表示”。所有 Python 整数都表示为二进制；为方便起见，当您打印它们时，它们只是转换为十进制。

如果你想按照这个解决方案来解决反转问题，你只需要找到合适numbits的 . 您可以手动指定它，也可以计算表示整数所需的位数n（n.bit_length()Python 2.7 和 3.1 中的新功能）。

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

于 2012-10-01T22:24:01.003 回答
3

您可以使用移位和掩码测试数字的第 i 位。例如，65 的第 6 位是(65 >> 6) & 1. 您可以通过向右移动 1 的次数以类似的方式设置位。这些见解为您提供了这样的代码（在“n”位的字段中反转 x）。

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))
于 2014-01-04T08:23:13.357 回答
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
于 2018-12-29T09:18:38.973 回答
2

一种在 Python 2.7 和 Python 3 中都有效的低效但简洁的方法：

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

对于您的示例：

>>> bit_reverse(65, 8)
130
于 2019-10-27T00:17:35.040 回答
1

您还可以使用查找表（可以使用上述方法生成一次）：

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]
于 2020-06-17T14:09:48.577 回答
0

另一种方法是遍历两端的位并相互交换。这是我从 EPI python 书中学到的。

i = 0; j = 7
num = 230
print(bin(num))
while i<j:
    # Get the bits from both end iteratively
    if (x>>i)&1 != (x>>j)&1:
        # if the bits don't match swap them by creating a bit mask
        # and XOR it with the number 
        mask = (1<<i) | (1<<j)
        num ^= mask
    i += 1; j -= 1
print(bin(num))
于 2018-04-02T07:55:49.260 回答