693. Binary Number with Alternating Bits

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

Example 1:
Input: 5
Output: True
Explanation:
The binary representation of 5 is: 101

Example 2:
Input: 7
Output: False
Explanation:
The binary representation of 7 is: 111.

Example 3:
Input: 11
Output: False
Explanation:
The binary representation of 11 is: 1011.

Example 4:
Input: 10
Output: True
Explanation:
The binary representation of 10 is: 1010.

思路:观察易知,若满足题设的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;
    }
};