LeetCode 476.数字的补数(简单)

题目描述:

给你一个 正 整数 ​​num​​ ，输出它的补数。补数是对该数的二进制表示取反。

示例 1:

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

示例 2:

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

提示:

• 给定的整数 ​​num​​ 保证在 32 位带符号整数的范围内。
• ​​num >= 1​​
• 你可以假定二进制数不包含前导零位。
• 本题与 1009 https://leetcode-cn.com/problems/complement-of-base-10-integer/ 相同

题目分析:

这道题是 ​​LeetCode 190.颠倒二进制位(简单)​​​ 的变形题，运用按位异或的性质就能解决这道题，因为按位取反其实就是按位异或操作。例如：​​101 ^ 111 = 010​​​ 。所以，我们就要拿题目给出的数和按位数进行异或操作，获取位数的方法可以使用右移操作实现。对于获取按位数，我们可以使用 ​​1​​​ 左移 ​​num 的有效长度​​​ 再减去 ​​1​​​ 获得。例如，题目给出的 ​​num = 101​​​ ，得到有效位数为 ​​3​​​ ，再计算 ​​(1 << 3) - 1 = 111​​​ ，最后将 ​​num = 101​​​ 和 ​​111​​​ 进行异或操作得到答案 ​​010​​ 。

题解:

执行用时: 0 ms

内存消耗: 35.2 MB

class Solution {
    public int findComplement(int num) {
        // 如果 num 为 0 直接返回 1
        if (num == 0) {
            return 1;
        }
        // 临时变量
        int temp = 0;
        // 循环 32 次，题目给定的是 32 位无符号整数
        for (int i = 0; i < 32; i++) {
            // num 右移 i 位和 1 按位与
            if (((num >> i) & 1) == 1) {
                // 如果最低位是 1 更新 temp
                temp = i + 1;
            }
        }
        // 返回结果
        // (1 << temp) - 1 得到与 num 相同长度的全 1 二进制数
        // 和 num 进行异或操作即可得到答案
        return num ^ ((1 << temp) - 1);
    }
}

题目来源:力扣(LeetCode)