LC 476. 数字的补数

题目描述

这是 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 < 2^{31}$

---

模拟（遍历）

返回对 $num$ 的二进制表示取反的数，注意 $num$ 的二进制表示是不包含前导零的。

因此主要问题求得 $num$ 最高位 $1$ 的位置。

一个简单的做法是：先对 $num$ 进行「从高到低」的检查，找到最高位 $1$ 的位置 $s$，然后再对 $num$ 进行遍历，将低位到 $s$ 位的位置执行逐位取反操作。

代码：

class Solution {
    public int findComplement(int num) {
        int s = -1;
        for (int i = 31; i >= 0; i--) {
            if (((num >> i) & 1) != 0) {
                s = i;
                break;
            }
        }
        int ans = 0;
        for (int i = 0; i < s; i++) {
            if (((num >> i) & 1) == 0) ans |= (1 << i);
        }
        return ans;
    }
}

• 时间复杂度：$O(\log{num})$
• 空间复杂度：$O(1)$

---

模拟（lowbit）

通过解法一我们发现，如果 $num$ 的二进制表示中最高位 $1$ 的位置为 $s$ 的话，那么实际上我们只需要对 $num$ 的前 $s - 1$ 位进行取反即是答案（第 $s$ 位的取反结果始终为 $0$）。

因此我们可以先使用 lowbit 操作来得到 $num$ 二进制表示中最高位 $1$ 的位置为 $1$，其余位为 $0$ 时所代表的数字 $x$。

然后 $x - 1$ 即是二进制表示中前 $s - 1$ 位均为 $1$，其余位为 $0$ 的数字，将其与 $num$ 的取反数执行「按位与」操作，即可达到「仅对 $num$ 的前 $s - 1$ 位进行取反」的效果。

代码：

class Solution {
    public int findComplement(int num) {
        int x = 0;
        for (int i = num; i != 0; i -= i & -i) x = i;
        return ~num & (x - 1);
    }
}

• 时间复杂度：$O(\log{num})$
• 空间复杂度：$O(1)$

---

最后

这是我们「刷穿 LeetCode」系列文章的第 No.476 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。