1. 题目到底在问什么交替位二进制数的本质刚看到“交替位二进制数”这个题名很多朋友第一反应是“又要写一个判断函数”但真正动手之后才发现这题考的是对二进制位模式的理解和位运算的基本功。LeetCode 693 的要求很简单给定一个正整数n判断它的二进制表示中相邻两位是否总是不同的。也就是说二进制串必须是101010...或者010101...这种交替模式不能出现11或00连续出现的情况。举个例子5的二进制是101交替返回true7的二进制是111不交替返回false10的二进制是1010交替返回true11的二进制是1011末尾两位都是1不交替。别看题目简单它其实是位运算爱好者非常喜欢的一类“模式识别”题适合用来练习对二进制位的敏感度也为后面做更复杂的位操作题比如统计连续1的个数、找最长交替段打下基础。这题适合谁来刷如果你是刚接触位运算的初学者这道题能帮你理解右移、按位与、异或这些基础操作的配合使用如果你已经刷了一段时间想巩固“转化为字符串”之外的位运算技巧这道题也能让你写出更优雅的解法。我见过很多人一上来就转换成字符串然后逐个字符比较那样当然能过但总觉得差点意思——既然题目专门强调“二进制数”那我们就应该用位运算的思路去处理既高效又漂亮。2. 暴力思路先行逐位比较也算一种解法2.1 最朴素的逐位检查法先别急着上位运算技巧我们把手撕的思路走一遍这样后面的优化才有对比。办法很简单把n不断右移每次取出最低位和上一次记录的那一位比较如果相同就直接返回false。具体操作是这样的先取n的最低位last n 1让n 1把原来的次低位移到最低位再取当前最低位cur n 1比较last和cur如果相同说明出现了两个连续的相同位直接返回false更新last cur继续循环直到n变为0如果整个循环结束都没有返回false说明确实交替返回true。这里面有一个细节需要注意如果n变成0了循环自然终止不需要再比较。因为正整数的二进制最高位一定是1在右移过程中当只剩最高位时cur取到的就是最高位之后n 1变成0循环结束。也就是说最高位只被比较了一次不会和它前面的“空位”比较这个逻辑是正确的。用代码写出来就是这样def hasAlternatingBits(n: int) - bool: last n 1 n 1 while n: cur n 1 if last cur: return False last cur n 1 return True这个解法的时间复杂度是O(1)因为 int 的位数固定例如 32 位最多循环 32 次空间复杂度O(1)。虽然它不算极致优雅但胜在直观适合面试时先给面试官讲清楚思路再过渡到位运算一行解。2.2 字符串转换法为什么我不推荐作为主解还有不少人习惯于用 Python 的bin(n)把数字变成字符串然后遍历比较相邻字符。代码大概长这样def hasAlternatingBits(n: int) - bool: s bin(n)[2:] for i in range(1, len(s)): if s[i] s[i - 1]: return False return True这种写法当然能通过而且看起来非常简单。但我始终觉得这是“用字符串的思维解二进制题”没有真正利用二进制本身的数学特性。一方面它涉及到字符串的构造和遍历实际运行效率并不比位运算高另一方面这道题的核心在于“位模式”如果养成无脑转字符串的习惯遇到更复杂的位操作题比如要求不借助循环判断某个位模式是否存在就会吃亏。所以我建议你至少掌握位运算的解法字符串法可以作为验证答案的辅助手段。3. 位运算优雅解三步走从n ^ (n 1)到n (n 1)3.1 核心观察交替位的二进制数到底有什么特征我们不妨把几个交替数的二进制列出来观察n二进制是否交替11是210是5101是101010是2110101是42101010是它们的一个显著特点是二进制中每一位都和相邻位相反。换句话说如果把所有位都“拉平”相邻位异或的结果应该全是1。怎么把“相邻位异或”批量算出来一个经典技巧是n ^ (n 1)。举个例子5的二进制是1015 1得到010注意实际二进制前面会有前导0但按位异或时自动补齐101 ^ 010 111。这个结果很有意思只要原数的相邻位都不同异或结果就会呈现一串连续的1位数比原数少一位。反过来说如果原数某个位置出现相邻两位相同异或结果的对应位就会变成0从而破坏“全1”的模式。所以判断交替位本质上就变成了n ^ (n 1)的结果是否由连续的1组成也就是形如111...11。3.2 如何快速判断一个数是否全为 1判断m n ^ (n 1)是否全为1最经典的操作是m (m 1) 0。为什么因为如果m是111那么m 1就是1000两者按位与的结果是000。反过来只要m不是全1m (m 1)就不会等于0。比如m 101m 1 110101 110 100非零。这个判断技巧非常常用其实质是检查一个数是否为“2的幂减1”即二进制全1。很多位运算题里都用它来验证“一串连续1”的存在。结合起来我们就能写出超级简洁的代码def hasAlternatingBits(n: int) - bool: m n ^ (n 1) return m (m 1) 0只有两行一行计算一行判断。我第一次看到这个解法时愣了一下——原来交替位二进制数的充要条件就是相邻位异或之后得到一个全1的序列。这是非常漂亮的推理也是这道题最值得记住的地方。3.3 另一种视角用n (n 1)和n | (n 1)组合判断如果你觉得上面的思路还不够直击本质我们还可以从另一个方向切入一个数如果是交替位那么它自身和右移一位后的数在每一位上必定互斥。也就是说n (n 1)应该等于0因为“互斥”意味着没有一位同时为1同时n | (n 1)应该得到一个连续的“低位全1”序列。这里稍微解释一下对于交替位二进制数1010右移一位是0101按位与时每一位都是0所以n (n 1) 0。但是反过来n (n 1) 0并不一定意味着交替。比如n 1001二进制1001右移得到0100按位与也是0但它显然不是交替位末尾两位是01最高两位是10但中间隔了两位等等1001的相邻位是1-0、0-0、0-1第二位和第三位都是0不满足交替。所以单靠n (n 1) 0是不够的。于是我们需要再加上n | (n 1)必须是一个“全1序列”的条件。注意这里的“全1序列”不是指整个二进制位全为1而是指从最低位到最高位之间没有0空洞。由于n和n 1在每一位上至少有一个是1否则该位就都是0那这位是空位所以按位或的结果正好能把交替位“填满”。判断一个数是否为“低位连续1”同样可以用m (m 1) 0来实现其中m n | (n 1)。写成代码def hasAlternatingBits(n: int) - bool: # 无同位的1且或运算后是低位连续1 return (n (n 1)) 0 and ((n | (n 1)) ((n | (n 1)) 1)) 0这个写法虽然长了一点但它从“互斥”和“填满”两个角度刻画了交替位逻辑上更完备。不过相比n ^ (n 1)的一行解显得有些绕实际工程中我还是推荐用异或版本。4. 边界条件与细节坑从n 1到n 2147483647刷题不做边界测试等于白刷。这道题虽然简单但有几个边界值非常容易踩坑我在这里整理一下我自己的测试记录。n二进制预期结果我的第一版代码是否通过11true通过210true通过311false通过4100false注意100相邻位是10和00不交替5101true通过7111false通过81000false通过101010true通过111011false通过2110101true通过42101010true通过1431655765101010...0101true通过1431655766101010...0110false通过其中n 1值得注意它的二进制只有一个1没有相邻位按位运算时n ^ (n 1)等于1 ^ 0 11 (11) 0返回true。逻辑上单一位视为交替位是正确的因为不存在相邻相同的情况。如果题目要求正整数1必须别漏掉。另外一个大坑是 Python 的无限精度整数。虽然题目默认 int 是 32 位有符号但如果你在 Python 里用n ^ (n 1)计算对于特别大的数也没问题因为 Python 的整数位数自动扩展。不过要注意如果你在 C 或 Java 里声明int当n是2147483647即0x7fffffff二进制全1但不交替时右移一位的结果是0x3fffffff异或之后是0x40000000按位与m (m 1)结果是0等等0x40000000 0x40000001 0x40000000非零判断正确。但如果n恰好是0x80000000二进制100...0右移一位得到0x40000000异或为0xc0000000m (m1)是否为零0xc0000000 1 0xc0000001与运算后0xc0000000非零结果正确。所以问题不大。还有一个细节在 C 中右移对于有符号数是算术右移补符号位对于正数没问题因为符号位是0右移高位补0但如果n是int且非负不用考虑负数情况。LeetCode 上的约束是1 n 10^9所以不会出现负数。4.1 为什么有些解法里要减到只剩低位我看到评论区有人讨论为什么n (n 1)等于 0 还不够还要检查n | (n 1)是全1这里我再用一个反例强调一下。比如n 9二进制是1001n 1是100按位与得到0000但相邻位中0和0相邻中间两位所以不交替。所以只用“没有相邻1”来推断交替位会把1001这种“1和1不相邻但存在相邻0”的情况误判为合法。交替位的完整条件有两个不能有相邻的1也不能有相邻的0。第一个条件用n (n 1) 0保证第二个条件用n | (n 1)的全1序列来保证。理解了这两个约束你就不会被这类反例难倒。5. 代码实现细节三种语言的写法对比5.1 Python 写法Python 的位运算与直觉一致直接写就行。推荐的最优解def hasAlternatingBits(n: int) - bool: m n ^ (n 1) return m (m 1) 0这版代码在一行内完成计算和判断可读性也不错。如果你担心别人看不懂可以加一行注释def hasAlternatingBits(n: int) - bool: # 相邻位异或后应该得到一串连续的1形如 111... return ((n ^ (n 1)) ((n ^ (n 1)) 1)) 0注意这里重复计算了两次n ^ (n 1)虽然不影响正确性但会让代码显得啰嗦。建议赋值给一个变量。实际比赛中位运算量极小重复计算也完全没问题但写清楚点总没坏处。5.2 Java 写法Java 的语法也差不多只是需要注意括号class Solution { public boolean hasAlternatingBits(int n) { int m n ^ (n 1); return (m (m 1)) 0; } }这里没有特别多要注意的int 默认就是 32 位移位运算对于正数安全。唯一可能出错的点是运算符优先级的优先级低于吗实际上在 Java 里位运算的优先级低于所以必须加括号(m (m 1)) 0否则编译报错或者逻辑错误。Python 里也有类似问题所以无脑加括号最安全。5.3 C 写法C 和 Java 类似但要小心整数类型是int还是long。如果题目范围放宽到10^18n ^ (n 1)的结果可能超过 32 位这时用long long更稳妥。这里按题目范围使用int即可#include iostream using namespace std; class Solution { public: bool hasAlternatingBits(int n) { int m n ^ (n 1); return (m (m 1)) 0; } };很多 C 的初学者会在return表达式里直接写n ^ (n 1) (n ^ (n 1)) 1 0这会因为运算符优先级导致完全不同的结果。所以我建议所有位运算表达式都加上括号这是防止调试半天发现自己被优先级坑了的最佳手段。6. 进阶思考从这道题你还能学到什么6.1m (m 1)是一个万能“全1序列”检测器这道题的核心技巧m (m 1) 0在实际刷题中出现的频率非常高。它不仅可以检测二进制是否全为1还可以用来判断一个数是否为“低位连续1”。比如m 7二进制111m (m1) 7 8 0全1m 5二进制101m (m1) 5 6 4非0说明中间有0。这个技巧在很多涉及到“连续一段1”的题目里都能用比如判断一个二进制串是否是有效的掩码或者在某些位压缩DP里判断状态是否合法。建议你专门记一下这个惯用法。6.2 从“逐位比较”到“整体模式识别”的思维跃迁很多人刷题题量上去了但思维能力没提升原因在于总是满足于暴力解。这道题最好的地方在于它用一个小例子展示了如何把一个“序列问题”转化为“整体数论问题”。你不需要一位一位去查而是通过移位和异或把“相邻位是否不同”压缩成一个全局性质的判断。这种思维迁移能力是刷题的核心收益之一。以后遇到类似的问题比如“判断n的二进制是否包含连续两个1”你可以直接用(n (n 1)) 0来判断遇到“统计二进制中1的个数”可以用n (n - 1)。这些位运算惯用法积累多了解题速度会明显提升。6.3 刷题平台上的扩展话题LeetCode 周赛与相关题单最近 LeetCode 周赛也频繁出现位运算相关题目很多都是基于这类基础操作进行变形。例如“交替位二进制数”的变种题让你判断某个区间内有多少个数具备这种性质或者是求第k个交替位二进制数。如果你掌握了异或之后全1的判断这些变种题会容易很多。我在刷 LeetCode 热门100题时也经常看到类似技巧比如“只出现一次的数字”系列就利用了异或的性质。所以千万别觉得一道简单题不重要它是你位运算社区的门票。7. 实战测试与踩坑记录我在跑这道题时遇到的问题我最初自己写的时候第一反应是转字符串过了以后觉得太没技术含量就开始尝试位运算。当时我用了n (n 1) 0这个条件自信地提交结果在n 9这个用例上挂了。那时候我才意识到“没有相邻1”不等于“交替”还需要保证没有相邻0。后来看题解才想到用n ^ (n 1)一步到位。这个教训提醒我判断一个模式是否成立不能只看其中一个条件要把正反两面都想到。另一个坑是在 Java 里写返回值时没加括号。我一开始写的是return (n ^ (n 1)) ((n ^ (n 1)) 1) 0;大家猜猜结果是什么因为 Java 中优先级低于所以实际等价于(n ^ (n 1)) (((n ^ (n 1)) 1) 0)也就是把一个整数和一个布尔值做按位与编译都不通过。很多初学者大概都会栽在这里。所以还是那句话括号要加满不要迷信自己的优先级记忆。如果你在本地调试时发现结果不对建议先打印出n的二进制、n 1的二进制、异或结果一眼就能看出问题。比如n 10时1010和0101异或得到1111这就很明显。调试位运算题目时这个“打印二进制”的小技巧比断点还要好用。8. 扩展交替位数的生成与逆问题最后再聊点有趣的。既然要判断一个数是否是交替位二进制数那么反过来如何快速生成第k个交替位二进制数其实交替位二进制数只有两种模式以1开头形如1010...和以0开头但正整数不能以0开头所以只有以1开头的模式。对于长度为L的交替位二进制数其实就是(1 L) - 1和某个掩码异或的结果我们来推一下。以1开头的长度为L的交替位序列如果L是奇数那么最低位也是1恰好等于(1 L) - 1的奇偶位模式不对(1 L) - 1是L个1。交替序列10101L5和11111的差异是偶数位我们可以用掩码表示。但更简单的生成方式是交替序列可以用0x55555555这种十六进制数二进制0101...按长度掩码得到。这里就不展开了感兴趣的朋友可以自己推一下也是很有意思的位运算练习。逆问题是给定一个交替位二进制数如何快速得到它的长度因为交替序列1010...其实等价于(n ^ (n 1))得到一个全1序列而全1序列的位数就是n的二进制位数。所以n.bit_length()等于(n ^ (n 1)).bit_length()吗验证一下n101010n ^ (n 1) 1111长度都是4。没问题。所以如果你需要知道交替数的二进制长度直接算异或结果的比特位长度即可。这种互相转化的思维都在一道简单题里。我在实际刷题中最喜欢的还是这次学到的m (m 1)这个套路它让我重新审视了“连续1”这个看似简单的概念。如果你在刷题过程中也遇到类似卡点建议把这道题收藏起来时常拿出来看看它会像一个钥匙帮你打开很多位运算题的门。
1. 题目到底在问什么交替位二进制数的本质刚看到“交替位二进制数”这个题名很多朋友第一反应是“又要写一个判断函数”但真正动手之后才发现这题考的是对二进制位模式的理解和位运算的基本功。LeetCode 693 的要求很简单给定一个正整数n判断它的二进制表示中相邻两位是否总是不同的。也就是说二进制串必须是101010...或者010101...这种交替模式不能出现11或00连续出现的情况。举个例子5的二进制是101交替返回true7的二进制是111不交替返回false10的二进制是1010交替返回true11的二进制是1011末尾两位都是1不交替。别看题目简单它其实是位运算爱好者非常喜欢的一类“模式识别”题适合用来练习对二进制位的敏感度也为后面做更复杂的位操作题比如统计连续1的个数、找最长交替段打下基础。这题适合谁来刷如果你是刚接触位运算的初学者这道题能帮你理解右移、按位与、异或这些基础操作的配合使用如果你已经刷了一段时间想巩固“转化为字符串”之外的位运算技巧这道题也能让你写出更优雅的解法。我见过很多人一上来就转换成字符串然后逐个字符比较那样当然能过但总觉得差点意思——既然题目专门强调“二进制数”那我们就应该用位运算的思路去处理既高效又漂亮。2. 暴力思路先行逐位比较也算一种解法2.1 最朴素的逐位检查法先别急着上位运算技巧我们把手撕的思路走一遍这样后面的优化才有对比。办法很简单把n不断右移每次取出最低位和上一次记录的那一位比较如果相同就直接返回false。具体操作是这样的先取n的最低位last n 1让n 1把原来的次低位移到最低位再取当前最低位cur n 1比较last和cur如果相同说明出现了两个连续的相同位直接返回false更新last cur继续循环直到n变为0如果整个循环结束都没有返回false说明确实交替返回true。这里面有一个细节需要注意如果n变成0了循环自然终止不需要再比较。因为正整数的二进制最高位一定是1在右移过程中当只剩最高位时cur取到的就是最高位之后n 1变成0循环结束。也就是说最高位只被比较了一次不会和它前面的“空位”比较这个逻辑是正确的。用代码写出来就是这样def hasAlternatingBits(n: int) - bool: last n 1 n 1 while n: cur n 1 if last cur: return False last cur n 1 return True这个解法的时间复杂度是O(1)因为 int 的位数固定例如 32 位最多循环 32 次空间复杂度O(1)。虽然它不算极致优雅但胜在直观适合面试时先给面试官讲清楚思路再过渡到位运算一行解。2.2 字符串转换法为什么我不推荐作为主解还有不少人习惯于用 Python 的bin(n)把数字变成字符串然后遍历比较相邻字符。代码大概长这样def hasAlternatingBits(n: int) - bool: s bin(n)[2:] for i in range(1, len(s)): if s[i] s[i - 1]: return False return True这种写法当然能通过而且看起来非常简单。但我始终觉得这是“用字符串的思维解二进制题”没有真正利用二进制本身的数学特性。一方面它涉及到字符串的构造和遍历实际运行效率并不比位运算高另一方面这道题的核心在于“位模式”如果养成无脑转字符串的习惯遇到更复杂的位操作题比如要求不借助循环判断某个位模式是否存在就会吃亏。所以我建议你至少掌握位运算的解法字符串法可以作为验证答案的辅助手段。3. 位运算优雅解三步走从n ^ (n 1)到n (n 1)3.1 核心观察交替位的二进制数到底有什么特征我们不妨把几个交替数的二进制列出来观察n二进制是否交替11是210是5101是101010是2110101是42101010是它们的一个显著特点是二进制中每一位都和相邻位相反。换句话说如果把所有位都“拉平”相邻位异或的结果应该全是1。怎么把“相邻位异或”批量算出来一个经典技巧是n ^ (n 1)。举个例子5的二进制是1015 1得到010注意实际二进制前面会有前导0但按位异或时自动补齐101 ^ 010 111。这个结果很有意思只要原数的相邻位都不同异或结果就会呈现一串连续的1位数比原数少一位。反过来说如果原数某个位置出现相邻两位相同异或结果的对应位就会变成0从而破坏“全1”的模式。所以判断交替位本质上就变成了n ^ (n 1)的结果是否由连续的1组成也就是形如111...11。3.2 如何快速判断一个数是否全为 1判断m n ^ (n 1)是否全为1最经典的操作是m (m 1) 0。为什么因为如果m是111那么m 1就是1000两者按位与的结果是000。反过来只要m不是全1m (m 1)就不会等于0。比如m 101m 1 110101 110 100非零。这个判断技巧非常常用其实质是检查一个数是否为“2的幂减1”即二进制全1。很多位运算题里都用它来验证“一串连续1”的存在。结合起来我们就能写出超级简洁的代码def hasAlternatingBits(n: int) - bool: m n ^ (n 1) return m (m 1) 0只有两行一行计算一行判断。我第一次看到这个解法时愣了一下——原来交替位二进制数的充要条件就是相邻位异或之后得到一个全1的序列。这是非常漂亮的推理也是这道题最值得记住的地方。3.3 另一种视角用n (n 1)和n | (n 1)组合判断如果你觉得上面的思路还不够直击本质我们还可以从另一个方向切入一个数如果是交替位那么它自身和右移一位后的数在每一位上必定互斥。也就是说n (n 1)应该等于0因为“互斥”意味着没有一位同时为1同时n | (n 1)应该得到一个连续的“低位全1”序列。这里稍微解释一下对于交替位二进制数1010右移一位是0101按位与时每一位都是0所以n (n 1) 0。但是反过来n (n 1) 0并不一定意味着交替。比如n 1001二进制1001右移得到0100按位与也是0但它显然不是交替位末尾两位是01最高两位是10但中间隔了两位等等1001的相邻位是1-0、0-0、0-1第二位和第三位都是0不满足交替。所以单靠n (n 1) 0是不够的。于是我们需要再加上n | (n 1)必须是一个“全1序列”的条件。注意这里的“全1序列”不是指整个二进制位全为1而是指从最低位到最高位之间没有0空洞。由于n和n 1在每一位上至少有一个是1否则该位就都是0那这位是空位所以按位或的结果正好能把交替位“填满”。判断一个数是否为“低位连续1”同样可以用m (m 1) 0来实现其中m n | (n 1)。写成代码def hasAlternatingBits(n: int) - bool: # 无同位的1且或运算后是低位连续1 return (n (n 1)) 0 and ((n | (n 1)) ((n | (n 1)) 1)) 0这个写法虽然长了一点但它从“互斥”和“填满”两个角度刻画了交替位逻辑上更完备。不过相比n ^ (n 1)的一行解显得有些绕实际工程中我还是推荐用异或版本。4. 边界条件与细节坑从n 1到n 2147483647刷题不做边界测试等于白刷。这道题虽然简单但有几个边界值非常容易踩坑我在这里整理一下我自己的测试记录。n二进制预期结果我的第一版代码是否通过11true通过210true通过311false通过4100false注意100相邻位是10和00不交替5101true通过7111false通过81000false通过101010true通过111011false通过2110101true通过42101010true通过1431655765101010...0101true通过1431655766101010...0110false通过其中n 1值得注意它的二进制只有一个1没有相邻位按位运算时n ^ (n 1)等于1 ^ 0 11 (11) 0返回true。逻辑上单一位视为交替位是正确的因为不存在相邻相同的情况。如果题目要求正整数1必须别漏掉。另外一个大坑是 Python 的无限精度整数。虽然题目默认 int 是 32 位有符号但如果你在 Python 里用n ^ (n 1)计算对于特别大的数也没问题因为 Python 的整数位数自动扩展。不过要注意如果你在 C 或 Java 里声明int当n是2147483647即0x7fffffff二进制全1但不交替时右移一位的结果是0x3fffffff异或之后是0x40000000按位与m (m 1)结果是0等等0x40000000 0x40000001 0x40000000非零判断正确。但如果n恰好是0x80000000二进制100...0右移一位得到0x40000000异或为0xc0000000m (m1)是否为零0xc0000000 1 0xc0000001与运算后0xc0000000非零结果正确。所以问题不大。还有一个细节在 C 中右移对于有符号数是算术右移补符号位对于正数没问题因为符号位是0右移高位补0但如果n是int且非负不用考虑负数情况。LeetCode 上的约束是1 n 10^9所以不会出现负数。4.1 为什么有些解法里要减到只剩低位我看到评论区有人讨论为什么n (n 1)等于 0 还不够还要检查n | (n 1)是全1这里我再用一个反例强调一下。比如n 9二进制是1001n 1是100按位与得到0000但相邻位中0和0相邻中间两位所以不交替。所以只用“没有相邻1”来推断交替位会把1001这种“1和1不相邻但存在相邻0”的情况误判为合法。交替位的完整条件有两个不能有相邻的1也不能有相邻的0。第一个条件用n (n 1) 0保证第二个条件用n | (n 1)的全1序列来保证。理解了这两个约束你就不会被这类反例难倒。5. 代码实现细节三种语言的写法对比5.1 Python 写法Python 的位运算与直觉一致直接写就行。推荐的最优解def hasAlternatingBits(n: int) - bool: m n ^ (n 1) return m (m 1) 0这版代码在一行内完成计算和判断可读性也不错。如果你担心别人看不懂可以加一行注释def hasAlternatingBits(n: int) - bool: # 相邻位异或后应该得到一串连续的1形如 111... return ((n ^ (n 1)) ((n ^ (n 1)) 1)) 0注意这里重复计算了两次n ^ (n 1)虽然不影响正确性但会让代码显得啰嗦。建议赋值给一个变量。实际比赛中位运算量极小重复计算也完全没问题但写清楚点总没坏处。5.2 Java 写法Java 的语法也差不多只是需要注意括号class Solution { public boolean hasAlternatingBits(int n) { int m n ^ (n 1); return (m (m 1)) 0; } }这里没有特别多要注意的int 默认就是 32 位移位运算对于正数安全。唯一可能出错的点是运算符优先级的优先级低于吗实际上在 Java 里位运算的优先级低于所以必须加括号(m (m 1)) 0否则编译报错或者逻辑错误。Python 里也有类似问题所以无脑加括号最安全。5.3 C 写法C 和 Java 类似但要小心整数类型是int还是long。如果题目范围放宽到10^18n ^ (n 1)的结果可能超过 32 位这时用long long更稳妥。这里按题目范围使用int即可#include iostream using namespace std; class Solution { public: bool hasAlternatingBits(int n) { int m n ^ (n 1); return (m (m 1)) 0; } };很多 C 的初学者会在return表达式里直接写n ^ (n 1) (n ^ (n 1)) 1 0这会因为运算符优先级导致完全不同的结果。所以我建议所有位运算表达式都加上括号这是防止调试半天发现自己被优先级坑了的最佳手段。6. 进阶思考从这道题你还能学到什么6.1m (m 1)是一个万能“全1序列”检测器这道题的核心技巧m (m 1) 0在实际刷题中出现的频率非常高。它不仅可以检测二进制是否全为1还可以用来判断一个数是否为“低位连续1”。比如m 7二进制111m (m1) 7 8 0全1m 5二进制101m (m1) 5 6 4非0说明中间有0。这个技巧在很多涉及到“连续一段1”的题目里都能用比如判断一个二进制串是否是有效的掩码或者在某些位压缩DP里判断状态是否合法。建议你专门记一下这个惯用法。6.2 从“逐位比较”到“整体模式识别”的思维跃迁很多人刷题题量上去了但思维能力没提升原因在于总是满足于暴力解。这道题最好的地方在于它用一个小例子展示了如何把一个“序列问题”转化为“整体数论问题”。你不需要一位一位去查而是通过移位和异或把“相邻位是否不同”压缩成一个全局性质的判断。这种思维迁移能力是刷题的核心收益之一。以后遇到类似的问题比如“判断n的二进制是否包含连续两个1”你可以直接用(n (n 1)) 0来判断遇到“统计二进制中1的个数”可以用n (n - 1)。这些位运算惯用法积累多了解题速度会明显提升。6.3 刷题平台上的扩展话题LeetCode 周赛与相关题单最近 LeetCode 周赛也频繁出现位运算相关题目很多都是基于这类基础操作进行变形。例如“交替位二进制数”的变种题让你判断某个区间内有多少个数具备这种性质或者是求第k个交替位二进制数。如果你掌握了异或之后全1的判断这些变种题会容易很多。我在刷 LeetCode 热门100题时也经常看到类似技巧比如“只出现一次的数字”系列就利用了异或的性质。所以千万别觉得一道简单题不重要它是你位运算社区的门票。7. 实战测试与踩坑记录我在跑这道题时遇到的问题我最初自己写的时候第一反应是转字符串过了以后觉得太没技术含量就开始尝试位运算。当时我用了n (n 1) 0这个条件自信地提交结果在n 9这个用例上挂了。那时候我才意识到“没有相邻1”不等于“交替”还需要保证没有相邻0。后来看题解才想到用n ^ (n 1)一步到位。这个教训提醒我判断一个模式是否成立不能只看其中一个条件要把正反两面都想到。另一个坑是在 Java 里写返回值时没加括号。我一开始写的是return (n ^ (n 1)) ((n ^ (n 1)) 1) 0;大家猜猜结果是什么因为 Java 中优先级低于所以实际等价于(n ^ (n 1)) (((n ^ (n 1)) 1) 0)也就是把一个整数和一个布尔值做按位与编译都不通过。很多初学者大概都会栽在这里。所以还是那句话括号要加满不要迷信自己的优先级记忆。如果你在本地调试时发现结果不对建议先打印出n的二进制、n 1的二进制、异或结果一眼就能看出问题。比如n 10时1010和0101异或得到1111这就很明显。调试位运算题目时这个“打印二进制”的小技巧比断点还要好用。8. 扩展交替位数的生成与逆问题最后再聊点有趣的。既然要判断一个数是否是交替位二进制数那么反过来如何快速生成第k个交替位二进制数其实交替位二进制数只有两种模式以1开头形如1010...和以0开头但正整数不能以0开头所以只有以1开头的模式。对于长度为L的交替位二进制数其实就是(1 L) - 1和某个掩码异或的结果我们来推一下。以1开头的长度为L的交替位序列如果L是奇数那么最低位也是1恰好等于(1 L) - 1的奇偶位模式不对(1 L) - 1是L个1。交替序列10101L5和11111的差异是偶数位我们可以用掩码表示。但更简单的生成方式是交替序列可以用0x55555555这种十六进制数二进制0101...按长度掩码得到。这里就不展开了感兴趣的朋友可以自己推一下也是很有意思的位运算练习。逆问题是给定一个交替位二进制数如何快速得到它的长度因为交替序列1010...其实等价于(n ^ (n 1))得到一个全1序列而全1序列的位数就是n的二进制位数。所以n.bit_length()等于(n ^ (n 1)).bit_length()吗验证一下n101010n ^ (n 1) 1111长度都是4。没问题。所以如果你需要知道交替数的二进制长度直接算异或结果的比特位长度即可。这种互相转化的思维都在一道简单题里。我在实际刷题中最喜欢的还是这次学到的m (m 1)这个套路它让我重新审视了“连续1”这个看似简单的概念。如果你在刷题过程中也遇到类似卡点建议把这道题收藏起来时常拿出来看看它会像一个钥匙帮你打开很多位运算题的门。
