LeetCode693 交替位二进制数

发表于 | 分类于 |
字数统计: 176 | 阅读时长 ≈ 1

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

题面

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

解法

常规解法很容易，但是用位运算做比较巧妙
（想不到）
将数n和右移后的n进行异或运算，如果符合交替的二进制，就会得到1111..1的结果
再将得到的数加一后进行异或，得到10000..0，异或的结果为0就是true，否则为false

代码

1
2
3
4
5
6
7
class Solution {
public:
    bool hasAlternatingBits(int n) {
        long long num = n ^ (n >> 1);
        return (num & (num + 1)) == 0;
    }
};