反转Python整数的位

问题描述 投票：0回答：14

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

65 → 01000001 → 10000010 → 130

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

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

步骤#2和步骤3看起来非常简单（参见this和this所以与步骤#2相关的问题），但我陷入了步骤#1。步骤 #1 的问题是检索填充零的完整十进制表示形式（即 65 = 01000001，而不是 1000001）。

我四处寻找，但似乎什么也没找到。

python integer bit-manipulation
14个回答
67
投票
int('{:08b}'.format(n)[::-1], 2)

您可以指定任何填充长度来代替 8。如果您想要真正喜欢，

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

允许您以编程方式指定宽度。

16
投票

如果您追求更快的速度，您可以使用中描述的技术 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
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))
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
)。

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))
3
投票

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

如果你想按照这个解决方案来解决反转问题，你只需要找到合适的

numbits
。您可以手动指定它，也可以使用 
n
 计算表示整数 
n.bit_length() 所需的位数（Python 2.7 和 3.1 中的新功能）。



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

    

      

      
      
      

      

        

          

            

              
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


    

      

      
      
      

      

        

          

            

              
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]


    

      

      
      
      

      

        

          

            

              
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


    



      

      
      
      

      

        

          

            

              
2
投票

              
            

          

        

        


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


    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        



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))


    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


num = int(input())

while num > 0:
  reminder = num % 2
  print(f'{str(reminder)}', end = '')
  num = int(num / 2)


    



      

      
      
      

      

        

          

            

              
0
投票

              
            

          

        

        


@measure
def rev03(n):
    b = ((n * 0x0802 & 0x22110) | (n * 0x8020 & 0x88440)) * 0x10101 >> 16
    return b & 255



如果你坚持使用字符串，那就是这个：


@measure
def rev01(n):
    b = bin(n)
    rev = b[-1:1:-1]
    rev = rev + (8 - len(rev))*'0'
    return int(rev, 2)



我使用了以下装饰器：


def measure(f):
    def wrapper(*args, **kwargs):
        start = time.time_ns()
        for i in range(100000):
            n = f(*args, **kwargs)
        end = time.time_ns()
        print("time(ns) = {}\n", end - start)
        return n

    return wrapper



祝评价愉快！

    





      

      
      
      

      

        

          

            

              
-1
投票

              
            

          

        

        


一行，它会自动转到顶部。 （编辑：使用 zfill 或 rjust 获得固定宽度 - 见下文）


>>> x = 0b1011000
>>> bin(x)[:1:-1]
'0001101'
>>> x = 0b100
>>> bin(x)[:1:-1]
'001'



 文本转换前面的“0b”被 [:1:-1] 中的“1”删除，在反转（通过 -1）后，自动添加 1（叹息，范围是 
真的
很奇怪）在被用作开始点而不是结束之前。
你需要在前面进行零填充以获得固定宽度的反转，但即使在那里 [:1:-1] 仍然会进行自动长度检测


zfill 完成这项工作，但您需要从 bin() 中分离出“0b”
首先，
then
 zfill，then反转（然后转换为int）
length=10
bin(x)[2:].zfill(length)[::-1]
int(bin(x)[2:].zfill(length)[::-1],2)



使用ljust：


bin(x)[:1:-1].ljust(length, '0')



奇怪的是，虽然时间更长，但我发现我更清晰了。

    



      

      
    

  

  

    
最新问题


  





  

    © www.soinside.com 2019 - 2024. All rights reserved.