Leetcode 颠倒二进制位

以下是对所提供的代码进行中文解释以及其算法思想分析：

算法思想

这段代码的目标是反转一个32位整数的二进制位。

核心思路是：

1. 逐位提取： 利用位操作从输入整数的最低位开始，逐位提取其二进制位。
2. 逐位插入： 将提取到的位插入到结果整数中，并将结果按要求向左移位以构建反转后的二进制数。
3. 依次处理： 将输入整数右移以处理其余的位，直到所有32位都被处理完成。

通过这种逐位操作，无论是正数还是负数，都可以实现反转操作。Java 使用补码形式表示有符号整数，因此不需要额外处理符号问题。

代码逐步解析

public int reverseBits(int n) {
    int result = 0; // 用于存储反转后的结果
    for (int i = 0; i < 32; i++) { // 需要处理32位
        int bit = n & 1; // 提取当前最低位（n的最后一位）
        result = (result << 1) | bit; // 将结果左移一位，并将提取的位加入到结果中
        n >>= 1; // 将输入整数右移一位，准备处理下一位
    }
    return result; // 返回反转后的整数
}

关键步骤分析

1. 提取最低位

   int bit = n & 1;
   

   n & 1 是一个位操作，它将提取出整数 n 的最低位。例如：

   • 如果 n = 5 (0101)，则 n & 1 = 1。
   • 如果 n = 6 (0110)，则 n & 1 = 0。

2. 将提取的位加入结果

   result = (result << 1) | bit;
   

   • result << 1 表示将结果的二进制位左移一位，为新提取的位留出位置。
   • | bit 表示将提取的位加入结果。例如：
     • 假设 result = 010 (2)，提取的 bit = 1，则操作后 result = 101 (5)。

3. 右移输入整数

   n >>= 1;
   

   将输入整数 n 的二进制位右移一位，以便在下一次循环中处理下一个最低位。

4. 循环32次

   • 因为输入是一个32位整数，所以需要循环32次，逐一处理所有的位。

输入输出示例

以示例1（输入 n = 43261596）为例：

• n 的二进制表示为：00000010100101000001111010011100。
• 反转后的结果为：00111001011110000010100101000000。
• 输出整数为：964176192。

以示例2（输入 n = -3）为例：

• n 的二进制补码表示为：11111111111111111111111111111101。
• 反转后的结果为：10111111111111111111111111111111。
• 输出整数为：-1073741825。

总结

这段代码的关键在于利用位运算逐位处理，结合移位操作构建反转结果。由于 Java 对有符号整数的补码处理特点，代码对正数和负数均适用，无需特别处理符号问题。