Integer中的奇妙位運(yùn)算
點(diǎn)擊上方藍(lán)色字體，選擇“標(biāo)星公眾號(hào)”
優(yōu)質(zhì)文章，第一時(shí)間送達(dá)
? 作者?|??南風(fēng)知我不易
來(lái)源 |? urlify.cn/zaIv22
66套java從入門到精通實(shí)戰(zhàn)課程分享
Integer中的奇妙位運(yùn)算
參考資料
https://segmentfault.com/a/1190000015763941
highestOneBit(int i)
函數(shù)的作用是獲得傳入?yún)?shù)的最高位的1，對(duì)于正數(shù)來(lái)說(shuō)返回值為小于i的最大二次冪，對(duì)于負(fù)數(shù)來(lái)說(shuō)永遠(yuǎn)是負(fù)數(shù)的最大值即-2^31
例如：7=0000 0111（省略前24位0）那么函數(shù)的返回值為 0000 0100=4
暴力法
通常來(lái)說(shuō)最直觀的做法就是暴力法，我一個(gè)一個(gè)數(shù)不就好了
//一位一位取就是了
public?int?heigestOneBit(int?i){
????int?res=1;
????if?(i<0)return?Integer.MIN_VALUE;
????while(i!=0){
????????if?(i!=1){
????????????res*=2;
????????}
????????i/=2;
????}
????return?res;
}
位運(yùn)算
看看JDK如何利用更加高效的位操作實(shí)現(xiàn)這一個(gè)函數(shù)
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);
}
為什么JDK一通位操作就把最高位取出來(lái)了呢？非常的巧妙啊，舉例說(shuō)明，看以下就知道了
//以下以數(shù)字為例，其中x表示0或者1不影響結(jié)果，1-最高位的1
i???????????????0000?001x?xxxx?xxxx?xxxx?xxxx?xxxx?xxxx
i>>1??0000?0001?xxxx?xxxx?xxxx?xxxx?xxxx?xxxx
i|=(i>>1)?0000?0011?xxxx?xxxx?xxxx?xxxx?xxxx?xxxx
i??0000?0011?xxxx?xxxx?xxxx?xxxx?xxxx?xxxx
i>>2??0000?0000?11xx?xxxx?xxxx?xxxx?xxxx?xxxx
i|=(i>>2)?0000?0011?11xx?xxxx?xxxx?xxxx?xxxx?xxxx
i??0000?0011?11xx?xxxx?xxxx?xxxx?xxxx?xxxx
i>>4??0000?0000?0011?11xx?xxxx?xxxx?xxxx?xxxx
i|=(i>>4)?0000?0011?1111?11xx?xxxx?xxxx?xxxx?xxxx
i??0000?0011?1111?11xx?xxxx?xxxx?xxxx?xxxx
i>>8??0000?0000?0000?0011?1111?11xx?xxxx?xxxx
i|=(i>>8)?0000?0011?1111?1111?1111?11xx?xxxx?xxxx
i??0000?0011?1111?1111?1111?11xx?xxxx?xxxx
i>>16??0000?0000?0000?0000?0000?0011?1111?1111
i|=(i>>16)?0000?0011?1111?1111?1111?1111?1111?1111
i??0000?0011?1111?1111?1111?1111?1111?1111
i>>>1??0000?0001?1111?1111?1111?1111?1111?1111
i-(i>>>1)?0000?0010?0000?0000?0000?0000?0000?0000
看完上面的簡(jiǎn)單分析應(yīng)該就知道JDK如何實(shí)現(xiàn)的了，簡(jiǎn)單來(lái)說(shuō)就是把第一個(gè)1不斷往后移動(dòng)，使得從第一個(gè)1之后的所有比特位都為1，此時(shí)減去右移一位的值，也就是減去后面所有的1代表的值，此時(shí)自然只剩下第一個(gè)1了，可以說(shuō)非常的巧妙了
bitCount(int i)
該方法的作用是統(tǒng)計(jì)一個(gè)整數(shù)的二進(jìn)制表示形式中1的個(gè)數(shù)，沒(méi)記錯(cuò)的話這其實(shí)也是leetcode中的一道題
首先還是我們自己來(lái)思考一下如何實(shí)現(xiàn)：
暴力法
一個(gè)bit一個(gè)bit計(jì)數(shù)
public?static?int?bitCount(int?i){
????//暴力法
????int?count=0;
????while(i!=0){
????????if?((i&1)==1){
????????????count++;
????????}
????????i=i>>>1;
????}
????return?count;
}
位運(yùn)算優(yōu)化一下
試想對(duì)于二進(jìn)制 100，1的個(gè)數(shù)為1，按照暴力法需要3次才能統(tǒng)計(jì)出來(lái)，怎么樣一次統(tǒng)計(jì)出來(lái)呢，也就是怎么一次就把100變成0呢？
對(duì)于1xxx這樣的數(shù)字，x代表0，以100為例，100-1=011，而100&011恰好為0，能做多少次這樣的運(yùn)算，它就有多少位1，代碼如下
public?static?int?bitCount(int?i){
????//位運(yùn)算優(yōu)化
????int?count=0;
????while(i!=0){
????????i=i&(i-1);
????????count++;
????}
????return?count;
}
到這里，有多少位的1，就統(tǒng)計(jì)多少次，貌似看起來(lái)已經(jīng)還算不錯(cuò)了
JDK的位運(yùn)算
public?static?int?bitCount(int?i)?{
????//?HD,?Figure?5-2
????i?=?i?-?((i?>>>?1)?&?0x55555555);
????i?=?(i?&?0x33333333)?+?((i?>>>?2)?&?0x33333333);
????i?=?(i?+?(i?>>>?4))?&?0x0f0f0f0f;
????i?=?i?+?(i?>>>?8);
????i?=?i?+?(i?>>>?16);
????return?i?&?0x3f;
}
Superise Mother Fxxk！這是在干什么？首先解釋一下總體的思想
//要統(tǒng)計(jì)如下二進(jìn)制的：1001 1010 1010 1010?的1的位數(shù)
//JDK是這樣做的
先每?jī)蓚€(gè)bit統(tǒng)計(jì)有多少個(gè)1，然后就保存在二進(jìn)制的本地
10?01?10?10?10?10?10?10
01?01?01?01?01?01?01?01
然后再統(tǒng)計(jì)連續(xù)四個(gè)bit有多少個(gè)1，然后保存在本地
0010?0010?0010?0010
再統(tǒng)計(jì)8個(gè)bit有多少個(gè)1，保存在本地
0000?0100?0000?0100
然后再統(tǒng)計(jì)每16個(gè)比特有多少個(gè)1，保存再本地
0000?0000?0000?1000?==8總共8個(gè)1有了整體的算法思想，來(lái)看看這幾個(gè)奇怪的數(shù)字0x55555555、0x33333333、0x0f0f0f0f
他們對(duì)應(yīng)的二進(jìn)制如下：
0x55555555???01010101010101010101010101010101
0x33333333???00110011001100110011001100110011
0x0f0f0f0f???00001111000011110000111100001111
針對(duì)0x55555555來(lái)看看效果，怎么把兩個(gè)相鄰bit位中的1存儲(chǔ)下來(lái)，
//以12345為例
12345????0000?0000?0000?0000?0011?0000?0011?1001
0x55555555???0101?0101?0101?0101?0101?0101?0101?0101
12345&
0x55555555???0000?0000?0000?0000?0001?0000?0001?0001
//可以看到相當(dāng)于把兩個(gè)相鄰的比特位的后一位的1全部取出來(lái)了
12345>>>1???0000?0000?0000?0000?0001?1000?0001?1100
0x55555555???0101?0101?0101?0101?0101?0101?0101?0101
12345>>>1
&0x55555555???0000?0000?0000?0000?0001?0000?0001?0100
//可以看到相當(dāng)于把兩個(gè)相鄰的比特位的前一位的1全部取出來(lái)了
12345????00?00?00?00?00?00?00?00?00?11?00?00?00?11?10?01
last?1????00?00?00?00?00?00?00?00?00?01?00?00?00?01?00?01
first?1????00?00?00?00?00?00?00?00?00?01?00?00?00?01?01?00
last1+fisrt1??00?00?00?00?00?00?00?00?00?10?00?00?00?10?01?01
//可以看到兩位中的1的數(shù)量已經(jīng)用兩個(gè)bit來(lái)保存了
算法實(shí)現(xiàn)如下：
public?static?int?bitCount(int?i)?{
????i?=?(i?&?0x55555555)?+?((i?>>>?1)?&?0x55555555);
????i?=?(i?&?0x33333333)?+?((i?>>>?2)?&?0x33333333);
????i?=?(i?&?0x0f0f0f0f)?+?((i?>>>?4)?&?0x0f0f0f0f);
????i?=?(i?&?0x00ff00ff)?+?((i?>>>?8)?&?0x00ff00ff);
????i?=?(i?&?0x0000ffff)?+?((i?>>>?16)?&?0x0000ffff);
????return?i;
}
JDK再做點(diǎn)優(yōu)化即可
第一步，對(duì)于 11 這兩個(gè)比特位來(lái)說(shuō)，用 01 + 01 的方式可以得到 10 也可以用 11 - 01 的方式，所以可以少做一次位運(yùn)算
第三步，統(tǒng)計(jì)兩個(gè) 4個(gè)連續(xù)bit 中1的個(gè)數(shù)，例如 0011 0011 -> 0000 1100 ，而8個(gè)bit最多就8個(gè)1，用4個(gè)bit就可以表示了，所以可以先加，0011 1100，再消除，0000 1100，第四步第五步同理，前面的留著不管，最后返回的時(shí)候把前面的bit置0
return i & 0x3f，32位的int，最多就32個(gè)1，所以取后六位即可表示所有的可能
上述兩者的使用
上面兩個(gè)方法均在HashMap（JDK7實(shí)現(xiàn)）中的roundroundUpToPowerOf2方法中被調(diào)用，HashMap的分析詳見(jiàn)https://www.cnblogs.com/danzZ/p/14075147.html，還是非常有意思的
粉絲福利：實(shí)戰(zhàn)springboot+CAS單點(diǎn)登錄系統(tǒng)視頻教程免費(fèi)領(lǐng)取
???
?長(zhǎng)按上方微信二維碼?2 秒 即可獲取資料
感謝點(diǎn)贊支持下哈?