Link
给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。
对一个 0、1 交替的数 n，其二进制位右移一位 n >> 1 一定与其互补（低位意义上）。取 XOR 后结果 \(x\) 必然为某个 \(2^n - 1\)。
这样的 \(x\) 必然满足 \(x \& (x+1) = 0\)；实际上这也是必要条件：若 \(x\) 在低位处有 \(0\)，则 \(x+1\) 在此位至多变为 \(1\)，导致高位必然不改变。高位必然有 \(1\)，则取 AND 后必然不为 \(0\)。
由于要计算 x + 1，x 应当为无符号整数而非有符号整数。否则在 n = 0b1010101010101010101010101010101 时会导致 x == INT_MAX。
时间复杂度和空间复杂度均为 \(O(1)\)。
class Solution {
public:bool hasAlternatingBits(int n) {unsigned x = n ^ n >> 1;return (x & (x + 1)) == 0;}
};