计算二进制数中1的个数

《计算二进制数中1的个数》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、第二章基础2.1操作最右侧位a.最右侧的1->0(01011000->01010000)x&(x-1)，可用来判断无符号整数是否为2的幂；x&(x+1)可用来检测无符号数是否为pow(2,n)-1的形式b.析出最右侧的1位(01011000->00001000)x&(-x)；析出最右侧的0位(01010111->00001000)~x&(x+1)c.识别后缀0的掩码(01011000->00000111)~x&(x-1)or~(x

2、(-x))or(x&-x)-1d.识别最右侧1位和后缀0的掩码(01011000->00001111)x^(x-1)(^表示

3、异或)e.向右传播最右侧的1位(01011000->01011111)x

4、(x-1)f.将最右侧连续的1位串修改成0位串(01011000->01000000)((x

5、(x-1))+1)&x，可用来检查一个非负整数是否具有pow(2,j)-pow(2,k)的形式(j>=k>=0)g.将上述具有对偶性公式的1和0,(x+1)和(x-1),~(x+1)和(-x),&和

6、相替换，而x与~x不变，则可以得出新的公式h.寻找一个和给定非负整数有相同数目的1位的下一个大数（将集合表示成数，元素为数位）：                   s<-x&(-x)    

7、          x=011110000,s=000010000                   r<-s+x                  r=100000000                   t<-((x^r)>>2)/s      x^r=111110000,t=000000111                   y<-r

8、t                y=100000111寻找一个和给定非负整数有相同数目的1位的下一个大数:x&(x-1)+12.4绝对值函数先计算y<-x>>31，然后使用abs:(x^y)-yor(x+y

9、)^yorx-(x<<1&y)                             nabs:y-(x^y)or(y-x)^yor(x<<1&y)-x2.7符号函数sign(x)=-1(x<0),0(x=0),1(x>0),使用比较谓词指令(x>0)-(x<0)or(x>=0)-(x<=0)（可推广到x与y比较）,或者(x>>31)

10、(-x>>31)2.9符号传递ISIGN(x,y)=abs(x)(y>=0),-abs(x)(y<0)              =(abs(x)^t)-t      (t=y>>31)              =(a

11、bs(x)+t)^t2.14循环移位(x为无符号整数）左循环移位n个位：y=(x<

12、(x>>(32-n))右循环移位n个位：y=(x>>n)

13、(x<<(32-n))摘自rotl.c，向左移位unsigned__cdecl_rotl(     unsignedval,     intshift     ){     shift&=0x1f;     val=(val>>(0x20-shift))

14、(val<

15、4val,     intshift     ){     shift&=0x3f;     val=(val>>(0x40-shift))

16、(val<

17、(y&m);y=

18、(y&~m)

19、(x&m);x=tmp    第三种方法：x=x≡y;y=y≡(x

20、m);y=x≡y    第四种方法：tmp=(x^y)&m;x=x^t;y=y^tb.同一寄存器的两个字段交换(x为非负整数)x:

21、-----------------------------------

22、     假设C和D段占k位,m是对应于D段的各位值为1的掩码，现需要交换B和D段：     

23、     A     

24、B

25、C

26、    D    

27、       E      

28、     t1=[x^(x>>k)]&m;t2=t1<

29、val=x^t1^t2     

30、-----------------------