快速计算二进制数中1的个数

int count1inBin(int binary){
	int count = 0;
	while(binary>0){
		binary &= (binary-1);
		++count;
	}
	return count;
}

核心在于binary &= (binary-1);

假设binary=X₁ X₂ …… X_n-1 X_n，其中 X_i(1≤i≤n)为1或0

不妨设Xi是最右边的1，那么binary就可以写成如下的形式

• binary=X₁ X₂……X_i-1 X_i 0……0，其中(1≤i≤n)，X_i 后面有n-i个0

• 因为 X_i =1，所以binary=X₁ X₂ …… X_i-1 1 0……0，其中(1≤i≤n)，1后面有n-i个0

• 则binary-1=X₁ X₂ ……X_i-1 0 1……1，其中(1≤i≤n)，0后面有n-i个1

• 则binary & (binary-1)= X₁ X₁ …… X_i-1 0 0 ……0，其中(1≤i≤n)，Xi - 1后面有 n-i+1个0

因此，binary & (binarye-1)的效果把最右边的1变成0

在上面的代码中，每把最右边的1变成0，则统计数加1，直到所有的1变成0为止。

算法循环的次数和binary中的1的个数有关，循环的次数就是1的个数

相较于移位的操作，减少了对数位上为0的数位的处理操作。