谁能帮忙解释一下这段程序的原理吗?

arcanelove

int bits_set(int word)
{
int tmp;
tmp = (work>>1)&033333333333;
tmp = word - tmp - ((tmp>>1)&033333333333);
return(((tmp +(tmp>>3))&030707070707)%077);
}

此程序的功能是输入一个整数,然后判断这个整数的二进制表示下有多少个1.
请帮忙解释一下程序的原理,还有最后一个%077有什么用
谢谢大家

stoneboy4000

Hacker's delight
先以2bits为一组计算1的个数，放在这2bits中；
再以4bits为一组，计算相邻的两组2bits的1的个数；
再以8bits为一组，计算相邻的两组4bits的1的个数，以次类推。
如下所示：
10 11 11 00 01 10 00 11 01 11 11 10 11 11 11 11
01|10|10|00|01|01|00|10|01|10|10|01|10|10|10|10
00 11|00 01|00 10|00 10|00 11|00 11|01 00|01 00
00 00 01 00|00 00 01 00|00 00 01 10|00 01 00 00
00 00 00 00 00 00 10 01|00 00 00 00 00 00 11 10
00 00 00 00 00 00 00 00 00 00 00 00 00 01 01 11

C程序：
x=x&0x55555555 + (x>>1)&0x55555555;
x=x&0x33333333 + (x>>2)&0x33333333;
x=x&0x0F0F0F0F + (x>>4)&0x0F0F0F0F;
x=x&0x00FF00FF + (x>>8)&0x00FF00FF;
x=x&0x0000FFFF + (x>>16)&0x0000FFFF;

copy from jingya_feng

有些类似，参考参考吧^_^

arcanelove

我理解这个程序的过程和结果
但是不知道原理就是为什么这么编写能达到结果,请高手指导一下

KTPOPO

用分治法减低循环累加强度之后,结果就是这样.....
把原本一位一位计算的东西,变成了并行计算.再展开.

KTPOPO

用分治法减低循环累加强度之后,结果就是这样.....
把原本一位一位计算的东西,变成了并行计算.再展开.

stoneboy4000

理解万岁

对这个问题来说，过程就是原理，应该和其他公式定理一样，有人提问，就有人研究，于是就有了这个算法
其实要证明的话很可能就是穷举
ps：本结论纯属猜测，如有雷同，纯属偶然^_^

吉娃娃

看来大家不了解 计算机组成原理(数据格式)和操作系统(系统平台差异)以及数学知识.

arcanelove

看来大家不了解 计算机组成原理(数据格式)和操作系统(系统平台差异)以及数学知识

____________________________________________

那能不能请你稍微解释一下呢？谢谢

天魔狂舞

理解了。
mark