693. 交替位二进制数
点击上方标题跳转至leetcode
题目描述
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
示例 1：
输入：n = 5 输出：true 解释：5 的二进制表示是：101
示例 2：
输入：n = 7 输出：false 解释：7 的二进制表示是：111.
示例 3：
输入：n = 11 输出：false 解释：11 的二进制表示是：1011.
提示：
1 <= n <= 231 - 1
解法
方法一：模拟
从最低位至最高位，我们用对 2 取模再除以 2 的方法，依次求出输入的二进制表示的每一位，并与前一位进行比较。如果相同，则不符合条件；如果每次比较都不相同，则符合条件。
方法二：模拟
n 循环右移直至为 0，依次检测 n 的二进制位是否交替出现。若循环过程中发现 0、1 没有交替出现，直接返回 false。否则循环结束返回 true。
方法三：位运算
假设 01 交替出现，那么我们可以通过错位异或将尾部全部转为 1，加 1 可以得到 2 的幂次的一个数 n（n 中只有一个位是 1），接着利用 n & (n + 1) 可以消除最后一位的 1。
此时判断是否为 0，若是，说明假设成立，是 01 交替串。
Python3
from typing import List
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
prev = 2
while n:
cur = n % 2
if cur == prev:
return False
prev = cur
n //= 2
return True
fun = Solution()
# n = 5
# n = 7
n = 11
res = fun.hasAlternatingBits(n)
print(res)
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
prev = -1
while n:
curr = n & 1
if prev == curr:
return False
prev = curr
n >>= 1
return True
class Solution:
def hasAlternatingBits(self, n: int) -> bool:
n ^= (n >> 1)
return (n & (n + 1)) == 0
C++
#include<iostream>
#include<string>
#include<string>
#include<vector>
using namespace std;
class Solution {
public:
bool hasAlternatingBits(int n) {
int prev = 2;
while(n){
int cur = n % 2;
if(cur == prev)
return false;
prev = cur;
n /=2;
}
return true;
}
};
int main(){
int n =11;
// string s ="abc";
bool res = Solution().hasAlternatingBits(n);
cout << res << endl;
return 0;
}
//g++ 693.cpp -std=c++11
class Solution {
public:
bool hasAlternatingBits(int n) {
int prev = -1;
while (n) {
int curr = n & 1;
if (prev == curr) return false;
prev = curr;
n >>= 1;
}
return true;
}
};
class Solution {
public:
bool hasAlternatingBits(int n) {
n ^= (n >> 1);
return (n & ((long) n + 1)) == 0;
}
};