/**
*快速计算二进制数中1的个数(FastBitCounting)
*该算法的思想如下:
*每次将该数与该数减一后的数值相与,从而将最右边的一位1消掉
*直到该数为0
*中间循环的次数即为其中1的个数
*例如给定"10100“,减一后为”10011",相与为"10000",这样就消掉最右边的1
*SparseOnesandDenseOneswerefirstdescribedbyPeterWegnerin
*“ATechniqueforCountingOnesinaBinaryComputer“,
*CommunicationsoftheACM,Volume3(1960)Number5,page322
*/
packageal;
publicclassCountOnes{
publicstaticvoidmain(String[]args){
inti=7;
CountOnescount=newCountOnes();
System.out.println("Thereare"+count.getCount(i)+"onesini");
}
/**
*@author
*@parami待测数字
*@return二进制表示中1的个数
*/
publicintgetCount(inti){
intn;
for(n=0;i>0;n++){
i&=(i-1);
}
returnn;
}
}