大家好，我是 @负雪明烛。👈👈 点击关注，优质题解不间断。

题目大意

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

解题方法

我用了 3 种不同的方法。

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

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

方法一：遍历判断

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

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

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

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

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

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

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

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

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

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

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

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

  1. class Solution(object):
  2.     def hasAlternatingBits(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: bool
  6.         """
  7.         b = 0b1010101010101010101010101010101010101010101010101010101010101010
  8.         while b > 0:
  9.             if b == n:
  10.                 return True
  11.             b = b >> 1
  12.         return False

方法三：位运算

又是骚操作。

第一步，使用 n ^ (n >> 1)，如果是 01 交错的二进制数字，在经历了这个操作之后，得到的全部是 1的二进制数字。

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

  1. In [1]: n = 5
  3. In [2]: bin(n)
  4. Out[2]: '0b101'
  6. In [3]: bin(n >> 1)
  7. Out[3]: '0b10'
  9. In [4]: bin(n ^ (n >> 1))
  10. Out[4]: '0b111'

第二步，使用与运算判断 n ^ (n - 1) 的结果，是否是全部为 1。

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

  1. In [1]: n = 5
  3. In [2]: bin(n)
  4. Out[2]: '0b111'
  6. In [3]: bin(n + 1)
  7. Out[3]: '0b1000'
  9. In [4]: n & n + 1
  10. Out[4]: 0
  12. In [5]: not (n & n + 1)
  13. Out[5]: True

代码如下：

  1. class Solution(object):
  2.     def hasAlternatingBits(self, n):
  3.         """
  4.         :type n: int
  5.         :rtype: bool
  6.         """
  7.         n ^= (n >> 1)
  8.         return not (n & n + 1)

总结

  1. 熟练掌握位运算技巧，才不会迷茫哦！

我是 @负雪明烛 ，刷算法题 1000 多道，写了 1000 多篇算法题解，收获阅读量 300 万。
关注我，你将不会错过我的精彩动画题解、面试题分享、组队刷题活动，进入主页 @负雪明烛 右侧有刷题组织，从此刷题不再孤单。