备考首页> C++> 表达式和语句

填空题 1 /71

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

查看讨论

上一题下一题