1

填空题 1 /69

 int func(unsigned int i) {
unsigned int temp = i;
 temp = (temp & 0x55555555) + ((temp & 0xaaaaaaaa) >> 1);
 temp = (temp & 0x33333333) + ((temp & 0xcccccccc) >> 2);
 temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0) >> 4);
 temp = (temp & 0x00ff00ff) + ((temp & 0xff00ff00) >> 8);
 temp = (temp & 0x0000ffff) + ((temp & 0xffff0000) >> 16); 
 return temp;
 }
请问 func(0x11530828)的返回值是:1

参考答案

首先确定这个题是想考察数的二进制表示中1的个数的“平行算法”,然后对代码两处笔误出进行改正如下:
1、 temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0 >> 4)); 
改为: temp = (temp & 0x0f0f0f0f) + ((temp & 0xf0f0f0f0) >> 4); 
2、 temp = (temp & 0xff00ff) + ((temp & 0xff00fff00) >> 8);
改为: temp = (temp & 0xff00ff) + ((temp & 0xff00ff00) >> 8);
接下来开始分析改算法是如何实现二进制表示中1的个数统计的,为了方便理解,我们把代码改成如下的形式:
int func(unsigned int i)
{
    unsigned int temp = i;
    temp = (temp & 0x55555555) + ((temp>> 1) & 0x55555555);  //temp相邻位相加  
    temp = (temp & 0x33333333) + ((temp >> 2) & 0x33333333);  //temp相邻(以2为单位)相加
    temp = (temp & 0x0f0f0f0f) + ((temp>> 4) & 0x0f0f0f0f);    //temp相邻(以4为单位)相加
    temp = (temp & 0xff00ff) + ((temp>> 8) & 0xff00ff);       //temp相邻(以8为单位)相加
    temp = (temp & 0xffff) + ((temp>> 16) & 0xffff) ;          //temp相邻(以16为单位)相加
    return temp;
}
temp相邻位相加:相加原理若相邻的两个数为00则结果为00, 相邻的两个数为01或10则结果为01,相邻两个数为11则结果为10,也就是先小范围统计每两位中1的个数,后面的步骤在累计有多少个1.
0x11530828的二进制表示如下:
0001  0001 1001 0011 0000 1000 0010 1000;
0  1    0  1   1  1   0  2   0  0   1  0   0  1   1  0;
  1         1       2      2        0      1        1      1;
        2                 4                1                    2 
                  6                                    3
                                    9