Integer.highestOneBit(int i)方法的作用与底层实现-白红宇

Integer.highestOneBit(int i)方法的作用与底层实现

阅读量：3711 次

发布时间：2019-05-21

本文共 2013 字，大约阅读时间需要 6 分钟。

在Integer类中有这么一个方法，你可以给它传入一个数字，它将返回小于等于这个数字的一个2的幂次方数。这个方法就是highestOneBit(int i)。

比如下面的Demo，注意方法的输入与返回值：

System.out.println(Integer.highestOneBit(15));  // 输出8System.out.println(Integer.highestOneBit(16));  // 输出16System.out.println(Integer.highestOneBit(17));  // 输出16

这个方法的实现代码量也是非常少的：

public static int highestOneBit(int i) {
       // HD, Figure 3-1    i |= (i >>  1);    i |= (i >>  2);    i |= (i >>  4);    i |= (i >>  8);    i |= (i >> 16);    return i - (i >>> 1);}

接下来，我们就来详细分析一下这块代码的逻辑。

首先，对于这个方法的功能：给定一个数字，找到小于或等于这个数字的一个2的幂次方数。

如果我们要自己来实现的话，我们需要知道：怎么判断一个数字是2的幂次方数。

说真的，我一下想不到什么好方法来判断，唯一能想到的就是一个数字如果把它转换成二进制表示的话，它会有一个规律：如果一个数字是2的幂次方数，那么它对应的二进制表示仅有一个bit位上是1，其他bit位全为0。

比如：

十进制6，二进制表示为：0000 0110

十进制8，二进制表示为：0000 1000

十进制9，二进制表示为：0000 1001

所以，我们可以利用一个数字的二进制表示来判断这个数字是不是2的幂次方数。关键代码怎么实现呢？去遍历每个bit位？可以，但是不好，那怎么办？我们还是回头仔细看看Integer是如何实现的吧？

public static int highestOneBit(int i) {
       // HD, Figure 3-1    i |= (i >>  1);    i |= (i >>  2);    i |= (i >>  4);    i |= (i >>  8);    i |= (i >> 16);    return i - (i >>> 1);}

我们发现这段代码中没有任何的遍历，只有位运算与一个减法，也就是说它的实现思路和我们自己的实现思路完全不一样，它的思路就是：给定一个数字，通过一系列的运算，得到一个小于或等于该数字的一个2的幂次方数。

也就是：如果给定一个数字18，通过运算后，要得到16。

18用二进制表示为： 0001 0010

想要得到的结果(16)是：0001 0000

那么这个运算的过程无非就是将18对应的二进制数中除最高位的1之外的其他bit位都清零，则拿到了我们想要的结果。

那怎么通过位运算来实现这个过程呢？

我们拿18对应的二进制数0001 0010来举个例子就行了：

先将0001 0010右移1位，

得到0000 1001，再与自身进行或运算：

得到0001 1011。

再将0001 1011右移2位，

得到0000 0110，再与自身进行或运算：