給定一個(gè)十進(jìn)制，統(tǒng)計(jì)其二進(jìn)制表示中1的個(gè)數(shù)。
- 解法一：
public int NumberOf1(int n) {
int flag = 1, count = 0;
while(flag != 0) {
if((n & flag) != 0) {
count ++;
}
flag = flag << 1;
}
return count;
}
使用一個(gè)輔助變量，初始值是1，也就是2的0次方，不斷左移，并且與n進(jìn)行與操作，這樣就可以判斷n從右往左各bit位上是否為1。進(jìn)而得到問(wèn)題的解。
- 解法二：
public int NumberOf1(int n) {
int count = 0;
while(n != 0) {
count ++;
n = n & (n - 1);
}
return count;
}
這種解法應(yīng)用了一種巧妙的思路:n與n-1進(jìn)行與操作，會(huì)消除n二進(jìn)制中最右邊的一位1。我們可以簡(jiǎn)單的思考一下，假如n的二進(jìn)制中最后一位是1，那么減去1之后，最后一位變成了0，其他位不變，滿足上面的結(jié)論；如果最后一位是0，那么減去1后，就相當(dāng)于從右往左數(shù)，第一位非0也就是1的位置開始，所有位按位取反，此時(shí)再與n做與操作，也是正好把從右往左的第一位1消除掉。結(jié)論得到證明。
- 解法三：
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;
}
第三種解法就是jdk里面給出的大神級(jí)實(shí)現(xiàn)了(Integer類里的靜態(tài)方法)。開始以為應(yīng)該會(huì)用解法二的解法就ok了。但是這里給出了一種看似更為"復(fù)雜"的方法。讓我們來(lái)看一下。
這種方式總體的思路有點(diǎn)類似于分治-合并的思路。兩兩一組統(tǒng)計(jì)組內(nèi)1的個(gè)數(shù)(分治)，然后量量一組合并求和，直到全部求和完畢，得到整個(gè)二進(jìn)制串中1的個(gè)數(shù)。讓我們來(lái)逐行看一下源碼。我們用666這個(gè)十進(jìn)制作為例子，debug一下這個(gè)方法的每一行。666對(duì)應(yīng)的二進(jìn)制為:
0000 0000 0000 0000 0000 0010 1001 1010
第一行:這一行應(yīng)該是這個(gè)方法中最關(guān)鍵也是最難以理解的一行，兩兩一組，求組內(nèi)1的個(gè)數(shù)。直接看的話，這個(gè)減操作還是很迷的。我們先來(lái)看一下每?jī)晌灰唤M，原值與二進(jìn)制中1的個(gè)數(shù)的真值表。（這個(gè)地方的思路，是百度了下jdk這個(gè)源碼的講解，看了某位大神的博客后，回來(lái)自己debug的。知識(shí)產(chǎn)權(quán)值得保護(hù)，下次再看到這的時(shí)候，補(bǔ)充下想法的來(lái)源。）
| 原值 | 1的個(gè)數(shù)(二進(jìn)制) | 操作過(guò)程 |
|---|---|---|
| 00 | 00 | 00 - 00 = 00 |
| 01 | 01 | 01 - 00 = 01 |
| 10 | 01 | 10 - 01 = 01 |
| 11 | 10 | 11 - 01 = 10 |
由于是每?jī)晌灰唤M，因此真值表中原值只有4個(gè)值。對(duì)應(yīng)的1的個(gè)數(shù)在第二列。下面就是見證奇跡的時(shí)刻了。我們發(fā)現(xiàn)，第二列的值，是第一列的值作為被減數(shù)，第一列右移一位的值作為減數(shù)求差的結(jié)果，也就是 i - i>>>1。有了這個(gè)公式，再來(lái)看第一行的操作，就比較好理解了。0x55555555對(duì)應(yīng)的二進(jìn)制為 0101 0101 0101 0101。i右移一位，再與一下0x55555555的話，就相當(dāng)于是右移之后，再把組內(nèi)的 第一個(gè)數(shù)字給消除掉，即構(gòu)造我們上面公式的減數(shù)。舉個(gè)例子，如果原數(shù)是1111，右移一位的話是0111，分成兩組為(01)(11)，與一下0x55555555，得到我們期望的減數(shù)(01)(01)。至此，減數(shù)被減數(shù)都有了，第一行執(zhí)行完畢，得到的二進(jìn)制串就是每?jī)晌恢?的個(gè)數(shù)。ps:這一步一共分成了16組(32/2)。
step1:右移一位
0000 0000 0000 0000 0000 0001 0100 1101
step2:與一下0x55555555
0000 0000 0000 0000 0000 0001 0100 0101
step3:用被減數(shù)(666)減一下上面的結(jié)果
0000 0000 0000 0000 0000 0001 0101 0101
第二行:從這一行開始，就是求和了。第二行是相鄰兩組合并。如果我們給分組編號(hào)，1-16組，那么+號(hào)前面的是保留組號(hào)2、4、6、8...16的分組。+號(hào)后面的操作是將1、3、5、7...15的分組，首先移動(dòng)到2、4、6、8...16組的位置上，然后將其他位置清0，這樣就跟+號(hào)左邊的對(duì)齊了，然后做加法。
step1: 保留2、4、6...
0000 0000 0000 0000 0000 0001 0001 0001
step2:右移兩位,保留2、4、6、8..
0000 0000 0000 0000 0000 0000 0001 0001
step3:求和
0000 0000 0000 0000 0000 0001 0010 0010
第三行:每四個(gè)一組求和。
step1: i + i>>>4
0000 0000 0000 0000 0000 0001 0011 0100
step2: &0x0f0f0f0f
0000 0000 0000 0000 0000 0001 0000 0100
第四行:每8個(gè)一組求和。
0000 0000 0000 0000 0000 0000 0000 0101
第五行:每16個(gè)一組求和
0000 0000 0000 0000 0000 0000 0000 0101
第六行: 獲取最后結(jié)果。因?yàn)閕nt是4字節(jié)，32bit，最多也就32個(gè)1，所以最終結(jié)果最大值為32(2^5),即為 0010 0000，所以取6位即可，0x3f就是這么來(lái)的。
00 0101（二進(jìn)制） = 5（十進(jìn)制）
- 總結(jié)
該方法總共5次無(wú)符號(hào)位移操作，5次與操作，4次加法操作，一次減法操作，總共15次計(jì)算。解法二的話，最壞場(chǎng)景的操作數(shù)是: 32*(1次加法+ 一次減法 + 一次與操作) = 96次操作。雖說(shuō)都是常數(shù)級(jí)的操作，但是應(yīng)該jdk的實(shí)現(xiàn)復(fù)雜效率更高一些。后面考慮怎么證明一下該方法的效率比方法二高。
