给定一个正整数，检查他是否为交替位二进制数：换句话说，就是他的二进制数相邻的两个位数永不相等。
示例 1:
输入: 5
输出: True
解释:
5的二进制数是: 101
示例 2:
输入: 7
输出: False
解释:
7的二进制数是: 111
示例 3:
输入: 11
输出: False
解释:
11的二进制数是: 1011
示例 4:
输入: 10
输出: True
解释:
10的二进制数是: 1010
答案：
1public boolean hasAlternatingBits(int n) {
2 n ^= (n >> 1);
3 return (n & (n + 1)) == 0;
4}
解析：
这道题非常简单，一个数的二进制位如果是0和1交替，那么把这个数往右移一位然后再和原来的数进行异或运算，就会让他全部变为1（注意这里是忽略前面的0的，比如5在java语言中的二进制是32位，我们只考虑后面的101，不用考虑前面的29个0。）。我们来随便举个例子画个图看一下
所以他会把原来的位置上全部变为1，然后我们再加1，让他原来的位置全部变为0，然后在和原来的自己进行与运算，判断结果是否为0。
2，加法实现
上面的异或运算我们还可以改为加法运算，像下面这样
1public boolean hasAlternatingBits(int n) {
2 n += n >> 1;
3 return (n & (n + 1)) == 0;
4}
3，逐个判断
我们还可以使用最原始的方式，从右往左一个个判断0和1是否是交替出现的，代码也很简单，我们来看下
1public boolean hasAlternatingBits(int n) {
2 int pre = n & 1;
3 for (int i = 1; i < 32; i++) {
4 if ((1 << i) > n)
5 break;
6 int cur = (n >> i) & 1;
7 if ((cur ^ pre) == 0)
8 return false;
9 pre = cur;
10 }
11 return true;
12}
第7行如果等于0，说明要么连续出现了0，要么连续出现了1，直接返回false即可。当然第7行的判断我们还可以再改一下，换一种思路
1public boolean hasAlternatingBits(int n) {
2 int pre = n & 1;
3 n >>>= 1;
4 while (n != 0) {
5 if ((n & 1) == pre)
6 return false;
7 pre = n & 1;
8 n >>>= 1;
9 }
10 return true;
11}
第5行如果成立，说明要么连续出现了0，要么连续出现了1，和上面很类似，不过实现方式上有些差别。或者我们还可以不使用任何临时变量，像下面这样每两两前后比较
4，前后两两比较
1public boolean hasAlternatingBits(int n) {
2 while (n != 0 && (n >>> 1) != 0) {
3 if (((n & 1) ^ ((n >>> 1) & 1)) == 0)
4 return false;
5 n = n >>> 1;
6 }
7 return true;
8}
或者我们还可以把它给为递归的写法
5，递归实现
1public boolean hasAlternatingBits(int n) {
2 return n < 3 || ((n % 2) != (n / 2 % 2)) && hasAlternatingBits(n / 2);
3}6，移两位计算
再来想一下，前面我们把n往右移一位然后在与自己进行异或运算，我们能不能把n先往右移两位在进行异或运算呢，其实也是可以的，我们来画个图分析一下
我们只需要计算异或的结果类似于10000…这种形式的就可以了，所以代码很简单，直接一行搞定
1public static boolean hasAlternatingBits(int n) {
2 return ((n ^= n >> 2) & (n - 1)) == 0;
3}
我们来找几个数据测试一下
1 System.out.println("二进制0b111是不是0和1交替出现的：" + hasAlternatingBits(0b111));
2 System.out.println("二进制0b101是不是0和1交替出现的：" + hasAlternatingBits(0b101));
3 System.out.println("二进制0b1010101010是不是0和1交替出现的：" + hasAlternatingBits(0b1010101010));
4 System.out.println("二进制0b1010101011是不是0和1交替出现的：" + hasAlternatingBits(0b1010101011));
看一下打印的结果
1二进制0b111是不是0和1交替出现的：false
2二进制0b101是不是0和1交替出现的：true
3二进制0b1010101010是不是0和1交替出现的：true
4二进制0b1010101011是不是0和1交替出现的：false
结果完全正确
7，乘以3计算
我们接着往下思考，如果n是0和1交替出现的，那么会有两种情况，一种是以0结尾的，比如101010，一种是以1结尾的，比如1010101，无论哪种情况我们把它乘以3会有一个奇怪的现象，因为是0和1交替出现，0乘以3还是0，1乘以3是11(二进制)，所以不会出现一直往前进位的问题，我们来看下代码
1public static boolean hasAlternatingBits(int n) {
2 return ((n * 3) & (n * 3 + 1) & (n * 3 + 2)) == 0;
3}
我们还是来找几组数据来测试一下结果
1 System.out.println("二进制0b111是不是0和1交替出现的：" + hasAlternatingBits(0b111000));
2 System.out.println("二进制0b1010101010是不是0和1交替出现的：" + hasAlternatingBits(0b1010101010));
3 System.out.println("二进制0b10101010101是不是0和1交替出现的：" + hasAlternatingBits(0b10101010101));
4 System.out.println("二进制0b1010101011是不是0和1交替出现的：" + hasAlternatingBits(0b1010101011));
再来看一下打印结果
1二进制0b111是不是0和1交替出现的：false
2二进制0b1010101010是不是0和1交替出现的：true
3二进制0b10101010101是不是0和1交替出现的：true
4二进制0b1010101011是不是0和1交替出现的：false
结果完全在我们的预料之中。这种解法一般我们不太容易想到，但也不提倡使用，会有一些小的问题，因为如果n比较小的话是没问题的，如果n比较大的话，那么n*3就会出现数字溢出，导致结果错误。如果想写这种解法，最好先把n转为long类型就可以了。
8，使用java类库
如果允许的话我们还以使用java类库提供的方法先进行转换，然后再进行判断也是可以的，代码比较简单，我们来看下
1public boolean hasAlternatingBits(int n) {
2 String s = Integer.toBinaryString(n);
3 for (int i = 0; i < s.length() - 1; i++) {
4 if (s.charAt(i) == s.charAt(i + 1)) {
5 return false;
6 }
7 }
8 return true;
9}
这种就非常好理解了，但对于二进制位的考察相对就弱了很多，或者我们还可以更简洁一些
1public static boolean hasAlternatingBits(int n) {
2 String binary = Integer.toBinaryString(n);
3 return !binary.contains("00") && !binary.contains("11");
4}
9，总结
这道题难度不大，其实解法还是挺多的，主要考察的是对二进制位的熟练使用，如果上面的所有解题思路都能掌握，代码也都能看的懂，那么对二进制位的操作也算是比较熟练的了，但远达不到精通，因为关于二进制位运算的技巧还是非常非常多的，不是这一篇文字就能讲的清楚的，后续也会有一系列对二进制位运算的介绍。
联系客服
