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

jonathan安全地带 lv.1

发布时间：2023-09-07 18:18:53 261

题目描述:

给你一个正整数 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)

文章来源： https://blog.51cto.com/u_15891283/5886574

特别声明：以上内容（图片及文字）均为互联网收集或者用户上传发布，本站仅提供信息存储服务！如有侵权或有涉及法律问题请联系我们。