反向位程序逻辑不清楚

Question

我被要求编写一个程序来反转给定 32 位无符号整数的位。

比如输入43261596，输出应该是964176192（输入的二进制是00000010100101000001111010011100，取反后输出是00111001011110000010100101000000，十进制等于61=19324）[7]

我写了下面的程序：

class Solution:
    def reverseBits(self, n: int) -> int:
        
        binary = ""
        
        for i in range(32):
            binary = binary + str(n%2)
            n = n//2
        
        return int(binary,2)

提交后，我们收到了这个答案和一个替代解决方案 'claimed to be more time ans space efficient'。这是另一种选择：

class Solution:
    def reverseBits(self, n: int) -> int:
        
        if (n == 0):
            return 0
    
        result = 0
        for i in range(32):
            result <<= 1
            if ((n & 1) == 1):
                result +=1
            n >>= 1
            
        return result

他们提供的逻辑是 left/right 移位。

我完全不知道移位到 left/right 如何帮助反转十进制整数的位。为了进一步澄清，我自己写了这个片段：

a = 9
print(a>>1,a<<1)

输出分别是4和18（整数减半和加倍）。

但是这个概念如何有助于反转整数位？还有为什么这被认为比我的解决方案花费更多的时间和 space 效率？请帮忙。

Answer 1

移位类似于您的字符串连接，binary = binary + str(n%2) 有效地将已经存在的字符向左移动一个位置（类似于 result <<= 1）。由于对于移位方法，这将在末尾添加一个 0，如果当前 n 的最后一个二进制数字是 [=13，他们需要选择将值增加 1 =]（result += 1）。然后 n >>= 1 与 n //= 2 相同。

第二种方法基本上需要 result 额外的 32 位（至少理论上是这样），而字符串方法将以 32 个字符的字符串结束，它使用大约 32 个字节。整数运算也可能比字符串运算更快。

反向位程序逻辑不清楚

Reverse bits program logic not clear

python

reverse

bit