题目
标题和出处
标题：数字的补数
出处：476. 数字的补数
难度
3 级
题目描述
要求
一个整数的补数是将该整数的二进制表示中的所有 0 \texttt{0} 0 变成 1 \texttt{1} 1 和所有 1 \texttt{1} 1 变成 0 \texttt{0} 0 之后得到的整数。
- 例如，整数 5 \texttt{5} 5 的二进制表示是 "101" \texttt{"101"} "101"，其补数是 "010" \texttt{"010"} "010"，表示整数 2 \texttt{2} 2。
给定一个整数 num \texttt{num} num，返回它的补数。
示例
示例 1：
输入： num = 5 \texttt{num = 5} num = 5
输出： 2 \texttt{2} 2
解释： 5 \texttt{5} 5 的二进制表示为 101 \texttt{101} 101（没有前导零位），其补数为 010 \texttt{010} 010。所以返回 2 \texttt{2} 2。
示例 2：
输入： num = 1 \texttt{num = 1} num = 1
输出： 0 \texttt{0} 0
解释： 1 \texttt{1} 1 的二进制表示为 1 \texttt{1} 1（没有前导零位），其补数为 0 \texttt{0} 0。所以返回 0 \texttt{0} 0。
数据范围
- 1 ≤ num < 2 31 \texttt{1} \le \texttt{num} < \texttt{2}^\texttt{31} 1≤num<231
解法
思路和算法
由于给定的整数 num \textit{num} num 满足 1 ≤ num ≤ 2 31 − 1 1 \le \textit{num} \le 2^{31} - 1 1≤num≤231−1，因此存在正整数 k k k 使得 2 k − 1 ≤ num ≤ 2 k − 1 2^{k - 1} \le \textit{num} \le 2^k - 1 2k−1≤num≤2k−1， num \textit{num} num 是 k k k 位二进制数（不含前导零）， num \textit{num} num 与补数之和为 2 k − 1 2^k - 1 2k−1。
用 sum \textit{sum} sum 表示 num \textit{num} num 与补数之和，则 sum \textit{sum} sum 是大于等于 num \textit{num} num 的最小的 2 k − 1 2^k - 1 2k−1 形式的整数，其中 k k k 是正整数。初始时 sum = 1 \textit{sum} = 1 sum=1，当 sum < num \textit{sum} < \textit{num} sum<num 时每次在 sum \textit{sum} sum 的二进制表示的最前面添加一个 1 1 1，等价于用 sum × 2 + 1 \textit{sum} \times 2 + 1 sum×2+1 作为 sum \textit{sum} sum 的新值，直到 sum ≥ num \textit{sum} \ge \textit{num} sum≥num。此时 sum − num \textit{sum} - \textit{num} sum−num 即为 num \textit{num} num 的补数。
由于 num \textit{num} num 的最大值是 2 31 − 1 2^{31} - 1 231−1，因此在上述计算过程中， sum \textit{sum} sum 可能的最大值是 2 31 − 1 2^{31} - 1 231−1，不会出现溢出的情况。
代码
class Solution {
public int findComplement(int num) {
int sum = 1;
while (sum < num) {
sum = sum * 2 + 1;
}
return sum - num;
}
}
复杂度分析
时间复杂度： O ( log num ) O(\log \textit{num}) O(lognum)，其中 num \textit{num} num 是给定的整数。寻找大于等于 num \textit{num} num 的最小整数 sum \textit{sum} sum 需要将 sum \textit{sum} sum 的值更新 O ( log num ) O(\log \textit{num}) O(lognum) 次。
空间复杂度： O ( 1 ) O(1) O(1)。