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

這篇文章將為大家詳細(xì)講解有關(guān)Integer.highestOneBit(int i)方法的作用是什么，文章內(nèi)容質(zhì)量較高，因此小編分享給大家做個(gè)參考，希望大家閱讀完這篇文章后對(duì)相關(guān)知識(shí)有一定的了解。

在Integer類中有這么一個(gè)方法，你可以給它傳入一個(gè)數(shù)字，它將返回小于等于這個(gè)數(shù)字的一個(gè)2的冪次方數(shù)。這個(gè)方法就是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

這個(gè)方法的實(shí)現(xiàn)代碼量也是非常少的：

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);
}

接下來(lái)，我們就來(lái)詳細(xì)分析一下這塊代碼的邏輯。

首先，對(duì)于這個(gè)方法的功能：給定一個(gè)數(shù)字，找到小于或等于這個(gè)數(shù)字的一個(gè)2的冪次方數(shù)。

如果我們要自己來(lái)實(shí)現(xiàn)的話，我們需要知道：怎么判斷一個(gè)數(shù)字是2的冪次方數(shù)。

說(shuō)真的，我一下想不到什么好方法來(lái)判斷，唯一能想到的就是一個(gè)數(shù)字如果把它轉(zhuǎn)換成二進(jìn)制表示的話，它會(huì)有一個(gè)規(guī)律：如果一個(gè)數(shù)字是2的冪次方數(shù)，那么它對(duì)應(yīng)的二進(jìn)制表示僅有一個(gè)bit位上是1，其他bit位全為0。 比如： 十進(jìn)制6，二進(jìn)制表示為：0000 0110 十進(jìn)制8，二進(jìn)制表示為：0000 1000 十進(jìn)制9，二進(jìn)制表示為：0000 1001 所以，我們可以利用一個(gè)數(shù)字的二進(jìn)制表示來(lái)判斷這個(gè)數(shù)字是不是2的冪次方數(shù)。關(guān)鍵代碼怎么實(shí)現(xiàn)呢？去遍歷每個(gè)bit位？可以，但是不好，那怎么辦？我們還是回頭仔細(xì)看看Integer是如何實(shí)現(xiàn)的吧？

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);
}

我們發(fā)現(xiàn)這段代碼中沒(méi)有任何的遍歷，只有位運(yùn)算與一個(gè)減法，也就是說(shuō)它的實(shí)現(xiàn)思路和我們自己的實(shí)現(xiàn)思路完全不一樣，它的思路就是：給定一個(gè)數(shù)字，通過(guò)一系列的運(yùn)算，得到一個(gè)小于或等于該數(shù)字的一個(gè)2的冪次方數(shù)。

也就是：如果給定一個(gè)數(shù)字18，通過(guò)運(yùn)算后，要得到16。

18用二進(jìn)制表示為： 0001 0010

想要得到的結(jié)果(16)是：0001 0000

那么這個(gè)運(yùn)算的過(guò)程無(wú)非就是將18對(duì)應(yīng)的二進(jìn)制數(shù)中除最高位的1之外的其他bit位都清零，則拿到了我們想要的結(jié)果。

那怎么通過(guò)位運(yùn)算來(lái)實(shí)現(xiàn)這個(gè)過(guò)程呢？

我們拿18對(duì)應(yīng)的二進(jìn)制數(shù)0001 0010來(lái)舉個(gè)例子就行了： 先將0001 0010右移1位， 得到0000 1001，再與自身進(jìn)行或運(yùn)算： 得到0001 1011。

再將0001 1011右移2位， 得到0000 0110，再與自身進(jìn)行或運(yùn)算： 得到0001 1111。

再將0001 1111右移4位， 得到0000 0001，再與自身進(jìn)行或運(yùn)算： 得到0001 1111。

再將0001 1111右移8位， 得到0000 0000，再與自身進(jìn)行或運(yùn)算： 得到0001 1111。

再將0001 1111右移16位， 得到0000 0000，再與自身進(jìn)行或運(yùn)算： 得到0001 1111。

再將0001 1111無(wú)符號(hào)右移1位， 得到0000 1111。

關(guān)于無(wú)符號(hào)右移，可以看我之前寫(xiě)的文章。

最后用0001 1111 - 0000 1111 = 0001 0000 震驚！得到了我們想要的結(jié)果。

其實(shí)這個(gè)過(guò)程可以抽象成這樣： 現(xiàn)在有一個(gè)二進(jìn)制數(shù)據(jù)，0001****，我們不關(guān)心低位的取值情況，我們對(duì)其進(jìn)行右移并且進(jìn)行或運(yùn)算。

先將0001****右移1位， 得到00001***，再與自身進(jìn)行或運(yùn)算： 得到00011***。

再將00011***右移2位， 得到0000011*，再與自身進(jìn)行或運(yùn)算： 得到0001111*。

再將0001111*右移4位， 得到00000001，再與自身進(jìn)行或運(yùn)算： 得到00011111。

后面不用再推算了，到這里我們其實(shí)可以發(fā)現(xiàn)一個(gè)規(guī)律： 右移與或運(yùn)算的目的就是想讓某個(gè)數(shù)字的低位都變?yōu)?，再用該結(jié)果 減去 該結(jié)果右移一位后的結(jié)果，則相當(dāng)于清零了原數(shù)字的低位。即得到了我們想要的結(jié)果。

到此，只能感嘆JDK作者對(duì)于位運(yùn)算的使用已經(jīng)達(dá)到了出神入化的境界了。

關(guān)于Integer.highestOneBit(int i)方法的作用是什么就分享到這里了，希望以上內(nèi)容可以對(duì)大家有一定的幫助，可以學(xué)到更多知識(shí)。如果覺(jué)得文章不錯(cuò)，可以把它分享出去讓更多的人看到。