每日一题-交替位二进制数

发表于 更新于 分类于 Waline：

693. 交替位二进制数

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/binary-number-with-alternating-bits

题目

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

提示：

  • $1 <= n <= 2^{31} - 1$

思路

根据题意比较相邻两个bit位即可，注意首先得计算出输入的数字有多少个bit位。可以找出比该数大的最小的2的幂次数，例如比11大的最小数为16有5位。比较11时只需比较到第4位即可。注意n最大为$2^{31} - 1$，因此位数不可能超过31。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
	public:
	    bool hasAlternatingBits(int n) {
		if (n == INT_MAX) {
			return false;
		}
		int k = 0;
		while(n > 1 << k) {
			++k;
			if (k == 31) {
				break;
			}
		}
		for (int i = 0 ; i < k ; ++i) {
			if ((n >> i & 1) == (n >> i+1 & 1)) {
				return false;
			}
		}
		return true;
	}
}
;