题目地址：https://leetcode.com/problems/binary-number-with-alternating-bits/description/open in new window
题目描述
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'
1 2
注意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))
1 2 3 4 5 6 7 8
直接判断相邻的数字是不同的：
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))
1 2 3 4 5 6 7 8
方法二：判断是否是交替模式
下面的代码速度更快，这是因为符合题目要求的二进制数字的模式是已知的（即 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
1 2 3 4 5 6 7 8 9 10 11 12
方法三：位运算
又是骚操作。
第一步，使用 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'
1 2 3 4 5 6 7 8 9 10
第二步，使用 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
1 2 3 4 5 6 7 8 9 10 11 12 13
代码如下：
class Solution(object):
def hasAlternatingBits(self, n):
"""
:type n: int
:rtype: bool
"""
n ^= (n >> 1)
return not (n & n + 1)
1 2 3 4 5 6 7 8
总结
1、 熟练掌握位运算技巧，才不会迷茫哦！；
2、 你学到了吗？留个言吧！；
DDKK.COM 弟弟快看-教程，程序员编程资料站，版权归原作者所有
本文经作者：负雪明烛 授权发布，任何组织或个人未经作者授权不得转发