What is the Number Complement problem?

The Number Complement problem asks you to flip all bits in the binary representation of an integer and return its complement.

How do you approach the Number Complement problem?

You can solve it by generating a mask with all 1’s and XOR-ing it with the original number. Alternatively, you can calculate the complement by flipping the bits based on the binary length.

What bit manipulation operations are useful for solving the Number Complement problem?

XOR is the primary operation used, as it effectively flips the bits when applied to a mask of 1’s.

Can the Number Complement problem be optimized further?

Yes, using more efficient methods to generate the mask or simplifying the solution using arithmetic tricks can improve performance.

How does the problem's pattern apply to other bit manipulation challenges?

The Number Complement problem demonstrates how bit manipulation can be used to flip specific bits, which is a common technique in problems involving binary representations or toggling states.

#476

Easy

auto_awesome位运算·操作·driven·solution·strategy

LeetCode 题解工作台

数字的补数

对整数的二进制表示取反（ 0 变 1 ， 1 变 0 ）后，再转换为十进制表示，可以得到这个整数的补数。例如，整数 5 的二进制表示是 "101" ，取反后得到 "010" ，再转回十进制表示得到补数 2 。给你一个整数 num ，输出它的补数。示例 1：输入： num = 5 输出： 2 …

位运算

题目描述

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

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

lightbulb

解题思路

方法一：位运算

根据题目描述，我们可以通过异或运算来实现取反的操作，步骤如下：

我们首先找到 $\textit{num}$ 的二进制表示中最高位的 $1$ ，位置记为 $k$ 。

然后，构造一个二进制数，第 $k$ 位为 $0$ ，其余低位为 $1$ ，即 $2^k - 1$ ；

最后，将 $\textit{num}$ 与上述构造的二进制数进行异或运算，即可得到答案。

时间复杂度 $O(\log \textit{num})$ ，其中 $\textit{num}$ 为输入的整数。空间复杂度 $O(1)$ 。

1

2

3

4

class Solution:
    def findComplement(self, num: int) -> int:
        return num ^ ((1 << num.bit_length()) - 1)

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ability to apply bitwise operations effectively.
question_mark
Understanding of binary number representations and manipulation.
question_mark
Ability to explain optimization of bit manipulation techniques.

warning

常见陷阱

外企场景

error
Forgetting to handle edge cases like when `num` is a single bit (i.e., 1 or 0).
error
Confusing the number of bits with the actual value of the complement.
error
Overcomplicating the solution instead of focusing on simple bitwise operations.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Can you find a way to solve this problem using just arithmetic?
arrow_right_alt
What if you were limited by space constraints and could only use a fixed number of variables?
arrow_right_alt
Can you modify this solution to work with negative integers?

help

常见问题

外企场景

继续练习

#477 汉明距离总和 #473 火柴拼正方形 #464 我能赢吗