---

0693. 交替位二进制数

• 标签：位运算
• 难度：简单

题目链接

• 0693. 交替位二进制数 - 力扣

题目大意

描述：

给定一个正整数 $n$。

要求：

检查它的二进制表示是否总是 $0$、$1$ 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

说明：

• $1 \le n \le 2^{31} - 1$。

示例：

• 示例 1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101

• 示例 2：

输入：n = 7
输出：false
解释：7 的二进制表示是：111.

解题思路

思路 1：位运算

思路 1：算法描述

这道题目要求判断一个正整数的二进制表示是否总是 $0$、$1$ 交替出现。

我们可以使用位运算来解决这个问题。如果二进制表示中相邻两位的数字永不相同，那么将 $n$ 右移一位后与 $n$ 进行异或运算，得到的结果应该是所有位都为 $1$ 的数。

具体步骤如下：

1. 计算 $a = n \oplus (n >> 1)$，其中 $\oplus$ 表示异或运算。
2. 如果 $n$ 的二进制表示是交替的，那么 $a$ 的二进制表示应该是所有位都为 $1$。
3. 判断 $a$ 是否满足 $a \& (a + 1) = 0$，如果满足则返回 $True$，否则返回 $False$。

解释：如果 $a$ 的所有位都为 $1$，那么 $a + 1$ 会产生进位，使得 $a \& (a + 1) = 0$。

思路 1：代码

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        # 将 n 右移一位后与 n 异或
        a = n ^ (n >> 1)
        # 判断 a 是否所有位都为 1
        return (a & (a + 1)) == 0

思路 1：复杂度分析

• 时间复杂度：$O(1)$。只需要进行常数次位运算。
• 空间复杂度：$O(1)$。只使用了常数级别的额外空间。