前言
本文主要介绍如何把一个int型二进制数的最右侧的1提取出来，也就是只保留该int型数对应的二进制最右侧的1，其他的都变为0，并返回对应的10进制数字。
现有个数num=112256700，这个num对应的二进制为00000110101100001110011010111100，要求把这个数的二进制最右侧的1保留，其他的位置全部变为0，也就是变为00000000000000000000000000000100，变更后的二进制数对应的十进制为4。
思路分析
方法一
此方法为比较传统的方法，也就是先把num这个是转为二进制形式，放到一个数组中，然后遍历数组，找到最右侧的1，记录1的位置，然后转成10进制形式。
此方法理解起来简单、实现也简单，但是没有什么技术可言，也不够优雅，不推荐。
方法一代码实现
public class Code16_FindRightOne {
public static int getRightOne(int num) {
int[] arr = new int[32];
for (int i = 31; i >= 0; i--) {
arr[i] = (num & (1 << i)) == 0 ? 0 : 1;
}
int res = 0;
for (int i = 0; i < arr.length; i++) {
if (arr[i] == 1) {
res = i;
break;
}
}
return (int) (Math.pow(2, res));
}
public static void main(String[] args) {
int rightOne = getRightOne(112256700);
System.out.println(rightOne);
}
}
复制代码
image.gif
看下运行结果为4。
方法二
此方法，利用了二进制的特性，可以非常简单的实现这个功能，先看下解决思路。
要保留左右侧的1，把其他位置都变为0，首先想到的是位运算，再来看下位运算的几个特性：
与&：两边都为1结果才为1，否则为0。
或|：两边有一个为1结果就为1，都为0时才为0。
异或^：相同为0，不同为1。
我们的目的是，把最右侧1左边的数，全部变为0，按照位运算来看，相与操作最为可能，只要把1左边的数取反再与原来的数相与就可以了。
如果把num取反，左边的数是解决了，那右边的数呢？右边的数也取反了，怎么把他还原回来呢？
先看个例子，比如一个二进制为000101000100，这个二进制取反后为111010111011，现在就差怎么把011变为100了，这么一看就简单了，把011加上1不就好了？111010111011 + 1 = 111010111100。让这两个数再进行相与就能保留最右侧的1了。
也就是，把原来的数num和num取反加1进行相与即可。
还记得取反加1又可以怎么表示吗？对了，num取反加1又可以表示为负数即-num。
方法二代码实现
来看下代码吧。
public class Code17_FindRightOne {
public static void printBinary(int num) {
for (int i = 31; i >= 0; i--) {
System.out.print((num & (1 << i)) == 0 ? "0" : "1");
}
System.out.println();
}
public static void main(String[] args) {
printBinary(112256700);
printBinary(112256700 & -112256700);
System.out.println(112256700 & -112256700);
}
}
复制代码
image.gif
输出结果：
00000110101100001110011010111100
00000000000000000000000000000100
4
复制代码
image.gif
可以看到运行结果和方法一是一样的，说明方法二的代码功能实现也是正确的。
为了查看方便，我把原来的数以及两个数相与后的结果的二进制形式也打印了出来。从上面结果来看，是不是把最右侧的1保留下来了呢？
总结
从上面两个方案来看，方法二使用位运算比方法一简单的太多了，仅仅简单的一行代码就把功能给实现了，而且在效率方面也远比方法一高的多。
把一个数的二进制最右侧的1提取出来，在很多算法题目中会经常遇到，这里只是简单的介绍了下如何实现，后面会介绍更多使用此方法的案例。
当然实现方法有很多种，如果你有更好的办法，欢迎在评论区留言交流
网友评论