Java数据结构及算法实例：快速计算二进制数中1的个数(Fast Bit Counting)

Java数据结构及算法实例：快速计算二进制数中1的个数(Fast Bit Counting)

/**

* 快速计算二进制数中1的个数(Fast Bit Counting)

* 该算法的思http://想如下：

* 每次将该数与该数减一后的数值相与，从而将最右边的一位1消掉 RdbqRxyy

* 直到该数为0

* 中间循环的次数即为其中1的个数

* 例如给定"10100“，减一后为”10011",相与为"10000",这样就消掉最右边的1

* Sparse Ones and Dense Ones were first described by Peter Wegner in

* “A Technique for Counting Ones in a Binary Computer“,

* Communications of the ACM, Volume 3 (1960) Number 5, page 322

*/

package al;

public class CountOnes {

public static void main(String[] args) {

int i = 7;

CountOnes count = new CountOnes();

System.out.println("http://There are " + count.getCount(i) + " ones in i");

}

/**

* @author

* @param i 待测数字

* @return 二进制表示中1的个数

*/

public int getCount(int i) {

int n;

for(n=0; i > 0; n++) {

i &= (i - 1);

}

return n;

}

}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。