LeetCode 693：交替位二进制数的位运算判断技巧

1. 题目到底在问什么：交替位二进制数的本质

刚看到“交替位二进制数”这个题名，很多朋友第一反应是“又要写一个判断函数”，但真正动手之后才发现，这题考的是对二进制位模式的理解和位运算的基本功。LeetCode 693 的要求很简单：给定一个正整数n，判断它的二进制表示中，相邻两位是否总是不同的。也就是说，二进制串必须是101010...或者010101...这种交替模式，不能出现11或00连续出现的情况。

举个例子，5的二进制是101，交替，返回true；7的二进制是111，不交替，返回false；10的二进制是1010，交替，返回true；11的二进制是1011，末尾两位都是1，不交替。别看题目简单，它其实是位运算爱好者非常喜欢的一类“模式识别”题，适合用来练习对二进制位的敏感度，也为后面做更复杂的位操作题（比如统计连续1的个数、找最长交替段）打下基础。

这题适合谁来刷？如果你是刚接触位运算的初学者，这道题能帮你理解右移、按位与、异或这些基础操作的配合使用；如果你已经刷了一段时间，想巩固“转化为字符串”之外的位运算技巧，这道题也能让你写出更优雅的解法。我见过很多人一上来就转换成字符串，然后逐个字符比较，那样当然能过，但总觉得差点意思——既然题目专门强调“二进制数”，那我们就应该用位运算的思路去处理，既高效又漂亮。

2. 暴力思路先行：逐位比较也算一种解法

2.1 最朴素的逐位检查法

先别急着上位运算技巧，我们把手撕的思路走一遍，这样后面的优化才有对比。办法很简单：把n不断右移，每次取出最低位，和上一次记录的那一位比较，如果相同就直接返回false。

具体操作是这样的：

1. 先取n的最低位last = n & 1；
2. 让n >>= 1，把原来的次低位移到最低位；
3. 再取当前最低位cur = n & 1；
4. 比较last和cur，如果相同，说明出现了两个连续的相同位，直接返回false；
5. 更新last = cur，继续循环直到n变为0；
6. 如果整个循环结束都没有返回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 核心观察：交替位的二进制数到底有什么特征

我们不妨把几个交替数的二进制列出来观察：

它们的一个显著特点是：二进制中每一位都和相邻位相反。换句话说，如果把所有位都“拉平”，相邻位异或的结果应该全是1。怎么把“相邻位异或”批量算出来？一个经典技巧是n ^ (n >> 1)。

举个例子，5的二进制是101，5 >> 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不是全1，m & (m + 1)就不会等于0。比如m = 101，m + 1 = 110，101 & 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 = 1值得注意：它的二进制只有一个1，没有相邻位，按位运算时n ^ (n >> 1)等于1 ^ 0 = 1，1 & (1+1) = 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，异或为0xc0000000，m & (m+1)是否为零？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，二进制是1001，n >> 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^18，n ^ (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（二进制111），m & (m+1) = 7 & 8 = 0，全1；
• m = 5（二进制101），m & (m+1) = 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。交替序列10101（L=5）和11111的差异是偶数位？我们可以用掩码表示。但更简单的生成方式是：交替序列可以用0x55555555这种十六进制数（二进制0101...）按长度掩码得到。这里就不展开了，感兴趣的朋友可以自己推一下，也是很有意思的位运算练习。

逆问题是：给定一个交替位二进制数，如何快速得到它的长度？因为交替序列1010...其实等价于(n ^ (n >> 1))得到一个全1序列，而全1序列的位数就是n的二进制位数。所以n.bit_length()等于(n ^ (n >> 1)).bit_length()吗？验证一下，n=10（1010），n ^ (n >> 1) = 1111，长度都是4。没问题。所以如果你需要知道交替数的二进制长度，直接算异或结果的比特位长度即可。这种互相转化的思维，都在一道简单题里。

我在实际刷题中，最喜欢的还是这次学到的m & (m + 1)这个套路，它让我重新审视了“连续1”这个看似简单的概念。如果你在刷题过程中也遇到类似卡点，建议把这道题收藏起来，时常拿出来看看，它会像一个钥匙，帮你打开很多位运算题的门。