欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

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

程序员文章站 2024-03-05 11:58:54
/** * 快速计算二进制数中1的个数(fast bit counting) * 该算法的思想如下: * 每次将该数与该数减一后的数值相与,从而将...
/** 
 * 快速计算二进制数中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;   
 } 
}