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

时间:2021-05-20

/** * 快速计算二进制数中1的个数(Fast Bit Counting) * 该算法的思想如下: * 每次将该数与该数减一后的数值相与,从而将最右边的一位1消掉 * 直到该数为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("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; } }

声明:本页内容来源网络,仅供用户参考;我单位不保证亦不表示资料全面及准确无误,也不保证亦不表示这些资料为最新信息,如因任何原因,本网内容或者用户因倚赖本网内容造成任何损失或损害,我单位将不会负任何法律责任。如涉及版权问题,请提交至online#300.cn邮箱联系删除。

相关文章