力扣1009补码解法C++实现

力扣 1009 题解析与 C 代码一、问题解析题目描述每个非负整数N都有其二进制表示。例如5的二进制表示为101其补码为010即十进制中的2。对于给定的十进制整数N返回其二进制表示取反即补码所对应的十进制整数。注意二进制表示中不包含前导零因此补码的二进制表示也不包含前导零。核心要点补码定义将原二进制数的每一位0变为11变为0。无前导零计算补码时只考虑原二进制数有效位的长度忽略更高位的虚拟零。例如5(101) 的有效位长度为3其补码是010(即2)而不是...11111010。数学等价关系对于一个有效位长度为L的二进制数N其补码等于(2^L - 1) ^ N或(2^L - 1) - N。其中2^L1是一个所有L位都为1的二进制掩码。算法思路确定有效位长度找到N的最高位1的位置其索引从0开始加1即为长度L。构造全1掩码创建一个二进制数其低L位全为1高位全为0。即mask (1 L)1。计算补码将原数N与掩码mask进行按位异或 (^) 操作即可得到补码。因为异或1会翻转该位。时间复杂度O(1)因为整数位数固定例如32位。空间复杂度O(1)。二、C 代码实现方法一位运算异或掩码法这是最直接和高效的方法。class Solution { public: int bitwiseComplement(int n) { // 处理边界情况n为0时其有效位长度为1掩码为1补码为1 if (n 0) return 1; // 步骤1计算有效位长度 L int length 0; int temp n; while (temp 0) { temp 1; // 右移一位 length; } // 或者使用内置函数 int length floor(log2(n)) 1; // 步骤2构造全1掩码 mask (1 L)1 int mask (1 length) - 1; // 步骤3计算补码 n ^ mask return n ^ mask; } };方法二位运算循环取反法通过循环直接逐位翻转逻辑更直观。class Solution { public: int bitwiseComplement(int n) { if (n 0) return 1; int result 0; int bitPosition 0; // 当前处理的位位置 while (n 0) { // 取n的最低位并翻转 (0-1, 1-0) int currentBit (n 1) ^ 1; // 将翻转后的位放到结果的正确位置 result | (currentBit bitPosition); // n右移一位准备处理下一位 n 1; bitPosition; } return result; } };方法三利用bitset辅助理解使用标准库bitset可以更清晰地展示二进制操作过程但效率略低。#include bitset class Solution { public: int bitwiseComplement(int n) { if (n 0) return 1; // 确定需要的位数32位足够 const int MAX_BITS 32; std::bitsetMAX_BITS bs(n); // 找到最高位1的位置 int highestBit MAX_BITS1; while (highestBit 0 !bs.test(highestBit)) { highestBit--; } // 翻转从最高位到第0位的所有位 for (int i 0; i highestBit; i) { bs.flip(i); } // 转换回整数 return static_castint(bs.to_ulong()); } };三、算法对比特性异或掩码法循环取反法bitset 法时间复杂度O(log N)O(log N)O(log N)空间复杂度O(1)O(1)O(1)核心思想构造全1掩码后异或逐位翻转并重组使用标准库位集操作代码简洁性简洁较简洁直观但稍冗长推荐度推荐推荐适用于教学演示四、关键点与示例边界条件输入N 0时其二进制表示为0有效长度视为1补码为1因此应返回1。掩码构造(1 L)1是生成L位全1掩码的常用技巧。例如L313 8(1000)8-17(111)。与 LeetCode 476 的关系本题 (1009) 与 数字的补数 本质上是同一道题解法完全相同。测试示例int main() { Solution sol; cout sol.bitwiseComplement(5) endl; // 输出: 2 (101 - 010) cout sol.bitwiseComplement(7) endl; // 输出: 0 (111 - 000) cout sol.bitwiseComplement(10) endl; // 输出: 5 (1010 - 0101) cout sol.bitwiseComplement(0) endl; // 输出: 1 (特殊处理) return 0; }参考来源1009. Complement of Base 10 Integer*阶乘求和全解析从 Python 秒过到 C 手写高精度力扣 476. 数字的补数 CLeetcode 476. 数字的补数 Cleetcode-1009. 十进制整数的反码刷题笔记c