我的C实践(7)：位计数

  位计数就是对一个数中具有某些特征的位进行计数。看下面实现：
/* bitscount.c：位计数 */
/* 计算x中1位的数目：方案1，采用分治策略 */
inline int pop(unsigned x){
/* 对每个2位字段，先析出其右端的1位，再析出其左端的1位，然后让这两个位相加 */
x=(x & 0x55555555)+((x>>1) & 0x55555555);
/* 对每个4位字段，先析出其右端2位字段，再析出其左端2位字段，然后让这两个2位字段相加 */
x=(x & 0x33333333)+((x>>2) & 0x33333333);
/* 对每个8位字段，先析出其右端4位字段，再析出其左端4位字段，然后让这两个4位字段相加 */
x=(x & 0x0f0f0f0f)+((x>>4) & 0x0f0f0f0f);
/* 对每个16位字段，先析出其右端8位字段，再析出其左端8位字段，然后让这两个8位字段相加 */
x=(x & 0x00ff00ff)+((x>>8) & 0x00ff00ff);
/* 最后让两个16位字段相加 */
x=(x & 0x0000ffff)+(x>>16);
return x;
}
/* 方案2：用公式sum_digits(z)=z-[z/2]-[z/4]-...-[z/2**(n-1)]，
并结合分治策略来计算 */
inline int pop_2(unsigned x){
unsigned n;
n=(x>>1) & 0x77777777; /* 对每个4位字段z，计算[z/2] */
x=x-n; /* 计算z-[z/2] */
n=(n>>1) & 0x77777777; /* 计算[z/4] */
x=x-n; /* 计算z-[z/2]-[z/4] */
x=(x+(x>>4)) & 0x0f0f0f0f; /* 对每相邻的两个4位字段相加，扩展成4个8位字段 */
x=x*0x01010101; /* 乘以0x01010101，即把这4个字节相加，
结果存放在最高阶的那个字节中 */
return x>>24;
}
/* 方案3：通过x&(x-1)不断地把最右侧的1位改成0位，并记录下这样的修改次数，直到x变成0 */
inline int pop_3(unsigned x){
int n=0;
while(x!=0){
++n;
x=x & (x-1);
}
return n;
}
/* 计算整个数组中的1位数目 */
int pop_array(unsigned A[], int n){
register int i,j,lim;
register unsigned s,s8,x;
s=0;
for(i=0;i<n;i=i+31){
lim=n <= i+31 ? n : i+31;
s8=0;
for(j=i;j<lim;++j){
x=A[j];
x=x-((x>>1) & 0x55555555); /* 变成16个2位字段 */
x=(x & 0x33333333)+((x>>2) & 0x33333333); /* 变成8个4位字段 */
x=(x+(x>>4)) &