693. 交替位二进制数

https://leetcode-cn.com/problems/binary-number-with-alternating-bits/

解法一：naive

思路:观察易知,若满足题设的n为偶数,则最低位必是0,形式为1010…10.若n为奇数,则最低位必是1,形式为1010…101. 奇数减1再右移一位,即(n-1)/2,得到满足题设的偶数. 偶数右移一位,即n/2,得到满足题设的奇数. 如此交替地进行奇偶变换,不中断,直到为0,中间结果全是满足题设的数. 换句话说,不停的进行如上奇偶变换,若中途只要发生1次不满足,则判定不符合题设.

class Solution {
public:
    bool hasAlternatingBits(int n) {
        bool flag = true;//初始开关设为真
        if (n == 0) return true;
        while (n) {
            if (n%2 == 0 && (n/2)%2 == 1) {//若n为偶,且n下一次变换后为奇
                n = n/2;
                continue;
            } else if (n%2 == 1 && ((n-1)/2)%2 == 0) {//若n为奇,且下一次变换后为偶
                n = (n-1)/2;
                continue;
            } else {//若不满足如上条件
                n = n/2;
                flag = false;//开关置为假
            }
        }
        return flag;
    }
};

解法二：

超强，n与n右移一位的数异或，若是交替位二进制，结果必为1111...

这个数+1为10000...

两者相与，结果为0则是交替位二进制

class Solution:
    def hasAlternatingBits(self, n: int) -> bool:
        temp = n^n>>1
        return temp&(temp+1) == 0