算法64位处理器

低年级讨论班第第1010章章寻求快速的种群计数寻求快速的种群计数数学科学学院杨嘉骐种群计数(种群计数(popcountpopcount))y种群计数(populationcount或简称为popcount)是一个非常基本的算法,其目的是对一个变量求其二进制表示中"1"的个数.
y在信息论与编码理论中,这个值也被叫做Hammingweight(汉明重量).
汉明距离就是就是gg(汉明)汉明距离就是就是求两个编码异或之后的Hammingweight.
这个算法在某些编码过程中会被大量重复使用,所以有法在某编码过程中会被大复使用,所以有必要进行精细的改进.
y本文主要针对指令系统里不含此命令的RISC(精本文主要针对指令系统里不含此命令的RISC(精简指令集计算机)处理器系统.
本文内容梗概本文内容梗概y平凡的算法y平凡的算法y对算法的改进y算法的应用本文要解决的目标问题非常简明,最平凡的算法文要解决的标非常简,平凡的算易于想到,作者对算法进行反复且多角度优化,告诉我们最简单的算法也大有改进空间,并能反单算有并能映算法设计者的巧思.
最平凡的算法最平凡的算法ypop=0;32位机器中C语言下一个无符号整数由32位进制ypop=0;for(i=0;i>1;}每次判定最末位是否是1,然后右移一位继续比较.
经过32次循环计算出较过次循环计算出结果.
每一循环被编译成大约7条指令.
最平凡的算法最平凡的算法ypop=0;为方便和后来的算法比ypop=0;for(i=0;i>1;}我们认为x的二进制表示每位为0和1的概率相等,则每循环经过15次则每一循环经过1.
5次add,1次and,1次shift,2次比较,那么平均需要2次比较,那么平均需要耗费32*5.
5=176次运算第一次改进第一次改进ypop=0;一般来说处理的数字都不会太大,二进制表示下前面的0很多,所以当右移至各位都是0的时ypop=0;while(x){pop=pop+(x&1);所以当右移至x各位都是0的时候(这时x值也为0)就可以跳出循环了.
另一个改进是去掉pop=pop+(x&1);x=x>>1;}出循环了.
另个改进是去掉比较过程,x&1为false的时候其值为0,正好对pop的值没有}影响.
所以直接加上就可以了.
即使按上个算法假设也只有4*32=128次算术运算如果值4*32=128次算术运算,如果值比较小的话运算数目减少更加明显.
明显.
从缩短循环次数入手从缩短循环次数入手ypop=0;本算法并不那么直观,但是改进效果还是明显的,算法主要ypop=0;while(x){pop=pop+1;目标是减少循环次数.
x&(x-1)的作用是把其最末尾的个"1"位清零每次pop=pop+1;x=x&(x-1);}的一个"1"位清零.
每一次循环减少一个"1",总计算量与"1"的个数成正比,如}量与1的个数成正比,如果按照每个数位上0和1出现概率相同计算需要耗费32*0.
5*4=64次算术运算,大大降低了运算量,但是若以数位长度N来估计复杂度的话数位长度N来估计复杂度的话仍然是O(N)时间代价最小的查表法时间代价最小的查表法staticchartable[256]={0,1,1,2,1,2,2,3,.
.
.
,8};=tbl[&0FF]+tbl[(>>8)&0FF]pop=table[x&0xFF]+table[(x>>8)&0xFF]+table[(x>>16)&0xFF]+table[x>>24];每8位为个单元预先计算好2的8次方共256种每8位为一个单元,预先计算好2的8次方共256种可能的情形每一种的pop值,然后将这4个值相加.
时间代价最小的查表法时间代价最小的查表法时间代价最小的查表法时间代价最小的查表法本算法采用了牺牲空间来达到时间代价最大化的目的只需要执行10次移位求价最大化的目的,只需要执行10次移位、求与和查表运算,但是由于所用空间较大不能像其他几种算法一样在寄存器中运算,不过由于数组固定且不是很大所以在缓存中存储由于数固定不是很大所以在缓存中存储的话还是可以达到很高的效率.
DivideandconquerisanimportantDivideandconquerisanimportanttechniquethatshouldbenearthetoptechniquethatshouldbenearthetoptechniquethatshouldbenearthetoptechniquethatshouldbenearthetopofeveryprogrammer'sbagoftricks.
ofeveryprogrammer'sbagoftricks.
——HenryS.
Warren,Jr.
生活中的例子生活中的例子y早晨一个女生背着一堆书进了阅览室,结果警报响了.
大妈让女生看看是哪本书把警报弄响的结果那女生把大妈让女生看看是哪本书把警报弄响的,结果那女生把书倒出来,准备一本一本的测.
大妈见状急了,把书分成两份第一份过了一下响了她又把这一份又分成两份两份,第份过了下,响了,她又把这份又分成两份接着测,三回就找到了那本书.
大妈又用鄙视的眼光看着那个女生,仿佛在说:O(n)和O(log2n)都分不清……()(g)——转载自某同学校内日志转载自某同学校内日志分治法分治法分治法分治法y字面上的解释是"分而治之",就是把一个复杂的问题分成两字面上的解释是分而治之,就是把个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并问题的解的合并.
——Wikipediay分治法有希望把将原来的复杂度降低到,同时便于并行算法的实现.
)(nNO)log(21NNOny很多著名算法就是采用了分治法的思想,比如二分查找、快速排序(C.
A.
R.
Hoare)、归并排序(JohnVonNeumann)、快速排序(C.
A.
R.
Hoare)、归并排序(JohnVonNeumann)、快速傅里叶变换(Cooley&Tukey)都是著名的快速算法.
原理其实非常直观原理其实非常直观y由于二进制表示的特殊性我们只需要把y由于二进制表示的特殊性,我们只需要把每一位的0和1看成十进制下的0和1,然后把每一位都加起来就能得到最终的结果把每一位都加起来就能得到最终的结果.
这和前面查表法的原理是一样的.
运用分治法解决多个数的加法就可以达到y运用分治法解决多个数的加法就可以达到优化算法的目的.
多数相加的分治算法多数相加的分治算法y求A+B+C+D0A0C=ABCD>>2&0101在本算法中A+B=EF,C+D=GH,+0B0D=ABCD&0101EFGHEF+GH=IJKL,所以算法可以完成运算,加法运算次数为l2同时利用了原值的空间00EF=EFGH>>2&0011log2n,同时利用了原值的空间没有额外的空间开销.
+00GH=EFGH&0011IJKL这里的字母既可代表一位也可代表多位J数字变形采取移位和掩码处理造成的额外运算速度开销较小造成的额外运算速度开销较小.
CC语言实现语言实现CC语言实现语言实现yx=(x&0x55555555)+((x>>1)&0x55555555);yx=(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&0x00FF00FF)+((x>>8)&0x00FF00FF);x=(x&0x0000FFFF)+((x>>16)&0x0000FFFF);0x55555555即为8段的0101,0x33333333为8段的0011,0x0F0F0F0F为4段的00001111,0x00FF00FF为2段的0000000011111111,0x0000FFFF为前16位为0后16位为1.
总共需要需要5次移位,10次求与,5次加法共20次算术运算.
次算术运算.
进一步优化进一步优化intpop(unsignedx){pp(g){x=x-((x>>1)&0x55555555);x=(x&0x55555555)+((x>>1)&0x55555555);x=(x&0x33333333)+((x>>2)&0x33333333);x=(x&0x33333333)+((x>>2)&0x33333333);x=(x+(x>>4))&0x0F0F0F0F;x=(x&0x0F0F0F0F)+((x>>4)&0x0F0F0F0F);x=x+(x>>8);x=x+(x>>16);x=(x&0x00FF00FF)+((x>>8)&0x00FF00FF);()returnx&0x0000003F;}x=(x&0x0000FFFF)+((x>>16)&0x0000FFFF);}进一步优化进一步优化共需要5次移位,4次求与4次加法1次减intpop(unsignedx){x=x-((x>>1)&0x55555555);(033333333)((2)次求与,4次加法,1次减法,共14次算数运算.
减少了6次算术运算.
x=(x&0x33333333)+((x>>2)&0x33333333);x=(x+(x>>4))&0x0F0F0F0F;减少了次算术运算但是程序的整体结构被破坏的较为严重.
x=(x+(x>>4))&0x0F0F0F0F;x=x+(x>>8);x=x+(x>>16);returnx&0x0000003F;}可以更进一步优化可以更进一步优化如果计算机执行乘法较快的话可以考虑用乘法代替加法多于的高位intpopcountmult(unsignedx){法代替加法,多于的高位自动溢出,共总共需要4次移位,4次求与,2次加法,intpopcount_mult(unsignedx){x-=(x>>1)&0x55555555;x=(x&0x33333333)+((x>>2)&0x33333333);1次减法,1次乘法共12次算术运算.
而且本算法易于推&0x33333333);x=(x+(x>>4))&0x0F0F0F0F;return(x*0x01010101)>>24;}而且本算法易于推广至64位整数,只需要改变最后的右移位数即可.
}HAKMEN169HAKMEN169HAKMEN是1972年由MIT人工智能实验室发表的一本算法备忘录,包含那个时代大量的优秀算法,主要使用汇编语言写成,共191个算法.
其中第169算法与种群计数有关,可以参阅如下网址:http://www.
inwap.
com/pdp10/hbaker/hakmem/hakmem.
htmlHAKMEN169HAKMEN169yintpop(unsignedx){unsignedn;算法的主要思想仍然是分治法,和前一个算法的区别有两点.
n=(x>>1)&033333333333;x=x–n;有两点第一点是第一步的时候是每位一组,相邻三组相加.
比如说对于n=(n>>1)&033333333333;x=x-n;x=(x+(x>>3))&比如说对于x=(abc)=4*a+2*b+c,x>>1&常数1=2*a+b,x(x(x3))&030707070707;returnx%63;}x>>2&常数2=a,于是x-(x>>1&常数1)(>>2&常数2)}-(x>>2&常数2)=a+b+cHAKMEN169HAKMEN169第二点是第二步做完之后yintpop(unsignedx){unsignedn;第二点是第二步做完之后,这时是每6位成一组,以12位整数(2组)为例,n=(x>>1)&033333333333;x=x–n;x=(ab)64=a*64+b.
很明显,a*64+b≡a+b(mod63).
模63就可以得到a+b.
n=(n>>1)&033333333333;x=x-n;x=(x+(x>>3))&就总共需要3次移位,3次求与,2次加法,1次乘法,1次取模共10次算术运算x(x(x3))&030707070707;returnx%63;}共10次算术运算.
不过取模运算速度较慢易成为瓶颈,所以在实际测试中并表别快}中并没有表现出特别快的速度.
不太实用的方法不太实用的方法不太实用的方法不太实用的方法其中加法靠不断对字长取模进行,需要62次算术运算,不能对非2的n次方字长的字进行运算.
WikipediaWikipedia上的上的测试结果测试结果ypopcount_naive:1.
6666e+07itersin688msecsfor41.
28nsecs/iter//原始算法ypopcount8:1e+08itersin995msecsfor995nsecs/iterypopcount_8:1e+08itersin995msecsfor9.
95nsecs/iterypopcount_6:2e+08itersin1725msecsfor8.
625nsecs/iterypopcount_hakmem:2e+08itersin1411msecsfor7.
055nsecs/iter//HAKMEM算法明显被取模耽误时间//HAKMEM算法,明显被取模耽误时间ypopcount_keane:1e+09itersin6566msecsfor6.
566nsecs/iterypopcount_3:1e+09itersin6270msecsfor6.
27nsecs/iterypopcount_2:1e+09itersin5658msecsfor5.
658nsecs/iter//改进算法ypopcount_mult:1e+09itersin4169msecsfor4.
169nsecs/iterpp_//带乘法改进算法y转载自http://wiki.
cs.
pdx.
edu/forge/popcount.
htmly使用算法源代码参见http://enwikipediaorg/wiki/Hammingweighty使用算法源代码参见http://en.
wikipedia.
org/wiki/Hamming_weight数组中的种群计数数组中的种群计数数组中的种群计数数组中的种群计数y最平凡的方法:把数组中的每个值分别进行种群计数然后相加行种群计数,然后相加.
y基于原算法的改进:由于数组中连续存储的二进制码相当于对一个32n位的数进行种群计数,于是发挥原算法的空间极限对每3群计数,于是发挥原算法的空间极限对每3个字为一组,在每三个4位/8位/16位的掩码结果相加结果相加.
基于基于CSACSA的一个算法的一个算法基于基于CSACSA的一个算法的一个算法y本算法借鉴了逻辑电路的设计思想利y本算法借鉴了逻辑电路的设计思想,利用CSA(carry-saveadder)保留进位加法器的设计思路完成快速处理一个数法器的设计思路,完成快速处理一个数组内种群计数总和的问题.
核心是定义这样两个输出值高位输出hy核心是定义这样两个输出值:高位输出h,低位输出lh=(a|b)&(b|c)&(c|a)=(a|b)&(a&b)|c=a|b&(a^b)|cl=(a^b)^cl(ab)c基于基于CSACSA的一个算法的一个算法基于基于CSACSA的一个算法的一个算法y#defineCSA(hlabc)\y#defineCSA(h,l,a,b,c)\{unsignedu=a^b;unsignedv=c;\h=(a&b)|(u&v);l=u^v;}intpopArray(unsignedA[],intn){ittti对于3个32位字,对其同一数位上的3个二进制码构成的三元组(a,b,c)inttot,i;unsignedones,twos;tot=0;//Initialize.
ones=0;f(i0i2ii2){若有3个"1"则h=1,L=1;2个"1"则h=1,L=0;1个"1"则h=0,L=1;for(i=0;i64位处理器安腾2已经提供了这条指令,在gcc的较高版本和VC2008中也供了这条指令,在gcc的较高版本和VC2008中也提供了这条函数.
y简单的应用譬如位向量表示集合的求数目总和、简单的应用譬如位向量表示集合的求数目总和、开头提到的求汉明距离.
y求后缀0:y求后缀0:ntz(x)=pop(~x&(x-1))=32–pop(x|-x)y生成符合二项分布的随机整数y生成符合二项分布的随机整数应用应用应用应用y中等稀疏矩阵的储存y中等稀疏矩阵的储存对矩阵A,使用一个额外的位串bits,A[i]中凡是有定义的位置ibits中相应的比特位i是1(位是有定义的位置i,bits中相应的比特位i是1(位向量表示存储).
由于位串可能很长将分成若干个32位字存储由于位串可能很长,将分成若干个32位字存储,用种群计数计算每个字的"1"含量就可以知道该字中含有几个元素,可以起到加速查找的作用.
该字中含有几个元素,可以起到加速查找的作用.
启示启示启示启示y大的算法框架和小的算法优化都值得注意大的y大的算法框架和小的算法优化都值得注意,大的算法框架更为重要因为其往往会带来算法效率数量级的进步,具体到每一步的算法优化也有机会量级的进步,具体到每步的算法优化也有机会在局部大幅度提高效率,但是往往会以牺牲程序可读性为代价.
可读性为代价参考文献参考文献参考文献参考文献[1]HammingWeight:http://en.
wikipedia.
org/wiki/Hamming_weight[2]popcount:http://dafandong.
spaces.
live.
com/blog/cns!
2F6B5FFD15BDD1D6!
637.
entry[3]HAKMEMITEM169:http://www.
inwap.
com/pdp10/hbaker/hakmem/hacks.
html#item169[4]Popcount:http://wiki.
cs.
pdx.
edu/forge/popcount.
html[5]HAKMEM169andotherpopcountimplementations:http://www.
dalkescientific.
com/writings/diary/archive/2008/07/03/hakmem_and_other_popcounts.
htmlThanksThanks