原文链接: https://leetcode-cn.com/problems/number-complement

英文原文

The complement of an integer is the integer you get when you flip all the 0's to 1's and all the 1's to 0's in its binary representation.

• For example, The integer 5 is "101" in binary and its complement is "010" which is the integer 2.

Given an integer num, return its complement.

 

Example 1:

Input: num = 5
Output: 2
Explanation: The binary representation of 5 is 101 (no leading zero bits), and its complement is 010. So you need to output 2.

Example 2:

Input: num = 1
Output: 0
Explanation: The binary representation of 1 is 1 (no leading zero bits), and its complement is 0. So you need to output 0.

 

Constraints:

• 1 <= num < 231

 

Note: This question is the same as 1009: https://leetcode.com/problems/complement-of-base-10-integer/

中文题目

对整数的二进制表示取反（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/ 相同

通过代码

高赞题解

模拟（遍历）

返回对 $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)$

---

最后

如果有帮助到你，请给题解点个赞和收藏，让更多的人看到 ~ (“▔□▔)/

也欢迎你 关注我（公主号后台回复「送书」即可参与长期看题解学算法送实体书活动）或 加入「组队打卡」小群 ，提供写「证明」&「思路」的高质量题解。

所有题解已经加入 刷题指南，欢迎 star 哦 ~

统计信息

通过次数	提交次数	AC比率
65350	91674	71.3%

提交历史

提交时间	提交结果	执行时间	内存消耗	语言