读书人

请各位帮小弟我解释一下这个程序关于

发布时间: 2012-03-17 19:06:28 作者: rapoo

请各位帮我解释一下这个程序,关于位运算的
unsigned int
ones32(register unsigned int x)
{
/* 32-bit recursive reduction using SWAR...
but first step is mapping 2-bit values
into sum of 2 1-bit values in sneaky way
*/
x -= ((x > > 1) & 0x55555555);
x = (((x > > 2) & 0x33333333) + (x & 0x33333333));
x = (((x > > 4) + x) & 0x0f0f0f0f);
x += (x > > 8);
x += (x > > 16);
return(x & 0x0000003f);
}
程序作用应该是算32位2进制数中1的个数。但是具体每一步右移和位运算的作用不明,希望能讲解一下。

[解决办法]
第一步: x -= ((x > > 1) & 0x55555555); 把 x 按 2 个 bit 一组进行分组,然后计算每一个分组中 1 的个数,具体来说就是把每个分组的 00-> 00 01-> 01 10-> 01 11-> 10
第二步: (((x > > 2) & 0x33333333) + (x & 0x33333333)); 把 x 按 4 个 bit 一组进行分组,并计算出其中每一个组中 1 的个数。
第三步: (((x > > 4) + x) & 0x0f0f0f0f); 把 x 按 8 个 bit 一组进行分组(就是一个 BYTE 了),并计算每一个分组中 1 的个数。
第四步: x += (x > > 8); 把第一个 BYTE(现在每个 BYTE 中都放着那个BYTE中1的个数) 和第二个 BYTE 相加放到第一个 BYTE 中,把第三个 BYTE 和第四个 BYTE 相加放到第三个 BYTE 中。
第五步:x += (x > > 16); 把第一个 BYTE 和第三个 BYTE 相加放到第一个 BYTE 中。
最后一步: return(x & 0x0000003f); 把出了最后一个 BYTE 之外的其余值清 0 来返回。

读书人网 >C++

热点推荐