LeetCode第190题_颠倒二进制位

LeetCode 第190题：颠倒二进制位

题目描述

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

提示：

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

难度

简单

题目链接

点击在LeetCode中查看题目

示例

示例 1:

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

示例 2:

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

提示

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

进阶

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

解题思路

方法一：逐位颠倒

最直接的方法是逐位处理，从右到左依次取出原始数字的每一位，然后从左到右构建结果数字。

关键点：

1. 遍历原始数字的32位
2. 对于每一位，判断其值（0或1）
3. 将结果数字左移一位，为新的位腾出空间
4. 如果原始数字当前位为1，则将结果数字的最低位设置为1
5. 原始数字右移一位，处理下一位

时间复杂度：O(1)，因为我们处理的是32位整数，循环次数是固定的
空间复杂度：O(1)，只需要常数额外空间

方法二：分治法（位运算优化）

我们可以使用分治法和位运算来优化算法。通过交换不同位置的位，逐步将整个二进制串颠倒。

关键点：

1. 先交换相邻的1位（相当于16对交换）
2. 然后交换相邻的2位（相当于8对交换）
3. 然后交换相邻的4位（相当于4对交换）
4. 然后交换相邻的8位（相当于2对交换）
5. 最后交换相邻的16位（相当于1对交换）

时间复杂度：O(1)，因为操作次数是固定的
空间复杂度：O(1)，只需要常数额外空间

方法三：查表法

如果需要多次调用这个函数，可以使用查表法优化。我们可以预先计算所有8位二进制数字的颠倒结果，然后在运行时直接查表。

关键点：

1. 将32位整数分成4个8位块
2. 对每个8位块查表获取其颠倒结果
3. 将4个颠倒后的8位块按照颠倒的顺序组合起来

时间复杂度：O(1)，只需要常数次操作
空间复杂度：O(1)，预计算表的大小是固定的（256个条目）

代码实现

C# 实现

方法一：逐位颠倒

public class Solution {
    public uint reverseBits(uint n) {
        uint result = 0;
        
        // 遍历32位
        for (int i = 0; i < 32; i++) {
            // 将结果左移一位，为新的位腾出空间
            result <<= 1;
            
            // 如果n的最低位是1，则将结果的最低位设置为1
            if ((n & 1) == 1) {
                result |= 1;
            }
            
            // 将n右移一位，处理下一位
            n >>= 1;
        }
        
        return result;
    }
}

方法二：分治法

public class Solution {
    public uint reverseBits(uint n) {
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
        n = (n >> 16) | (n << 16);
        
        return n;
    }
}

方法三：查表法

public class Solution {
    // 预计算表
    private readonly uint[] reversedByte = new uint[256];
    
    public Solution() {
        // 初始化表
        for (int i = 0; i < 256; i++) {
            uint reversed = 0;
            for (int j = 0; j < 8; j++) {
                reversed <<= 1;
                reversed |= (uint)(i >> j) & 1;
            }
            reversedByte[i] = reversed;
        }
    }
    
    public uint reverseBits(uint n) {
        uint result = 0;
        
        // 处理四个字节
        result |= reversedByte[n & 0xFF] << 24;
        result |= reversedByte[(n >> 8) & 0xFF] << 16;
        result |= reversedByte[(n >> 16) & 0xFF] << 8;
        result |= reversedByte[(n >> 24) & 0xFF];
        
        return result;
    }
}

Python 实现

方法一：逐位颠倒

class Solution:
    def reverseBits(self, n: int) -> int:
        result = 0
        
        # 遍历32位
        for i in range(32):
            # 将结果左移一位，为新的位腾出空间
            result <<= 1
            
            # 如果n的最低位是1，则将结果的最低位设置为1
            if n & 1:
                result |= 1
                
            # 将n右移一位，处理下一位
            n >>= 1
            
        return result

方法二：分治法

class Solution:
    def reverseBits(self, n: int) -> int:
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1)
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2)
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4)
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8)
        n = (n >> 16) | (n << 16)
        
        # 确保结果是32位无符号整数
        return n & 0xFFFFFFFF

方法三：查表法

class Solution:
    def __init__(self):
        # 初始化表
        self.reversed_byte = [0] * 256
        for i in range(256):
            self.reversed_byte[i] = self._reverse_byte(i)
    
    def _reverse_byte(self, byte):
        reversed_byte = 0
        for i in range(8):
            reversed_byte <<= 1
            reversed_byte |= (byte >> i) & 1
        return reversed_byte
    
    def reverseBits(self, n: int) -> int:
        result = 0
        
        # 处理四个字节
        result |= self.reversed_byte[n & 0xFF] << 24
        result |= self.reversed_byte[(n >> 8) & 0xFF] << 16
        result |= self.reversed_byte[(n >> 16) & 0xFF] << 8
        result |= self.reversed_byte[(n >> 24) & 0xFF]
        
        return result

C++ 实现

方法一：逐位颠倒

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        
        // 遍历32位
        for (int i = 0; i < 32; i++) {
            // 将结果左移一位，为新的位腾出空间
            result <<= 1;
            
            // 如果n的最低位是1，则将结果的最低位设置为1
            if (n & 1) {
                result |= 1;
            }
            
            // 将n右移一位，处理下一位
            n >>= 1;
        }
        
        return result;
    }
};

方法二：分治法

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        n = ((n & 0xAAAAAAAA) >> 1) | ((n & 0x55555555) << 1);
        n = ((n & 0xCCCCCCCC) >> 2) | ((n & 0x33333333) << 2);
        n = ((n & 0xF0F0F0F0) >> 4) | ((n & 0x0F0F0F0F) << 4);
        n = ((n & 0xFF00FF00) >> 8) | ((n & 0x00FF00FF) << 8);
        n = (n >> 16) | (n << 16);
        
        return n;
    }
};

方法三：查表法

class Solution {
private:
    // 预计算表
    uint32_t reversedByte[256];
    
    // 初始化表
    void initTable() {
        for (int i = 0; i < 256; i++) {
            uint32_t reversed = 0;
            for (int j = 0; j < 8; j++) {
                reversed <<= 1;
                reversed |= (i >> j) & 1;
            }
            reversedByte[i] = reversed;
        }
    }
    
public:
    Solution() {
        initTable();
    }
    
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0;
        
        // 处理四个字节
        result |= reversedByte[n & 0xFF] << 24;
        result |= reversedByte[(n >> 8) & 0xFF] << 16;
        result |= reversedByte[(n >> 16) & 0xFF] << 8;
        result |= reversedByte[(n >> 24) & 0xFF];
        
        return result;
    }
};

性能分析

各语言实现的性能对比：

补充说明

代码亮点

1. 方法一简单直观，容易理解和实现
2. 方法二利用位运算和分治思想，简化了操作步骤
3. 方法三通过预计算和查表优化，适合多次调用的场景
4. 所有方法都充分考虑了32位整数处理的特点

分治法中的位运算解释

分治法中使用的掩码和移位操作可能看起来有些复杂，这里详细解释一下：

1. 0xAAAAAAAA 表示二进制中所有偶数位为1（从0开始计数），0x55555555 表示所有奇数位为1
2. 0xCCCCCCCC 表示每4位中高2位为1，0x33333333 表示每4位中低2位为1
3. 0xF0F0F0F0 表示每8位中高4位为1，0x0F0F0F0F 表示每8位中低4位为1
4. 0xFF00FF00 表示每16位中高8位为1，0x00FF00FF 表示每16位中低8位为1

通过这种方式，我们可以在不使用循环的情况下，利用分治思想高效地完成位颠倒操作。

常见错误

1. 没有考虑到无符号整数和有符号整数的区别，导致错误的位运算结果
2. 在分治法中使用了错误的掩码或位移操作
3. 在查表法中没有正确初始化预计算表
4. 忘记处理32位整数的边界情况

相关题目

• 7. 整数反转
• 191. 位1的个数
• 338. 比特位计数