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

本是古典何须时尚 2024-03-30 13:10 77阅读 0赞

### 前言 ###

本文主要介绍如何把一个`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提取出来，在很多算法题目中会经常遇到，这里只是简单的介绍了下如何实现，后面会介绍更多使用此方法的案例。

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