LeetCode 476. Number Complement 数字补数Go 语言位运算构造掩码的两种解法【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go本文基于开源仓库 LeetCode-Go 中 leetcode/0476.Number-Complement/README.md 的题目分析与 476. Number Complement.go 的源码实现系统讲解 LeetCode 476「数字的补数」这一经典位运算题的完整解法。读完本文你将掌握「按二进制有效长度构造掩码再取反/异或」这一位运算核心技巧并能够将其推广到 Reverse Bits、Power of Two 等同源题目。一、题目理解补数的精确语义原文档给出的题目描述是Given a positive integer, output its complement number. The complement strategy is to flip the bits of its binary representation.即给定一个正整数输出它的补数complement number。补数的定义是对该数的二进制表示逐位取反。这道题的易错点在于取反的范围。题目附带两条约束直接决定了算法的形态给定的整数保证在 32 位带符号整数的范围内——意味着我们不能简单地用整型变量对 32 位全取反因为那会连同高位的 0 一起翻转把正数变成负数可以假定二进制表示不包含前导零位——例如 5 写作101而不是0000...0101因此只需要对有效位取反翻转后的结果必然是非负的。两个官方示例示例 1Input: 5 Output: 2 Explanation: 5 的二进制表示为 101无前导零其补数为 010即输出 2。示例 2Input: 1 Output: 0 Explanation: 1 的二进制表示为 1无前导零其补数为 0即输出 0。用公式概括若num的有效二进制位数为k则答案等于num的低k位全部取反。换句话说我们需要一个恰好覆盖k位的掩码这是两种解法的共同出发点。二、核心思路为什么要构造掩码直接写出^num按位取反会得到num所有 32 位的反码包括高位大量无意义的 0 也会变成 1结果是一个负数或与题意不符的大数。因此正确做法是先构造一个掩码mask低k位为 1、其余位为 0的数其中k是num的二进制有效长度用掩码对num做一次按位运算实现「只在低k位取反」。原文档对这一思路的总结是“按照题意构造相应的 mask 再取反即可”。下面结合仓库源码看两种具体的掩码构造法。三、解法一全 1 左移构造掩码Number Complement.go 中给出的第一种解法// 解法一 func findComplement(num int) int { xx : ^0 // ^0 1111111111111111111111 for xxnum 0 { xx 1 // 构造出来的 xx 1111111…0000000 的个数就是 num 的长度 } return ^xx ^ num // xx ^ num结果是前面的 0 全是 1 的num再取反即是答案 }逐行拆解其位运算逻辑xx : ^0Go 中一元运算符^表示按位取反^0得到全 1 的数32 位下即0xFFFFFFFF十进制 -1for xxnum 0不断将xx左移一位直到xx与num没有任何公共的 1 为止。此时xx从「全 1」变成了「高位全 1、低k位全 0」的形式低位的 0 恰好有k个k为num的二进制有效位数return ^xx ^ num先对xx取反得到「低k位全 1、高位全 0」的掩码再与num异或低k位逐位翻转高位保持不变即为答案。以num 5101为例走一遍步骤xx 的值低位视角说明初始...1111xx ^0全 1循环 1...1110xx5 101 0左移循环 2...1100xx5 100 0左移循环 3...1000xx5 0循环结束计算^xx ^ 50b111 ^ 0b1010b0102得到答案四、解法二temp左移 异或构造掩码同一文件中的第二种解法思路更直观也更容易向面试官讲清楚// 解法二 func findComplement1(num int) int { temp : 1 for temp num { temp 1 // 构造出来的 temp 00000……10000末尾 0 的个数是 num 的长度 } return (temp - 1) ^ num // temp - 1 即是前面都是 0num 长度的末尾都是 1 的数再异或 num 即是最终结果 }其原理是从temp 1开始不断左移直到temp num。此时temp是刚好大于num的最小 2 的幂它形如1000...0末尾 0 的个数正好等于num的二进制有效位数ktemp - 1得到低k位全 1、高位全 0 的掩码掩码与num异或即可完成低k位的翻转。以num 5为例temp依次为 1、2、4、8在8 5时停下8 - 1 70b1117 ^ 5 2答案正确。五、两种解法对比维度解法一findComplement解法二findComplement1掩码来源^0全 1向左移位到与num无交集1向左移位到刚好大于num终止条件xxnum 0temp num掩码形态高位全 1、低k位全 0再取反低k位全 1、高位全 0直接可用核心算式^xx ^ num(temp - 1) ^ num循环次数k次k次两者时间复杂度均为O(k)由于题目限定 32 位整数k ≤ 31可视为常数级空间复杂度均为O(1)。区别仅在于掩码的构造起点与终止判定解法一从「全 1」出发「消掉」低位解法二从「1」出发「补齐」低位。从源码结构看解法二对初学者的可读性更好解法一则体现了更贴近底层的位取反直觉两种写法都能通过仓库中的测试。需要特别说明的是符号位的处理题目要求不能改变符号位而两种解法的掩码都严格限制在num的有效位数k内高位含符号位所在位置的 0 在异或/取反后仍保持 0因此输出恒为非负整数符合题意。六、测试用例与运行验证仓库为本题提供了配套测试文件 476. Number Complement_test.go采用 LeetCode-Go 仓库统一的para/ans结构组织用例type question476 struct { para476 ans476 } type para476 struct { one int } type ans476 struct { one int }Test_Problem476中覆盖了与题目完全一致的两组用例para476{5}→ans476{2}对应示例 1para476{1}→ans476{0}对应示例 2测试同时调用findComplement与findComplement1两种实现输出形如【input】:5 【output】:2的日志。若想在本地复现可在仓库根目录执行go test -v ./leetcode/0476.Number-Complement/ -run Test_Problem476整个仓库通过 gotest.sh 以-covermodeatomic -coverprofilecoverage.txt ./leetcode/...的方式对全部题解做覆盖率统计本题的源码与测试文件均位于标准题解目录结构中可直接并入该测试流程。七、位运算专题中的定位与延伸476 题属于典型的「位运算」入门题其核心考点正是「掩码构造」。在仓库的 topic/Bit_Manipulation.pngLeetCode Bit Manipulation 专题题目列表截图中476. Number Complement 被归入 Easy 难度与 Single Number、Number of 1 Bits、Power of Two、Hamming Distance 等经典位运算题并列。掌握「构造低k位掩码」后可以顺带理解一类同源题目Reverse Bits190同样需要限定在固定位宽内操作只是将「翻转 0/1」换成「翻转位置」Power of Two231利用n (n-1) 0判断与解法二中temp - 1的掩码思想同源Number of 1 Bits191依赖n (n-1)逐位消去最低位的 1与解法一xxnum的判定逻辑互为镜像。这类「有效位长度感知」的处理方式是后续处理 IP 地址掩码、位图压缩、哈希散列等工程场景的通用底层能力。建议读者在掌握本题两种解法后亲手在 LeetCode 上以 5、1、8、0 附近的边界值验证掩码构造的正确性即可彻底吃透这一位运算模式。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考