/*http://resnet.uoregon.edu/~gurney_j/jmpc/bitwise.html*/#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)#define BX_(x) ((x) - (((x)>>1)&0x77777777) - (((x)>>2)&0x33333333) - (((x)>>3)&0x11111111))
以一个4bit的数据ABCD为例,其中A~D为0或1。
则
BX_(x) = ABCD - 0ABC - 00AB - 000A
= (1-1/2-1/4-1/8)A000 + (1-1/2-1/4)B00 + (1-1/2)C0 + D
= A +B +C +D
所以,BX_(X) 可以看作低4位的BIT_COUNT运算。
进一步,如果是一个8位的ABCD0000进行BX_()运算:
BX_(ABCD0000) = ABCD0000 - (ABC 0000) - (AB 0000) - (A 0000)
= (A+B+C+D)<<4
所以,写到这里BX_(x)的功能基本既可以猜出来了,它以4bit为一个单位进行BIT_COUNT,在此基础上16进制。
上例中BX_(x)最多可以支持0xffff_ffff,即32位的数据
那么可以猜测一下,BITCOUNT()应该实现如下功能:
BITCOUNT(x) = sum( 0x000_000f & (BX_(x) >> (i*4)) ),其中sum()表示求和运算,i的取值为0~7。
下面来看BITCOUNT(x)的定义,比较简单:
#define BITCOUNT(x) (((BX_(x)+(BX_(x)>>4)) & 0x0F0F0F0F) % 255)
先来假设x是一个8位的数,上式就括号里有作用,显然成立,相当于:
#define BITCOUNT(x) (BX_(x)+(BX_(x)>>4)
再来看如果x是一个16位的数,比如abcd,其中a~d代表一个4bit的数。
并且BX_(abcd) = efgh, BITCOUNT 应该等于 e+f+g+h。
则BITCOUNT(abcd) = ((efgh + 0efg ) & 0x0f0f) %0xff
= 0j0k % 0xff ,其中j= e+f, k = g+h
= j+k = e+f+g+h,得证。
如果,x是一个32位的数呢,比如ijkl_mnop,则BX_(ijkl_mnop)=abcd_efgh,需要证明 BITCOUNT = sum(a,h)
BITCOUNT(x) = ((abcd_efgh + 0abc_defg) & 0x0f0f_0f0f) % 0xff
= 0q0r0s0t % 0xff, 其中 q=a+b,r=c+d, s=e+f, t=g+h
= q+r+s+t = sum(a,h),从而得证。
可以进一步思考,仅从BX_(x)的0x77777777等考虑支持32位数据,但从取余255考虑那该支持多少位呢,哈哈。