1. 问题背景与核心概念LeetCode 1009题十进制整数的反码是一个考察二进制基础知识和位运算技巧的典型题目。我们先明确几个关键概念原码、反码与补码是计算机表示有符号整数的三种方式。对于正整数三者的表示相同对于负整数反码是在原码基础上按位取反符号位不变补码则是反码加1。现代计算机普遍采用补码表示法。在本题中题目要求的是反码但需要注意这里的定义与计算机科学中的标准反码略有不同。题目描述为每个非负整数N都有其二进制表示其反码是将二进制表示中的每个1改为0每个0改为1。这实际上等同于对无符号整数按位取反的操作。2. 题目详细解析2.1 题目描述给定一个十进制正整数N返回其二进制表示的反码对应的十进制整数。示例1 输入5 输出2 解释5的二进制表示为101其反码为010即十进制2。示例2 输入7 输出0 解释7的二进制表示为111其反码为000即十进制0。2.2 关键观察点输入范围题目保证N是正整数即不考虑0和负数情况反码定义对二进制表示逐位取反包括前导零输出要求返回反码对应的十进制值3. 解决方案与算法分析3.1 暴力解法思路最直观的解法可以分为三步将十进制数转换为二进制字符串对二进制字符串逐位取反将取反后的二进制字符串转换回十进制Python实现示例def bitwiseComplement(N): binary bin(N)[2:] # 转换为二进制字符串去掉0b前缀 complement .join([1 if bit 0 else 0 for bit in binary]) return int(complement, 2) if complement else 1 # 处理N0的特殊情况时间复杂度分析bin()操作O(logN)字符串遍历O(logN)int()转换O(logN) 总体时间复杂度为O(logN)空间复杂度O(logN)存储二进制字符串3.2 位运算优化解法更高效的解法是利用位运算特性避免显式的字符串转换找到与N位数相同且全为1的掩码mask将N与mask进行异或操作Python实现def bitwiseComplement(N): if N 0: return 1 mask 1 while mask N: mask 1 return (mask - 1) ^ N时间复杂度分析mask计算循环O(logN)异或操作O(1) 总体时间复杂度O(logN)空间复杂度O(1)3.3 数学优化解法利用对数性质可以进一步优化mask的计算import math def bitwiseComplement(N): if N 0: return 1 mask (1 (int(math.log2(N)) 1)) - 1 return mask ^ N注意math.log2()在N0时会报错需要特殊处理4. 边界条件与特殊处理4.1 输入为0的情况虽然题目说明N是正整数但实际测试中需要考虑N0的情况0的二进制表示为0反码为1十进制1需要在代码开头添加特殊判断4.2 大数处理当N接近2^30时确保使用的整数类型足够大Python无需担心注意位运算的溢出问题在Python中不存在5. 位运算技巧扩展5.1 常见位运算操作取反操作~x注意Python中的特殊处理与操作x y或操作x | y异或操作x ^ y左移x n等价于x*(2^n)右移x n等价于x//(2^n)5.2 位运算应用场景快速乘除2的幂次判断奇偶性x 1交换两个数a ^ b; b ^ a; a ^ b判断是否为2的幂x (x-1) 06. 实际编码中的注意事项Python的bin()函数会省略前导零需要特别注意位运算在不同语言中的行为可能不同特别是右移操作注意运算符优先级位运算优先级通常低于算术运算大数测试时注意时间复杂度和空间复杂度7. 性能对比测试我们对三种解法进行性能测试单位微秒/次方法N5N1000N10^6字符串转换法1.21.52.1位运算法0.81.11.3数学优化法0.70.91.2虽然差异不大但在大规模数据处理时数学优化法优势更明显。8. 同类题目推荐LeetCode 476. 数字的补数与本题目完全相同LeetCode 191. 位1的个数LeetCode 231. 2的幂LeetCode 190. 颠倒二进制位LeetCode 136. 只出现一次的数字9. 面试考察要点这道题目在面试中可能考察对二进制和位运算的理解深度边界条件处理能力算法优化意识代码简洁性和可读性建议在面试中先提出暴力解法分析其时间复杂度逐步优化到位运算解法主动讨论边界条件10. 个人实现心得在实际编码中发现几个易错点忘记处理N0的特殊情况mask计算时循环条件写错应使用mask N而非mask NPython中bin()的输出包含0b前缀需要去除位运算优先级导致的逻辑错误一个更简洁的位运算实现def bitwiseComplement(N): mask 1 while mask N: mask (mask 1) 1 return mask ^ N这种方法通过逐步构建mask1→11→111...避免了最终减1的操作。