題目
計(jì)算在一個 32 位的整數(shù)的二進(jìn)制表式中有多少個 1.
樣例
給定32(100000)匪凉，返回1
給定5(101)延届，返回2
給定1023(111111111)址貌，返回9
分析
方法一 普通法
最容易想到的方法脚翘，通過移位加計(jì)數(shù)骂因，一個個計(jì)算統(tǒng)計(jì)1的個數(shù)
public int countOnes1(int num){
int count = 0;
while(num!=0){
if(num%2==1)
count++;
num=num/2;
}
return count;
}
改進(jìn)的普通法
用位操作替代方法一
public int countOnes2(int num){
int count = 0;
while(num!=0){
count +=num&0x01;
num = num>>1;
}
return count;
}
方法三 快速法
這種方法速度比較快炎咖，其運(yùn)算次數(shù)與輸入n的大小無關(guān)，只與n中1的個數(shù)有關(guān)寒波。如果n的二進(jìn)制表示中有k個1乘盼，那么這個方法只需要循環(huán)k次即可。其原理是不斷清除n的二進(jìn)制表示中最右邊的1俄烁，同時累加計(jì)數(shù)器绸栅，直至n為0
為什么n &= (n – 1)能清除最右邊的1呢？因?yàn)閺亩M(jìn)制的角度講页屠，n相當(dāng)于在n - 1的最低位加上1粹胯。舉個例子蓖柔，8（1000）= 7（0111）+ 1（0001），所以8 & 7 = （1000）&（0111）= 0（0000）风纠，清除了8最右邊的1（其實(shí)就是最高位的1况鸣，因?yàn)?的二進(jìn)制中只有一個1）。再比如7（0111）= 6（0110）+ 1（0001）竹观，所以7 & 6 = （0111）&（0110）= 6（0110）镐捧，清除了7的二進(jìn)制表示中最右邊的1（也就是最低位的1）
public int countOnes3(int num){
int count = 0;
while(num!=0){
num = num & (num-1);
count++;
}
return count;
}
