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.

 

这道题让我们判断一个二进制数的1和0是否是交替出现的,博主开始也美想到啥简便方法,就一位一位来检测呗,用个变量bit来记录上一个位置的值,初始化为-1,然后我们用‘与’1的方法来获取最低位的值,如果是1,那么当此时bit已经是1的话,说明两个1相邻了,返回false,否则bit赋值为1。同理,如果是0,那么当此时bit已经是0的话,说明两个0相邻了,返回false,否则bit赋值为0。判断完别忘了将n向右移动一位。如果while循环退出了,返回true,参见代码如下:

 

解法一:

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int bit = -1;
        while (n > 0) {
            if (n & 1 == 1) {
                if (bit == 1) return false;
                bit = 1;
            } else {
                if (bit == 0) return false;
                bit = 0;
            }
            n >>= 1;
        }
        return true;
    }
};

 

下面这种解法写的更加简洁了,我们不需要用if条件来判断,而是可以通过‘亦或’1的方式来将0和1互换,当然我们也可以通过d = 1 - d 来达到同样的效果,但还是写成‘亦或’1比较叼,while循环的条件是最低位等于d,而d不停的在0和1之间切换,n每次也向右平移一位,这样能交替检测0和1,循环退出后,如果n为0,则返回true,反之则返回false,参见代码如下:

 

解法二:

class Solution {
public:
    bool hasAlternatingBits(int n) {
        int d = n & 1;
        while ((n & 1) == d) {
            d ^= 1;
            n >>= 1;
        }
        return n == 0;
    }
};

 

下面这种解法就十分的巧妙了,利用了0和1的交替的特性,进行错位相加,从而组成全1的二进制数,然后再用一个检测全1的二进制数的trick,就是‘与’上加1后的数,因为全1的二进制数加1,就会进一位,并且除了最高位,其余位都是0,跟原数相‘与’就会得0,所以我们可以这样判断。比如n是10101,那么n>>1就是1010,二者相加就是11111,再加1就是100000,二者相‘与’就是0,参见代码如下:

 

解法三:

class Solution {
public:
    bool hasAlternatingBits(int n) {
        return ((n + (n >> 1) + 1) & (n + (n >> 1))) == 0;
    }
};

 

下面这种解法也很巧妙,先将n右移两位,再和原来的n亦或,得到的新n其实就是除了最高位,其余都是0的数,然后再和自身减1的数相‘与’,如果是0就返回true,反之false。比如n是10101,那么n/4是101,二者相‘亦或’,得到10000,此时再减1,为1111,二者相‘与’得0,参见代码如下:

 

解法四:

class Solution {
public:
    bool hasAlternatingBits(int n) {
        return ((n ^= n / 4) & (n - 1)) == 0;
    }
};

 

类似题目:

Number of 1 Bits

 

参考资料:

https://discuss.leetcode.com/topic/106280/c-concise-code

https://discuss.leetcode.com/topic/106356/oneliners-c-java-ruby-python 

https://discuss.leetcode.com/topic/106295/java-c-very-simple-solution-1-line

 

LeetCode All in One 题目讲解汇总(持续更新中…) 


转载请注明来源于 Grandyang 的博客 (grandyang.com),欢迎对文章中的引用来源进行考证,欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论,也可以邮件至 grandyang@qq.com

💰


微信打赏


Venmo 打赏

(欢迎加入博主的知识星球,博主将及时答疑解惑,并分享刷题经验与总结,试运营期间前五十位可享受半价优惠~)

×

Help us with donation