这是悦乐书的第292次更新，第310篇原创
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第160题（顺位题号是693）。给定正整数，检查它是否具有交替位：即它的二进制数的任意两个相邻位总是具有不同的值。例如：
输入：5
输出：true
说明：5的二进制表示是：101
输入：7
输出：false
说明：7的二进制表示为：111。
输入：11
输出：false
说明：11的二进制表示是：1011。
输入：10
输出：true
说明：10的二进制表示是：1010。
本次解题使用的开发工具是eclipse，jdk使用的版本是1.8，环境是win7 64位系统，使用Java语言编写和测试。
02 第一种解法
最直接解法，将正整数转为二进制字符串，借助包装类Integer的toBinaryString方法实现，然后对字符串的字符进行遍历，如果相邻的字符相等了，直接返回false。
public boolean hasAlternatingBits(int n) {
String str = Integer.toBinaryString(n);
for (int i=1; i<str.length(); i++) {
if (str.charAt(i) == str.charAt(i-1)) {
return false;
}
}
return true;
}
03 第二种解法
我们也可以观察下为true的那些数，从1开始：
1，其二进制数为：1
2，其二进制数为：10
5，其二进制数为：101
10，其二进制数为：1010
通过观察这些二进制数，我们可以发现，它们可以看做是10和1的组合体。对于10，可以有零个，也可以有多个，而对于1，只可能是0个或者1个，多了就重复了。因此，我们也可以使用正则表达式来解。
匹配多字符10，使用圆括号；匹配0次或者多次，使用星号，或者{0,}。
匹配1，可以直接写1，匹配0次或者1次，使用问号，或者{0,1}。
public boolean hasAlternatingBits(int n) {
String str = Integer.toBinaryString(n);
//(10){0,}1{0,1} 这样写也是可以的
return str.matches("(10)*1?");
}
04 第三种解法
我们也可以不将其转为二进制字符串，直接使用位运算来判断，借助与(&)运算。与运算的规则是对应位都为1才为1，否则对应位为0。每次将n和1进行与运算，看它最后一位是0还是1，使用一个临时变量，将其二进制数的最后一位记录下来，与当前的最后一位比较，如果相同了，就返回false。
public boolean hasAlternatingBits(int n) {
// 记录每次操作的最后一位
int prev = -1;
while (n > 0) {
if ((n&1) == 1) {
if (prev == 1) {
return false;
}
prev = 1;
} else {
if (prev == 0) {
return false;
}
prev = 0;
}
// 每次将其右移一位
n >>= 1;
}
return true;
}
05 第四种解法
对于第三种解法，我们还可以再简化下。上面我们每进行一次计算都会去判断一下，是否等于上一次计算的最后一位，这里我们将其移动到while循环的判断条件中去，反过来处理，先得到下一次正确的最后一位，看其符不符合。依旧使用一个临时变量，循环继续的条件变成了当前最后一位是否等于预先设定好的那个数，在循环内部，我们对temp变量进行变动，取每次计算的相反值，如果计算为0，那么temp就为1，表示下一次参与计算后的最后一位要为1，否则就去判断n是否已经等于0了。
public boolean hasAlternatingBits(int n) {
int temp = n&1;
while ((n&1) == temp) {
temp = 1-temp;
n >>= 1;
}
return n == 0;
}
06 第五种解法
此解法利用了n的二进制数0与1交替的特征，与自身右移一位后的数进行错位相加，变成了一个全部由1组成的二进制数，然后再利用检测是否全为1的方法，判断是否符合题意。而检测的方法就是，加1后和自身进行与运算，因为如果该二进制数全为1，加1后就转为了首位为1，其余位都是0的二进制数，再与原来的自己进行与运算，运算的结果就是0。比如5，5+5/2变成了7，二进制数为111，加1后，其二进制数变为了1000，两者进行与运算后，得到的结果是0。除以2和右移一位的效果等同。
public boolean hasAlternatingBits(int n) {
// ((n + (n >> 1) + 1) & (n + (n >> 1))) == 0 这样写也行
return ((n+n/2+1) & (n+n/2)) == 0;
}
07 小结
算法专题目前已日更超过四个月，算法题文章160+篇，公众号对话框回复【数据结构与算法】、【算法】、【数据结构】中的任一关键词，获取系列文章合集。
以上就是全部内容，如果大家有什么好的解法思路、建议或者其他问题，可以下方留言交流，点赞、留言、转发就是对我最大的回报和支持！
网友评论