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

梦里梦外; 2022-09-02 08:10 156阅读 0赞

题目如下：

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

![在这里插入图片描述][6587dc5002b54ac192a6a98cb57073e1.png]

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

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

10进制转二进制相信大家都会转，那怎么用代码来实现它呢？可以先来分析一下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]

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

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

得到二进制后，需要将二进制转为反码形式，只需循环遍历二进制数，当为0时，用1替换；当为1时，用0替换。  
![在这里插入图片描述][939334618be44bbe8692ee46e611788e.png]

最后以该反码形式表示的二进制再转为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再减去当前的位数即可得到幂次。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 3]

最后得出代码如下：

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：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 4]

其实这道题还有一个非常巧妙的解法，我们知道，二进制的反码形式是由原码转换而来的，只需对原码的每一位取反即可，那么它其实可以通过与对应二进制位的全1异或来得到反码，比如：  
![在这里插入图片描述][170960db601b4122bb4c32ca8079bcc9.png]

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：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 5]

[6587dc5002b54ac192a6a98cb57073e1.png]: /images/20220829/a1257b221f8742a78f6dc62b3a4f5902.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70]: /images/20220829/482f2b794afe400f8a8e0f0e2af74c40.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 1]: /images/20220829/debb0f4fc3e34c65876107521d2bc155.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 2]: /images/20220829/b52fc57ff2e14998a85d266489a46699.png
[939334618be44bbe8692ee46e611788e.png]: /images/20220829/955e40bf9d7e4163a4e531fcfb108c1d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 3]: /images/20220829/19ba0e87ee814c63b4f638e76a246d4f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 4]: /images/20220829/f9998f1823eb4cd59dfb0dbc58082fdf.png
[170960db601b4122bb4c32ca8079bcc9.png]: /images/20220829/a077f40f5750459e863d5b42fd425d20.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNDUzMTE3_size_16_color_FFFFFF_t_70 5]: /images/20220829/eb38920ae12c47b58a558218ed096131.png