Integer.highestOneBit(int i)方法的作用是什么

发布时间:2021-06-25 14:14:28 作者:Leah
来源:亿速云 阅读:153

这篇文章将为大家详细讲解有关Integer.highestOneBit(int i)方法的作用是什么,文章内容质量较高,因此小编分享给大家做个参考,希望大家阅读完这篇文章后对相关知识有一定的了解。

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

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

System.out.println(Integer.highestOneBit(15));  // 输出8
System.out.println(Integer.highestOneBit(16));  // 输出16
System.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,再与自身进行或运算: 得到0001 1111

再将0001 1111右移4位, 得到0000 0001,再与自身进行或运算: 得到0001 1111

再将0001 1111右移8位, 得到0000 0000,再与自身进行或运算: 得到0001 1111

再将0001 1111右移16位, 得到0000 0000,再与自身进行或运算: 得到0001 1111

再将0001 1111无符号右移1位, 得到0000 1111

关于无符号右移,可以看我之前写的文章。

最后用0001 1111 - 0000 1111 = 0001 0000 震惊!得到了我们想要的结果。

其实这个过程可以抽象成这样: 现在有一个二进制数据,0001****,我们不关心低位的取值情况,我们对其进行右移并且进行或运算。

先将0001****右移1位, 得到00001***,再与自身进行或运算: 得到00011***

再将00011***右移2位, 得到0000011*,再与自身进行或运算: 得到0001111*

再将0001111*右移4位, 得到00000001,再与自身进行或运算: 得到00011111

后面不用再推算了,到这里我们其实可以发现一个规律: 右移与或运算的目的就是想让某个数字的低位都变为1,再用该结果 减去 该结果右移一位后的结果,则相当于清零了原数字的低位。即得到了我们想要的结果。

到此,只能感叹JDK作者对于位运算的使用已经达到了出神入化的境界了。

关于Integer.highestOneBit(int i)方法的作用是什么就分享到这里了,希望以上内容可以对大家有一定的帮助,可以学到更多知识。如果觉得文章不错,可以把它分享出去让更多的人看到。

推荐阅读:
  1. 由自动装箱和拆箱引发我看Integer源码
  2. JDK:Integer.getChars(int i, int index, char[] buf

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

上一篇:php中如何实现扫雷游戏

下一篇:React ref的原理和应用

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》