LeetCode 1009 476 数字的补数

LeetCode 1009 & 476 数字的补数

问题描述

给定一个正整数（或非负整数），输出它的补数。补数是对该数的二进制表示（不包含前导零）按位取反的结果。
例如：5 的二进制是101，取反得010，即十进制 2。

LeetCode 1009 题名为“十进制整数的补码”，LeetCode 476 题名为“数字的补数”，两者本质完全相同。

解法一：逐位取反法（对应 LeetCode 1009 代码）

classSolution{public:intbitwiseComplement(intn){if(!n)return1;// 特殊情况：0 的二进制取反应为 1intres=0;for(inti=0;1<<i<=n;i++)// 遍历有效位，直到 2^i 超过 nres|=!(n>>i&1)<<i;// 取出第 i 位，取反后左移 i 位，累加到结果returnres;}};

思路解析

• 核心思想：逐位处理原数的二进制有效位，对每一位取反后构建新数。
• 步骤：
  1. 若n == 0，直接返回1（二进制0取反为1）。
  2. 从低位到高位循环，i表示当前位，循环条件1 << i <= n保证只处理有效位（忽略前导零）。
  3. (n >> i) & 1取出第i位的值（0 或 1）。
  4. 逻辑非!将位值取反：!0 = 1，!1 = 0。
  5. 将取反后的值左移i位，放回原来的位权位置，通过按位或|=累加到结果res。
  6. 循环结束，res即为补数。

复杂度分析

• 时间复杂度：O(log n)，循环次数等于 n 的二进制位数。
• 空间复杂度：O(1)，只使用了常数变量。

解法二：掩码取反法（对应 LeetCode 476 代码）

classSolution{public:intfindComplement(intnum){if(!num)return1;// 特殊情况处理intcnt=0,x=num;while(x){// 统计有效位数x>>=1;cnt++;}// 构造低 cnt 位全 1 的掩码，与 ~num 按位与，保留低位return~num&((1ll<<cnt)-1);}};

思路解析

• 核心思想：先确定原数的有效位数，构造一个掩码，将取反后的结果截断到有效位。
• 步骤：
  1. 若num == 0，直接返回1。
  2. 统计有效位数cnt：将num不断右移直到 0，每移一次计数加 1。
  3. 构造掩码mask = (1ll << cnt) - 1，即低cnt位全为 1 的二进制数（使用1ll防止左移溢出 int 范围）。
  4. 对num按位取反得~num，此时高位（超出有效位）也被取反，与掩码按位与&后，高位清零，只保留低cnt位，即为正确补数。

复杂度分析

• 时间复杂度：O(log n)，统计位数需要循环，但取反和与运算是 O(1)。
• 空间复杂度：O(1)。

两种解法对比

共同点

• 都正确处理了不包含前导零的二进制取反。
• 都对n == 0做了特殊处理（返回 1）。
• 均基于位运算实现，未借助字符串转换。

不同点

• 实现方式：解法一在循环中直接计算结果，解法二先统计位数再使用取反和掩码。
• 取反手段：解法一用逻辑非!配合移位实现位取反；解法二直接用按位取反~，再通过与掩码结合。
• 溢出考虑：解法二必须注意掩码构造时的溢出问题，使用1ll转为 long long 是必要的。

总结

两道题本质相同，解法各有特色。

• 解法一（逐位取反）思路直观，适合初学者理解二进制位操作。
• 解法二（掩码取反）代码更简洁，利用掩码一次完成截断，体现了位运算的灵活性，但在使用时需留意数据范围。

掌握这两种解法有助于加深对位运算和二进制表示的理解，在实际开发中可根据场景选择合适的方法。