reverseBits.md

190. 颠倒二进制位

原题

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

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

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

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

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

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/reverse-bits

两种解法

1.我的解法

public int reverseBits(int n) {
        if(n == 1) // 0001 翻转之后符号位为1，其余为0，是特殊的最小值
            return Integer.MIN_VALUE;
        int[] bits = getBit(n);
        if(bits[31] == 1){ // 说明这是一个负数，先转为反码（-1） 再转成原码（除符号位之外 取反）
            for(int i = 0; i < 32; i++){
                if(bits[i] == 0) bits[i] = 1;
                else {
                    bits[i] = 0;
                    break;
                }
            }
            for(int i = 0; i < 31; i++){
                if(bits[i] == 0) bits[i] = 1;
                else bits[i] = 0;
            }
        }

        int product = (n & 1) == 1 ? -1 : 1;
        int res = 0;
        for(int i = 0; i < 31; i++){
            res += product * bits[i];
            product *= 2;
        }
        return res;
    }

    private int[] getBit(int n){
        int[] res = new int[32];
        int index = 31;
        while(n != 0){
            if((n & 1) == 1)
                res[index] = 1;
            index--;
            n >>>= 1;
        }
        return res;
    }

思路分析：

• 从题目给的示例看，如果将一个数的二进制表示存放在长度为32的int[]中，答案就是将这个数组进行翻转后对应的数。
• 于是就进行这样这样的翻转操作，方法int[] getBit(int n)得到翻转后的二进制数组。
  • 通过while循环及n & 1不断得到原数右边的二进制位上的数字，然后依次放在结果数组索引为31，30，29……处。
  • 直到n == 0，其余二进制位的数字为0，数组默认值为0，所以不用进行处理。
• 接下来要将翻转后的二进制数组再转换为十进制输出。这里要注意区分翻转后的数是正数还是负数。因为存放正数与负数的方式不同
  • 正数使用原码，直接按位进行加和即可。
  • 负数使用补码，要先转换为原码，然后按位加和再取负。
• 判断正负通过符号位判断，也就是bits[31]，如果这个值为-1，那么就是负数。要将其转换为原码，先进行-1操作，再除了符号位按位取反。
  • 减一操作就是从低位开始，将遇到的0变为1，直到遇到第一个1，将其变为0.（6-12行）
  • 除了符号位按位取反。（13-16行）
• 之后按位相加即可。第i位需要加的数为2^(i-1) * bits[i]。2^(i - 1)可以使用变量product来存放，每次移动一位都使product *= 2即可。
• 时间复杂度与空间复杂度都是$O(1)$的。但是确实麻烦

运行结果：

• 执行用时 :2 ms, 在所有 Java 提交中击败了16.14%的用户
• 内存消耗 :38.2 MB, 在所有 Java 提交中击败了5.27%的用户

2.评论区方法

public int reverseBits2(int n) {
        int res = 0;
        for(int i = 31; i >= 0 && n != 0; i--){
            res += (n & 1) << i;
            n >>>= 1;
        }
        return res;
    }

思路分析：

• 不需要自己去完成二进制与十进制转换的处理。
• 举一个例子10的二进制表示为：1010。 它等于 1000 + 0000 + 0010 + 0000。一个数就等于它的每一位二进制位的数字保持不变，其余位都置为0的32个数相加。所以我们要得到二进制翻转后的结果，从低位往高位，依次将该为数字 1或者0通过移位得到翻转后该位对应的数，再相加即可。
• 剩下的事就是为了翻转而进行移位操作。
  • 通过n & 1得到每一位的数字，通过n >>>= 1无符号右移一位来准备获取下一位的数字。
  • 当n == 0后，剩余位的数字都是0，不会对加和有影响，停止循环。
  • 最低位要移到第32位，需要将最低位数字向左移动31位；第二位要移动到第30位，需要将第二位的数字左移30位。所以设置初状态i = 31，表示最低位要左移31位。通过i--不断表示之后的数字需要移动几位。
• 时间复杂度与空间复杂度都是$O(1)$的。

运行结果：

• 执行用时 :1 ms, 在所有 Java 提交中击败了100.00%的用户
• 内存消耗 :38.3 MB, 在所有 Java 提交中击败了5.27%的用户