693. 交替位二进制数

发表于 分类于 阅读次数： Waline： 本文字数： 237 阅读时长 ≈ 1 分钟

考点

  • 移位技巧

题解

同下

思路

循环判断

传统办法，依次判断当前位是否与上一位相同即可

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
	public:
		bool hasAlternatingBits(int n) {
			int prev = 2;
			while (n) {
				int tmp = n & 1;
				if (tmp == prev) return false;
				prev = tmp;
				n = n >> 1;
			}
			return true;
		}
};

时间复杂度：\(O\left( \log n \right)\)

空间复杂度：\(O\left( 1 \right)\)

找规律

若整数是交替位二进制类型，去掉多余的前导零后，实际组成类似0101或者1010

它们向右移一位后与原数异或，可以得到全1的数；比如0101 >> 1 = 0010，0010 ^ 0101 = 0111

全1的数再加1则会进位，故而作为判断依据

这里的tmp最大值可达0x7fffffff，为避免再加1后导致溢出，需要将tmp设置为无符号数

1
2
3
4
5
6
7
class Solution {
	public:
		bool hasAlternatingBits(unsigned int n) {
			unsigned int tmp = n ^ (n >> 1);
			return (tmp & (tmp + 1)) == 0;
		}
};

时间复杂度：\(O\left( 1 \right)\)

空间复杂度：\(O\left( 1 \right)\)