LeetCode刷题【476】数字的补数

对整数的二进制表示取反（0 变 1 ，1 变 0）后，再转换为十进制表示，可以得到这个整数的补数。

• 例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。

给你一个整数 num ，输出它的补数。

 

示例 1：

输入：num = 5
输出：2
解释：5 的二进制表示为 101（没有前导零位），其补数为 010。所以你需要输出 2 。

示例 2：

输入：num = 1
输出：0
解释：1 的二进制表示为 1（没有前导零位），其补数为 0。所以你需要输出 0 。

 

提示：

• 1 <= num < 231

 

注意：本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同

简单做下，不用位运算 & 用位运算

首先在不用位运算的情况下，我们理清下逻辑

1. 要取反的话，用当前数字余2，结果为1则取0，结果为0则取1，得到的数字留在当前位置
2. 然后接下来，对应二进制数往前找一位，我们用除法的除以2来实现，用`num = num /2`
3. 再次对num值余2，结果为1则取0，结果为0则取1，得到的结果要放在之前(1)中的二进制数前面,那么简单的相应作法把当前数字乘以2再加上（1）的结果，得到一个新的结果
4. 再次`num = num /2`
5. 再次对num值余2，结果为1则取0，结果为0则取1，这次得到的结果需要放在（3）的结果前面，那么对应的这次的结果需要乘以2的平方
6. 依此继续循环

class Solution {
    public int findComplement(int num) {
        int res = 0;
        int i = 1;
        while ( num > 0){
            res +=  (num%2==0?1:0) * i;
            i *= 2;
            num /= 2;
        }
        return res;
    }
}

更进一步

根据位运算相关规则，我们把上面的代码重新写一遍

乘以i个2就可以直接改写成左移i次，同时把后面要执行的`i+1`的操作也一并带上的话就变成了`<< i++`

余2判断奇偶性变成`num&1`，结果再取相反的那么就是`num&1^1`，注意不要使用`~`,这会把原来的1变成`11111111111111111111111111111110`，而0变成`11111111111111111111111111111111`

而对应的`num = num /2`改为`num = num >> 1`

class Solution {

    /**
     * 与&：0&0=0 0&1=0 1&0=0 1&1=1
     * 或|：0|0=0 0|1=1 1|0=1 1|1=1
     * 异或^：0^0=0 0^1=1 1^0=1 1^1=0
     * 取反~：~1=0 ~0=1
     * 左移<<：左边的二进制位丢弃，右边补0
     * 右移>>：正数左补0，负数左补1，右边丢弃
     * 无符号左移<<<：左边的二进制位丢弃，右边补0
     * 无符号右移>>>：忽略符号位，空位都以0补齐
     * @param num
     * @return
     */
    public int findComplement(int num) {
        int res = 0;
        int i = 0;
        while ( num > 0){
            res += (num&1^1) << i++;
            num = num >> 1;
        }
        return res;
    }
    
}

结束收工