693. Binary Number with Alternating Bits 交替位二进制数

作者： 负雪明烛 id： fuxuemingzhu 个人博客： http://fuxuemingzhu.cn/

---

@TOC

题目地址：https://leetcode.com/problems/binary-number-with-alternating-bits/description/

题目描述

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.

题目大意

判断一个数的二进制表示中是不是相邻的两个数字都是不同的。

解题方法

我用了 3 种不同的方法。

方法一是普通方法；方法二三都很新颖，肯定让你有收获哦！

无论你使用的什么语言，都一定看到文章最后！！

方法一：遍历判断

该想法很朴素，判断二进制数任意两个数字是否是不同的即可。

先用bin()方法，把整数转成二进制的字符串，然后判断相邻的两位是否不同。

In [1]: bin(5)
Out[1]: '0b101'

注意 bin()方法返回值前面两个字符时 0b 需要裁剪掉。

判断时，可以用相加为 1来判断，也可以直接用 **不等 **来判断。

class Solution(object):
    def hasAlternatingBits(self, n):
        """
        :type n: int
        :rtype: bool
        """
        bin_n = bin(n)[2:]
        return all(int(bin_n[i]) + int(bin_n[i+1]) == 1 for i in xrange(len(bin_n) - 1))

直接判断相邻的数字是不同的：

class Solution(object):
    def hasAlternatingBits(self, n):
        """
        :type n: int
        :rtype: bool
        """
        bin_n = bin(n)[2:]
        return all(bin_n[i] != bin_n[i+1] for i in xrange(len(bin_n) - 1))

方法二：判断是否是交替模式

下面的代码速度更快，这是因为符合题目要求的二进制数字的模式是已知的（即 01交替）。

因此可以生成所有的模式，从而这个数字是否在这些模式之中。

如果 n 不符合 b 中的任意一个模式，说明 n 不是 01 交替的。

class Solution(object):
    def hasAlternatingBits(self, n):
        """
        :type n: int
        :rtype: bool
        """
        b = 0b1010101010101010101010101010101010101010101010101010101010101010
        while b > 0:
            if b == n:
                return True
            b = b >> 1
        return False

方法三：位运算

又是骚操作。

第一步，使用 n ^ (n >> 1)。

如果是 01 交错的二进制数字，在经历了这个操作之后，得到的全部是 1的二进制数字。

举个例子 n = 5 是 01交错的二进制数字：

In [1]: n = 5

In [2]: bin(n)
Out[2]: '0b101'

In [3]: bin(n >> 1)
Out[3]: '0b10'

In [4]: bin(n ^ (n >> 1))
Out[4]: '0b111'

第二步，使用 not (n & n + 1) 判断上一步的结果是否是全部为 1。

举个 n = 5时，bin(n ^ (n >> 1)) = '0b111'例子：

In [1]: n = 5

In [2]: bin(n)
Out[2]: '0b111'

In [3]: bin(n + 1)
Out[3]: '0b1000'

In [4]: n & n + 1
Out[4]: 0

In [5]: not (n & n + 1)
Out[5]: True

代码如下：

class Solution(object):
    def hasAlternatingBits(self, n):
        """
        :type n: int
        :rtype: bool
        """
        n ^= (n >> 1)
        return not (n & n + 1)

总结

1. 熟练掌握位运算技巧，才不会迷茫哦！
2. 你学到了吗？留个言吧！

日期

2018 年 1 月 17 日 2018 年 11 月 ９ 日 —— 睡眠可以 2022 年 3 月 28 日 —— 早起时间利用很可以，公众号转载+题解一篇