Integer.highestOneBit(int i)方法的作用与底层…
2019-08-31 07:14:41来源:博客园 阅读 ()
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作者对于位运算的使用已经达到了出神入化的境界了。
如果想学习更多的精彩的Java、分布式、微服务等方面的知识,请关注微信公众号:1点25
原文链接:https://www.cnblogs.com/nicerblog/p/11431181.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
- System.out.println()和System.out.print()区别 2020-06-10
- 类的继承,方法重新中修饰符如何定义 2020-06-10
- java里面main方法中的String[]args 2020-06-07
- 错误: 在类中找不到 main 方法, 请将 main 方法定义为: & 2020-06-06
- 学习笔记之方法引用 2020-06-06
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash