LeetCode每日一练（十进制整数的反码）

题目如下：

每个非负整数 N 都有其二进制表示。例如， 5 可以被表示为二进制 “101”，11 可以用二进制 “1011” 表示，依此类推。注意，除 N = 0 外，任何二进制表示中都不含前导零。二进制的反码表示是将每个 1 改为 0 且每个 0 变为 1。例如，二进制数 “101” 的二进制反码为 “010”。给你一个十进制数 N，请你返回其二进制表示的反码所对应的十进制整数。

在这里插入图片描述

题目要求将一个非负整数二进制的反码表示转为十进制数，比如，5的二进制位101，那么其反码形式为010，以该反码为二进制所对应的十进制整数为2，所以输入整数5，应该得到整数2。

那么首先可以将输入的整数先转为二进制，然后将二进制的反码形式求出来，最后通过该反码转为十进制。

10进制转二进制相信大家都会转，那怎么用代码来实现它呢？可以先来分析一下：

在这里插入图片描述

对于十进制数11，其转为二进制的过程如上图所示，让11除以2，得到商5，余数1,；在让5除以2，得到商2，余数1；最后让2除以2，得到商1，余数0，二进制为1011。 由此得出结论，不断地让输入的数除以2，直至余数为0停止，让最后一次除法的商从下至上拼接所有的余数即可得到二进制，如下所示：

在这里插入图片描述

但在代码的实现过程中，我们只能从上往下除，并不能提前得知后面的商和余数，解决办法也很简单，使用一个StringBuilder，把每次除以2得到的余数放入StringBuilder，除完后将StringBuilder反转，然后将最后一次除法的商插入到StringBuilder的首部即可得到二进制。

在这里插入图片描述

得到二进制后，需要将二进制转为反码形式，只需循环遍历二进制数，当为0时，用1替换；当为1时，用0替换。

在这里插入图片描述

最后以该反码形式表示的二进制再转为10进制，转换也非常简单：0 * 2 ^ 3 + 1 * 2 ^ 2 + 0 * 2 ^ 1 + 0 * 2 ^ 0 = 0 + 4 + 0 + 1 = 5，所以最后的结果为5。

那如何用代码来实现这一过程呢？只需遍历整个二进制数，然后对每一位进行乘法操作，比如0100中的第一位0，它需要乘以2的3次方，而第二位1需要乘以2的2次方，我们可以通过字符串的长度减1再减去当前的位数即可得到幂次。

在这里插入图片描述

最后得出代码如下：

public class Solution {

    public static int bitwiseComplement(int n) {
        // 10进制转为2进制
        StringBuilder sb = new StringBuilder();
        while (n / 2 != 0) {
            int num = n % 2; // 求出余数
            sb.append(num); // 将余数存入StringBuilder
            n = n / 2; // 求出商
        }
        // 反转字符串，并将最后一次除法的商插入到字符串的首部
        String binaryNum = sb.reverse().insert(0, n).toString();
        // 将二进制转为反码形式
        char[] chars = binaryNum.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == '0') {
                // 如果为0，转为1
                chars[i] = '1';
            } else if (chars[i] == '1') {
                // 如果为1，转为0
                chars[i] = '0';
            }
        }
        // 将反码表示的二进制转回十进制
        int result = 0;
        for (int i = 0; i < chars.length; i++) {
            // 将字符转为数字
            int num = Integer.parseInt(chars[i] + "");
            result += num * Math.pow(2, chars.length - 1 - i);
        }
        return result;
    }
}

提交到LeetCode：

在这里插入图片描述

其实这道题还有一个非常巧妙的解法，我们知道，二进制的反码形式是由原码转换而来的，只需对原码的每一位取反即可，那么它其实可以通过与对应二进制位的全1异或来得到反码，比如：

在这里插入图片描述

11的二进制原码为1011，让其异或相等位数的全1二进制，因为异或的规则为相同为0，不同为1，那么原码中的1因为与之相同就会转为0，而原码中的0因为与之不同就会转为1，所以最终得到0100。

那接下来的问题就转化为了求出位数，因为需要相等位数的全1与其异或，我们可以找找规律，对于整数11，需要四位的全1二进制与其异或，1111表示的十进制为15；对于整数5，需要三位的全1二进制与其异或，111表示的十进制为7，由此得出结论，只需要全1的二进制数大于了输入的整数，那么其位数就一定与之相同。

我们可以从只有1位二进制数1开始计算，当只有1位二进制数1时，对应的十进制为1； 当有2位二进制数11时，对应的十进制为3； 当有3位二进制数111时，对应的十进制为7； 当有4位二进制数1111时，对应的十进制为15； 规律已经非常明显了，它就等于前一个数的2次方加1，即：2n + 1。

由此可得代码：

public static void main(String[] args) {
    double num = 1;
    while (num < 11){   // 当num大于11时结束循环
        num = num * 2 + 1; // 在前一个num值的基础上乘以2加1
    }
    System.out.println(num);
}

num = num * 2 + 1;也可以转化为移位操作：num = (num << 1) + 1，向左移一位，表示乘以2的1次方，效果是一样的。

这样就能够得出需要与之异或的值，最后让其直接与输入的整数异或即可：

class Solution {
    public int bitwiseComplement(int N) {
        int num = 1;
        while(num < N){
            num = (num << 1) + 1;
        }
        return num ^ N;
    }
}

提交到LeetCode：

在这里插入图片描述