位运算

---

题目详情

给定一个正整数，检查它的二进制表示是否总是 0、1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

---

示例1：

输入：n = 5
输出：true
解释：5 的二进制表示是：101
1
2
3

示例2:

输入：n = 7
输出：false
解释：7 的二进制表示是：111.
1
2
3

示例3:

输入：n = 11
输出：false
解释：11 的二进制表示是：1011.
1
2
3

第一种方法:正常取余逐位比较

按题目要求老老实实比较每一位和它的前一位

class Solution 
{
public:
    bool hasAlternatingBits(int n) 
    {
        int pre = -1; //注意初始化
        while (n != 0)
        {
            int cur = n % 2;

            if (cur == pre)
            return false;

            pre = cur;
            n /= 2;
        }
        return true;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

第二种方法:位运算!

举个例子你就懂了,假如有个数字101010101
我们将它右移一位,得到了010101010 ------刚刚好错位了!
相信你已经懂了,再将两者进行异或运算,如果满足交替位二进制数,就会得到111…111全是1的数
然后再根据 n&n-1 == 0的充要条件是n的二进制位上全是1 来验证即可

我的代码：

class Solution 
{
public:
    bool hasAlternatingBits(int n) 
    {
        long a = n ^ (n >> 1);//注意类型
        return (a & (a + 1)) == 0;
    }
};

1
2
3
4
5
6
7
8
9
10

位运算常用技巧