算法 | 如何把一个int型二进制数的最右侧的1提取出来？

前言

本文主要介绍如何把一个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);
    }
}

看下运行结果为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);
    }
}

输出结果：

00000110101100001110011010111100
00000000000000000000000000000100
4

可以看到运行结果和方法一是一样的，说明方法二的代码功能实现也是正确的。

为了查看方便，我把原来的数以及两个数相与后的结果的二进制形式也打印了出来。从上面结果来看，是不是把最右侧的1保留下来了呢？

总结

从上面两个方案来看，方法二使用位运算比方法一简单的太多了，仅仅简单的一行代码就把功能给实现了，而且在效率方面也远比方法一高的多。

把一个数的二进制最右侧的1提取出来，在很多算法题目中会经常遇到，这里只是简单的介绍了下如何实现，后面会介绍更多使用此方法的案例。

当然实现方法有很多种，如果你有更好的办法，欢迎在评论区留言交流。