判断数字二进制是否为交替位的O(1)解法失效，求排查

问题需求 #

判断一个整数的二进制表示是否由交替的1和0组成（例如1010、101这类），要求时间复杂度与空间复杂度均为O(1)。

你的思路问题分析 #

你尝试通过计算数字n的对应二进制位数的反码，然后用n & complement(n) == 0来判断，但这个逻辑根本行不通，原因如下：

• 举个反例：比如n=6（二进制110），它的反码是001（十进制1），此时6 & 1 = 0，按你的逻辑会返回true，但110明显不是交替位的二进制数。
• 本质上，n & complement(n) == 0只能说明n和它的反码没有重叠的1位，但反码是和n二进制位数相同的全1掩码异或得到的，这个条件无法区分“交替位”和其他存在连续相同位的情况。

另外你的补码函数还有个隐患：当n=0时，log2(0)会触发错误，需要额外处理。

正确的O(1)解法 #

利用交替位数字的特性就能解决：把n右移一位后和原数做异或运算，如果n是交替位，得到的结果会是全1的二进制数；接着判断这个结果加1后是否是2的幂（全1的数加1会变成1000...，这种数和它减1的按位与结果为0）。

具体代码实现：

bool hasAlternatingBits(int n) {
    if (n == 0) return true;
    long long m = (long long)n ^ (n >> 1); // 用long long避免溢出
    return (m & (m + 1)) == 0;
}

用long long是为了防止n取最大int值时，异或后的结果加1溢出int范围。

验证逻辑 #

• 当n是交替位：比如n=10（二进制1010），右移一位是0101，异或后得到1111，加1是10000，1111 & 10000 = 0，返回true。
• 当n不是交替位：比如n=6（二进制110），右移一位是011，异或后得到101，加1是110，101 & 110 = 100 != 0，返回false。

内容的提问来源于stack exchange，提问作者Pranav_Mundhra