計(jì)算一個(gè)二進(jìn)制數(shù)中的1的個(gè)數(shù)
1.循環(huán)法
首先二進(jìn)制數(shù)有這么一個(gè)性質(zhì)钳吟，當(dāng)一個(gè)數(shù)減去1再與原來(lái)的數(shù)字去&運(yùn)算敷钾，得到的結(jié)果其實(shí)是將原來(lái)的那個(gè)數(shù)字的最右邊的那個(gè)1變成0后的數(shù)字。
舉個(gè)粒子：
10101010
10101010 - 1 = 10101001
10101010 & 10101001 =
10101000
所以執(zhí)行一次這樣的運(yùn)算就把二進(jìn)制數(shù)的一個(gè)1給消滅了。澈圈。它掂。
運(yùn)用這樣的性質(zhì)還可以去解決其他的移位問(wèn)題
來(lái)上代碼：
public static int bitNums0(int i){
int count = 0;
while(i != 0){
i = (i - 1) & i;
count++;
}
return count;
2. 不使用循環(huán)的方法
01010111
- 先把一個(gè)二進(jìn)制數(shù)分為兩個(gè)兩個(gè)一組巴帮，01,01,01,11,
組內(nèi)的高位和低位相加溯泣，
然后再四個(gè)分為一組，組內(nèi)高二位與第二位相加
...以此榕茧，最后的那個(gè)就是結(jié)果垃沦。
public static int bitNums(int i){
int bit2 = 0x55_55_55_55;//0101 0101 0101...
int bit4 = 0x33_33_33_33;//0011 0011 0011...
int bit8 = 0x0f_0f_0f_0f; //0000 1111 0000 1111...
int bit16 = 0x00_ff_00_ff; //0000 0000 1111 1111...
int bit32 = 0x00_00_ff_ff; //0000 0000 0000 0000...1111 ...
i = ((i >>> 1) & bit2) + (i & bit2);
i = ((i >>> 2) & bit4) + (i & bit4);
i = ((i >>> 4) & bit8) + (i & bit8);
i = ((i >>> 8) & bit16) + (i & bit16);
i = ((i >>> 16) & bit32) + (i & bit32);
return i;
}
