LeetCode-Go 题解693. Binary Number with Alternating Bits 交替位二进制数判定与位运算剖析【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go导读本题是 LeetCode 第 693 题「Binary Number with Alternating Bits」交替位二进制数核心任务是判断一个正整数二进制表示中任意相邻两位是否互不相同。本文以 leetcode/0693.Binary-Number-with-Alternating-Bits/README.md 为骨架结合仓库中 解法源码 与 单元测试完整讲解题目语义、两种解法的实现细节、位运算背后的数学原理以及复杂度对比读完可直接复现并能举一反三地迁移到同类“相邻位关系”判定问题中。题目判定交替位二进制数题目描述给定一个正整数positive integer检查它是否为交替位二进制数alternating bits也就是说它的二进制表示中任意相邻两个位的值始终不同即 0 与 1 交替出现形如101010...或010101...。官方示例题目给出了 4 组标准示例仓库的测试用例与之一一对应输入二进制表示输出说明5101true相邻位 1-0、0-1 均不同7111false相邻位存在相同值111011false尾部11相邻两位相同101010true相邻位 1-0、0-1、1-0 均不同这 4 组用例同时被写入 693. Binary Number with Alternating Bits_test.go 的qs表驱动用例中覆盖了题目原样给出的全部输入输出。题目大意中文解读给定一个正整数检查它是否为交替位二进制数换句话说就是它的二进制数相邻的两个位永不相等。例如5 101满足条件返回true而7 111不满足返回false。解题思路总览这一题有多种做法从实现复杂度上可以分为两派直接模拟逐位取出二进制位相邻位两两比较一旦发现相等立即返回false。思路直观、零推导成本时间复杂度与二进制位数成正比。位运算构造利用n ^ (n 1)与n (n 1)两个位运算组合在一次“拍平”操作中完成判定时间复杂度为常数级是面试中更具区分度的写法。README 原文强调的思路是010101与构造出的101010两者相互做位运算以后结果为 0因为二者恰好“插空”——这正是位运算解法的核心直觉下文展开推导。解法一直接模拟逐位比较仓库中hasAlternatingBits1实现了最简单的模拟法// 解法二 func hasAlternatingBits1(n int) bool { last, current : 0, 0 for n 0 { last n 1 n n / 2 current n 1 if last current { return false } } return true }执行流程拆解循环体内共三步last n 1取当前最低位n n / 2右移一位等价于n 1准备取下一位current n 1取出移位后的新最低位即原数的次低位。随后比较last与current只要有一次相等说明存在相邻两位相同直接返回false。循环自然结束时n被除到 0说明所有相邻位都互不相同返回true。正确性说明单比特正整数如1二进制1不存在“相邻位”循环只执行一次比较即因n0退出返回true语义正确该解法只依赖相邻位关系与数的符号、进制长度无关天然覆盖所有正整数时间复杂度为 O(log n)即二进制位数空间复杂度 O(1)。解法二位运算构造“全 1”再判定仓库中hasAlternatingBits是位运算写法源码注释里给出了完整的位模式推演表// 解法一 func hasAlternatingBits(n int) bool { /* n 1 0 1 0 1 0 1 0 n 1 0 1 0 1 0 1 0 1 n ^ n1 1 1 1 1 1 1 1 1 n 1 1 1 1 1 1 1 1 n 1 1 0 0 0 0 0 0 0 0 n (n1) 0 0 0 0 0 0 0 0 */ n n ^ (n 1) return (n (n 1)) 0 }核心只有两行分两步完成判定。第一步n n ^ (n 1)将“相邻位异同”压缩成一位异或XOR的语义是“相同为 0、不同为 1”。把n与自身右移一位的结果做异或得到的每一位恰好表示原数相邻两位是否不同原数相邻位不同交替→ 对应异或位为1原数相邻位相同 → 对应异或位为0。因此“原数相邻位全部互不相同”等价于“n ^ (n 1)的结果全为 1”。以n 10二进制1010为例n 1 0 1 0 n 1 0 1 0 1 异或 1 1 1 1 ← 全 1第二步n (n 1) 0判定“全 1”形态一个数全为 1 时其二进制形态必然是111...1即形如2^k - 1。对于这种数n 1会得到1000...02^k二者按位与的结果恒为 0n 1 1 1 1 n 1 1 0 0 0 0 n (n1) 0 0 0 0 0反过来只要n不是“全 1”形态即n ^ (n 1)中存在 0 位n (n 1)就必然不为 0。因此(n (n 1)) 0是判断“某数是否为全 1”的经典位运算技巧也等价于判断n是否为2^k - 1形式的梅森数形态。与 README 直觉的对应README 中描述的“010101构造出101010两者后为 0因为都插空了”可以这样理解若交替位成立则n与n 1的每一位都互补二者在每一位上“插空”交错异或后铺满全 1随后与1进位产生的更高位再次“插空”两次插空相交为 0。这一直觉正是两步位运算的图形化表达。复杂度时间复杂度 O(1)固定次数的移位、异或、加法、按位与空间复杂度 O(1)仅使用常数个临时变量。边界情况与极端输入推演两个解法对以下边界输入的表现值得验证输入二进制预期结果模拟法行为位运算法行为11true循环一次即退出1^(11)1120→ true210true1 与 0 不同2^(1)3全 1340→ true311false1 与 1 相同3^(1)2232≠0→ false0x555555550101...交替交替true全相邻位不同异或后全 1判定通过其中0x55555555是 32 位整数中典型的“全交替”常数可作为压测用例验证解法在长位宽下的正确性而0x55555555 ^ 0x1之类的单点破坏则会让位运算解法的结果立即非零。测试验证仓库中的表驱动用例仓库为本题提供了 693. Binary Number with Alternating Bits_test.go结构采用该仓库统一的questionXXX / paraXXX / ansXXX表驱动模式para693封装输入参数one intans693封装期望输出one boolqs列表收录了题目全部 4 组示例5→true、7→false、11→false、10→true。测试主体在Test_Problem693中遍历用例同时调用hasAlternatingBits与hasAlternatingBits1两个实现并打印输入输出既验证了位运算解法的正确性也隐含校验了两个解法结果的一致性。仓库 gotest.sh 通过go test -covermodeatomic -coverprofilecoverage.txt ./leetcode/...统一跑全量测试并生成覆盖率报告运行单个用例可直接使用go test -v ./leetcode/0693.Binary-Number-with-Alternating-Bits/...两种解法对比与迁移思考维度模拟法hasAlternatingBits1位运算法hasAlternatingBits思路成本低逐位比较即可较高需要理解 XOR 压缩与全 1 判定时间复杂度O(log n)O(1)空间复杂度O(1)O(1)代码量约 10 行2 行核心逻辑面试/工程价值稳妥兜底易读易审体现位运算功底适合追求常数时间此外本题的位运算套路可以迁移到一系列“相邻位关系”判定题中判断 2 的幂n 0 (n (n - 1)) 0判断全 1形如 2^k − 1(n (n 1)) 0本题第二步统计相邻位差异数对n ^ (n 1)的结果做bits.OnesCount若等于位数减 1 即为交替位——这为“部分交替”场景提供了定量化的变体解法。总结LeetCode 693 是一道典型的“小切口”位运算题。通过仓库中的双解法源码与表驱动测试可以确认模拟法以 O(log n) 的代价换取零推导成本位运算法则利用n ^ (n 1)把“相邻位互异”这一全局性质压缩为“结果全 1”这一单点性质再借n (n 1) 0的梅森数判定技巧完成常数时间求解。掌握这条“异或压缩 全 1 判定”的思考路径比单纯背下两行代码更有价值它可以直接复用于判断 2 的幂、全 1 形态以及各类相邻位统计问题。【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考