题目描述
给定一个正整数,检查它的二进制表示是否总是 0、1 交替出现:换句话说,就是二进制表示中相邻两位的数字永不相同。
样例
输入:n = 5
输出:true
解释:5 的二进制表示是:101
输入:n = 7
输出:false
解释:7 的二进制表示是:111
输入:n = 11
输出:false
解释:11 的二进制表示是:1011
输入:n = 10
输出:true
解释:10 的二进制表示是:1010
输入:n = 3
输出:false
限制
1 <= n <= 2^31 - 1
算法
(模拟) $O(\log n)$
- 每次判断当前的二进制位是否与上一次的相等。
时间复杂度
- 需要 $O(\log n)$ 的时间遍历所有二进制位。
空间复杂度
- 仅需要常数的额外空间。
C++ 代码
class Solution {
public:
bool hasAlternatingBits(int n) {
int last = -1;
for (; n; n >>= 1) {
if (last == (n & 1))
return false;
last = n & 1;
}
return true;
}
};