请问 func(0x11530828)的返回值是?

[填空题]

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

推荐

努力去BAT的女子

首先确定这个题是想考察数的二进制表示中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

编辑于 2015-09-05 22:22:05 回复(16)

L.K.

平行法计算二进制中1的个数，二进制中利用相邻位相加，直到最后剩下一个数，求出1的个数。

举例：

求255（1111 1111）二进制中1的个数。

1 1 1 1 1 1 1 1

2 2 2 2

4 4

将255的8个位置进行编号，1号位置到8号位置，首先对12、34、56、78进行相加，得到2、2、2、2，分别存放于12、34、56、78位置，再将12、34、56、78看成一个整体，将12和34、56和78相加，得到4、4存放于1234、5678位置，最后再将1234和5678相加，得到8。算法也是利用了二分的思想，给定一个二进制数，将均分成两部分，分别求左边和右边的1的个数，然后相加，最后得到结果。

发表于 2015-08-11 09:42:37 回复(0)