标签: 位运算
难度: Easy
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例 1：
输入：n = 5 输出：true 解释：5 的二进制表示是：101
示例 2：
输入：n = 7 输出：false 解释：7 的二进制表示是：111.
示例 3：
输入：n = 11 输出：false 解释：11 的二进制表示是：1011.
提示：
1 <= n <= 231 - 1
Submission
运行时间: 23 ms
内存: 16.0 MB
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
pre=n&1
n>>=1
while n>0:
digit=n&1
if not pre^digit:
return False
pre=digit
n>>=1
return True
Explain
该题解的思路是通过位运算来判断相邻两位是否不同。首先记录最低位 pre，然后右移 n，每次取出最低位 digit 与 pre 做异或操作，如果异或结果为0，说明相邻两位相同，返回 False。每次迭代更新 pre 为当前 digit，继续右移 n 直至为0。如果遍历完整个二进制数都没有返回 False，则说明符合条件，返回 True。
时间复杂度: O(log(n))
空间复杂度: O(1)
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
pre = n & 1 # 记录最低位
n >>= 1 # 右移 n
while n > 0:
digit = n & 1 # 取出最低位
if not pre ^ digit: # 判断相邻两位是否不同
return False
pre = digit # 更新 pre 为当前 digit
n >>= 1 # 继续右移 n
return True # 遍历完整个二进制数都没有返回 False，则返回 True
Explore
异或操作（XOR）是一种二进制操作，当两个比较的位相同时结果为0，不同时结果为1。因此，使用异或操作可以直接判断两个相邻的位是否相同。在这个题解中，如果相邻的两位是相同的，异或的结果会是0，与期望的交替位（应该相异，即期待结果为1）不符，从而返回False。这种方法通过直接比较每一对相邻位的异或结果，确保了能有效且正确地判断二进制数是否具有交替位的特性。
在代码中，通过不断地右移操作（n >>= 1）和位与操作（n & 1）来逐位处理二进制数。每次右移操作将当前最低位移出，并在下一次迭代中通过位与操作取出新的最低位。这个过程会持续直到整个数为0，即所有位都已经被处理。这种方法适用于任何大小的整数，因为它按照二进制的形式逐位处理，不依赖于数值的实际大小。
如果二进制数的最高位和次高位相同，则它们的异或结果会是0。根据算法逻辑，如果任何一对相邻位的异或结果为0，算法将返回False。这是因为相同的结果表明它们不是交替的，这正是算法设计的核心逻辑。因此，这种情况下的异或结果直接导致算法正确地判断出二进制数不是一个交替位二进制数。
当输入的 n 是1时，算法首先将1的最低位存储为pre，然后将n右移变为0。由于没有更多的位可供处理（n已经变为0），循环结束。由于在整个过程中没有发现任何一对相邻位不满足交替位的条件（实际上只有一个位，没有相邻位可以比较），算法最终返回True。这表明，对于只有一个位的二进制数，算法认为其符合交替位的定义，这是合理的因为没有相邻位产生冲突。