面试经典算法题61-颠倒二进制位

LeetCode.190

问题描述

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

提示：

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

示例 1：

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

示例 2：

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

思路

1. 逐位翻转：从最低位到最高位，逐位翻转。可以通过位运算提取每一位，然后在结果中相应位置上进行设置。

2. 使用循环和位运算：

   • 将输入的整数 n 的每一位提取出来，并通过左移操作放到相应的位置上。

   • 使用掩码和位运算来提取和设置位。

具体步骤：

1. 初始化结果变量 result 为 0。

2. 使用一个循环从 0 运行到 31（因为我们处理的是 32 位整数）。

3. 在每次循环中：

   • 通过右移操作提取 n 的最低位。

   • 将提取的位通过左移操作放到相应的位置上。

   • 将提取的位加到 result 上。

   • 将 n 右移一位，以便在下一次循环中处理下一位。

4. 循环结束后，result 就是翻转后的整数。

参考代码

C++

#include <iostream>
using namespace std;

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t result = 0; // 初始化结果变量
        for (int i = 0; i < 32; ++i) {
            // 提取最低位
            uint32_t bit = n & 1;
            // 将提取的位左移到相应的位置
            result = (result << 1) | bit;
            // 右移 n，以处理下一位
            n >>= 1;
        }
        return result;
    }
};

int main() {
    Solution sol;
    uint32_t input1 = 0b00000010100101000001111010011100;
    uint32_t output1 = sol.reverseBits(input1);
    cout << "输入：n = 00000010100101000001111010011100" << endl;
    cout << "输出：" << output1 << " (" << bitset<32>(output1) << ")" << endl;

    uint32_t input2 = 0b11111111111111111111111111111101;
    uint32_t output2 = sol.reverseBits(input2);
    cout << "输入：n = 11111111111111111111111111111101" << endl;
    cout << "输出：" << output2 << " (" << bitset<32>(output2) << ")" << endl;

    return 0;
}

Java

public class Solution {
    // 颠倒给定的 32 位无符号整数的二进制位
    public int reverseBits(int n) {
        int result = 0; // 初始化结果变量
        for (int i = 0; i < 32; i++) {
            // 提取最低位
            int bit = n & 1;
            // 将提取的位左移到相应的位置
            result = (result << 1) | bit;
            // 右移 n，以处理下一位
            n >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        Solution sol = new Solution();
        
        // 输入：n = 00000010100101000001111010011100
        int input1 = 0b00000010100101000001111010011100;
        int output1 = sol.reverseBits(input1);
        System.out.println("输入：n = 00000010100101000001111010011100");
        System.out.println("输出：" + output1 + " (" + Integer.toBinaryString(output1) + ")");
        
        // 输入：n = 11111111111111111111111111111101
        int input2 = 0b11111111111111111111111111111101;
        int output2 = sol.reverseBits(input2);
        System.out.println("输入：n = 11111111111111111111111111111101");
        System.out.println("输出：" + output2 + " (" + Integer.toBinaryString(output2) + ")");
    }
}

Python

class Solution:
    # 颠倒给定的 32 位无符号整数的二进制位
    def reverseBits(self, n: int) -> int:
        result = 0  # 初始化结果变量
        for i in range(32):
            # 提取最低位
            bit = n & 1
            # 将提取的位左移到相应的位置
            result = (result << 1) | bit
            # 右移 n，以处理下一位
            n >>= 1
        return result

# 测试用例
if __name__ == "__main__":
    sol = Solution()
    
    # 输入：n = 0b00000010100101000001111010011100
    input1 = 0b00000010100101000001111010011100
    output1 = sol.reverseBits(input1)
    print(f"输入：n = 00000010100101000001111010011100")
    print(f"输出：{output1} ({bin(output1)})")
    
    # 输入：n = 0b11111111111111111111111111111101
    input2 = 0b11111111111111111111111111111101
    output2 = sol.reverseBits(input2)
    print(f"输入：n = 11111111111111111111111111111101")
    print(f"输出：{output2} ({bin(output2)})")