当前位置：首页 > news >正文

LeetCode 面试经典150题 190.颠倒二进制位

news 来源：原创 2024/9/23 12:23:02

复习知识：正数的原码、反码、补码相同，负数的反码在其原码的基础上, 符号位不变，其余各个位取反，负数的补码是在其原码的基础上, 符号位不变, 其余各位取反, 最后+1 (即在反码的基础上+1)。

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

提示：

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

示例 2：

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

不用管符号，比如示例2，我们输入的整数是正的而且大于Java中int的正数表示范围。所以采用找一个有符号数，它的二进制形式跟我们输入的无符号二进制形式一模一样，我们就把这个有符号数当作无符号数来处理，对其32位都进行颠倒。颠倒后输出结果，把我们的无符号数当作有符号输出即可，我们自己根据补码转换。总而言之，把int n当作无符号数来处理，就把它想象成一个字符串。

思路：

执行的 & >> << | 都是位操作，我们不用关心数据是大端存储还是小端存储，怎么进行位运算、符号什么的，因为我们执行的是位运算操作，编译器会为我处理，我们不用管。想像成直接对一个二进制数执行位操作，其余的不用管。

代码：

public class Solution {// you need treat n as an unsigned valuepublic int reverseBits(int n) {int res = 0;  // 反转结果，初始为0表示所有位都为0// 循环处理32位，idx为位索引for (int idx = 0; idx < 32; idx++) {int digit = n & 1;  // 获取当前最低位n >>= 1;  // 将最低位右移掉res |= (digit << (31 - idx));  // 将最低位反转到实际位置上}return res;}
}

性能：

时间复杂度o(1)

空间复杂度o(1)