颠倒二进制位

难度: Easy

颠倒给定的 32 位无符号整数的二进制位。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数，你将如何优化你的算法？

Submission

运行时间: 20 ms

内存: 15.9 MB

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

Explain

该题解的思路是通过位运算来实现二进制位的颠倒。具体来说，使用一个循环来遍历输入整数的32个二进制位。在每次迭代中，通过与1进行位与运算来获取当前位的值，然后将结果左移一位，并将当前位的值加到结果中。同时，将输入整数右移一位，以便在下一次迭代中处理下一个二进制位。重复这个过程32次，最终得到颠倒后的二进制数。

时间复杂度: O(1)

空间复杂度: O(1)

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        for i in range(32):
            # 获取当前位的值
            t = n & 1
            # 将结果左移一位
            result = result << 1
            # 将当前位的值加到结果中
            result += t
            # 将输入整数右移一位
            n = n >> 1
        return result

Explore

在给定的算法中，通过32次迭代确保处理了整数的所有32位。在每次迭代中，都将输入整数的最低位（最右侧的位）提取出来，并将其添加到结果整数的最低位，然后将结果整数左移一位。这样，每次提取的位都被放置在结果整数的正确位置上，而结果整数的左移操作则确保了每个新添加的位都位于正确的颠倒位置。通过重复这个过程32次，可以确保所有位都被正确处理和颠倒。

在解题中使用了三种位运算操作：位与（AND）、左移和右移。1. 位与运算（`n & 1`）用于提取整数n的最低位（即最右侧的位），这是因为1在二进制中除了最低位为1外其余都是0，因此与任何数进行AND运算时只有最低位可能为1，其余位都将变为0。2. 左移运算（`result << 1`）用于将结果整数的所有位向左移动一位，这样可以为下一个即将添加的位腾出位置。3. 右移运算（`n >> 1`）用于将整数n的所有位向右移动一位，这样在下次迭代中可以处理n的下一位。这三个操作共同确保了二进制位的正确颠倒和提取。

`t = n & 1` 是位与运算的一个应用，它用于获取整数n的最低位的值。这个操作中，1的二进制表示为 000...0001（只有最低位是1），当与n进行AND运算时，只有n的最低位会影响结果，因为只有当n的最低位是1时，结果才为1（即1 AND 1 = 1），如果n的最低位是0，则结果为0（即0 AND 1 = 0）。因此，这个操作有效地提取出n的最低位，将其存储在变量t中。

将输入整数右移一位（`n = n >> 1`）的目的是为了在下一次迭代中处理下一个更高位的位。右移操作会将整数的所有位都向右移动一个位置，从而使原来的倒数第二位变成最低位。这使得在下一次迭代中可以使用同样的`n & 1`操作来提取出这个新的最低位。这样的移位保证了每次迭代都能顺序地处理整数的每一位，直到最高位。