二进制平行算法

2019-11-08 20:16:34

字体：大中小

来源：转载

供稿：网友

接下来开始分析改算法是如何实现二进制表示中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

上一篇：nginx 参数优化

下一篇：洛谷 P1328 生活大爆炸版石头剪刀布