### 题目描述 给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。 ### 输入输出 #### 示例1 ``` 输入：n = 5 输出：true 解释：5 的二进制表示是：101 ``` #### 示例2 ``` 输入：n = 7 输出：false 解释：7 的二进制表示是：111. ``` #### 示例3 ``` 输入：n = 11 输出：false 解释：11 的二进制表示是：1011. ``` **提示** 1 <= n <= 2^31 - 1 ### 题目解答 #### 思路1 **方法** 依次按位数进行判断，如果相同的话返回False，否则返回True。 **算法复杂度** 设数字的大小为N， 时间复杂度：其二进制表示的位数是$$o(log(n))$$, 因此按位数依次判断复杂度是log级别。 空间复杂度：空间复杂度，记录一位数，则空间复杂度O(1) #### 思路2 **方法** 采用位运算的方式，将该数字与该数字**右移**之后的数字进行**异或**运算，如果结果每一位均为1，那么该数字二进制是01交替。 那么全1的结果如何判断，将该数字+1，如果1111就会变成10000， 进行与操作就会全0 **为什么要进行右移?** 如果最后一位是1，那么右移动之后1没了变成0，异或满足。如果最后一位是0，那么右移动之后0没了变成1，异或也满足。 但是如果左移的话，如果最后1位数是0，左移又出一个0，0与0进行异或操作，结果为0，不满足条件。 **算法复杂度** 时间复杂度：该算法先异或，再与运算，复杂度$$O(1)$$ 空间复杂度：无需额外空间，也是$$O(1)$$ #### 代码实现 ```python class Solution: # 按位计算 def hasAlternatingBits(self, n: int) -> bool: record = n % 2 n = n // 2 while n > 0: rest = n % 2 if rest == record: return False record = rest n = n //2 return True def hasAlternatingBits(self, n: int) -> bool: # 必须得右移，不然如果最后一位是0，左移又多出一个0来 num = (n >> 1) ^ n return (num + 1) & num == 0 ``` 最后编辑：2024年04月23日 ©著作权归作者所有 赞 0 分享
最新回复