计算二进制数中1的个数

1、第二章基础2.1 操作最右侧位a.最右侧的1->0(0101 1000->0101 0000) x&(x-1),可用来判断无符号整数是否为2的哥；x&(x+1)可用来检测无符号数是否为pow(2,n)-1的形式b.析出最右侧的 1 位(0101 1000->0000 1000) x&(-x);析出最右侧的 0位(0101 0111->0000 1000) x&(x+1)c.识别后缀 0 的掩码(0101 1000->0000 0111) x&(x-1) or (x|(-x) or (x&-x)-1d.识别最右侧1位和

2、后缀0的掩码(0101 1000->0000 1111) xA(x-1) (A表示异或)e.向右传播最右侧的1 位(0101 1000->0101 1111) x|(x-1)f.将最右侧连续的 1位串修改成 0位串(0101 1000->0100 0000) (x|(x-1)+1) & x ,可用来检查一个非负整数是否具有pow(2,j)-pow(2,k)的形式(j>=k>=0)g.将上述具有对偶性公式的1和0, (x+1)和(x-1), (x+1)和(-x), &和|相替换，而x与-x不变,则可以得出新的公式h.寻找一个和给定非负整数有相同数目的

3、1位的下一个大数(将集合表示成数，元素为数位)s <- x&(-x)x=01111 0000, s=00001 0000r <- s+xr=10000 0000t <- (xAr)>>2)/s y <- r|txAr=11111 0000, t=00000 0111 y=10000 0111寻找一个和给定非负整数有相同数目的1位的下一个大数：x&(x-1) + 12.4 绝对值函数先计算 y <-x>>31 ,然后使用 abs: (xAy)-y or (x+y)Ay or x-(x<<1 & y)nabs

4、: y-(xAy) or (y-x)Ay or (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)|(-x>>31)2.9 符号传递ISIGN(x,y) = abs(x)(y>=0), -abs(x) (y<0)=(abs(x)At)-t (t=y>>31)=(abs(x)+t)At2.14 循环移位(x为无符号整

5、数)左循环移位 n 个位：y=(x<< n)|(x>>(32- n)右循环移位 n 个位：y=(x>> n)|(x<<(32- n)摘自rotl.c,向左移位unsigned _cdecl _rotl (unsigned val,int shift)shift &= 0x1f;val = (val>>(0x20 - shift) | (val << shift); return val;unsigned _int64 _cdecl _rotl64 (unsigned _int64 val, int shift)sh

6、ift &= 0x3f;val = (val>>(0x40 - shift) | (val << shift); return val;2.19交换寄存器x = x oper y, y = y oper x, x = x oper y; oper 可为+、-、 异或和异或的补 (& equiv;)a.交换寄存器的相应字段：给定 x和y以及掩码m,当第i为的掩码m(i)=1时，交换x和y 的第i位内容，否则不变第一种方法：x = xAy; y = yA(x&m); x = xAy第二种方法：tmp = (x&m)|(y&m); y

7、=(y&m)|(x&m); x = tmp第三种方法：x = x&equiv;y; y = y&equiv;(x|m); y = x&equiv;y第四种方法： tmp =(xAy)&m; x = xAt; y = yAtb.同一寄存器的两个字段交换(x为非负整数)x: |1假设C和D段占k位,m是对应于 D段的各位值为 1的掩码，现需要交换B和D段：| A | B | C | D | E | t1 = xA(x>>k)&m; t2 = t1 << k; val = xAfTtzI1上述基于异或的交换方法，当m为0

8、时退化为无操作，当 m为全1时则是交换x和y的值第三章2的哥边界(非负整数)3.1 上、下舍入到已知 2的哥的倍数假设舍入的因子以调整量的log2的形式给出，k=log2(调整量)(例如k=3 ,调整量=8)下舍入到已知2的哥的倍数，x&(-1)<<k) or (x>>k)<<k,例如取舍入的调整量为8 x&(-8) or(x>>3)<<3上舍入到已知 2的哥的倍数，t=(1<<k)-1; (x+t)&t或者t=(-1)<<k; (x-t-1)&t,例如取舍入的调整量为8(x+7

9、)&(-8) or x+(-x&7)3.2 上、下舍入到下一个2的哥下舍入到不大于x的最大的2的哥：unsigned flp(unsigned x) y = 0x80000000;do x = x | (x >> 1);while(y > x)y = x;x = x | (x >> 2);y = y >> 1;x = x & (x-1);x = x | (x >> 4);return;while(x != 0);x = x | (x >> 8);return y;x = x | (x >> 1

10、6);循环次数是前导0数目循环次数是x中1位的数Ireturn x - (x >> 1);上舍入到不小于 x的最小的2的哥：unsigned clp(unsigned x) x = x - 1;x = x | (x >> 1);x = x | (x >> 2);x = x | (x >> 4);x = x | (x >> 8);x = x | (x >> 16);return x + 1;第五章 位计数5.1 1位计数1.二分法:x = (x & 0x55555555) + (x >> 1) &

11、 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)另外利用 pop(x) = x - x/2 - x/4 -x/2A31 (x/2A31 = 0, x为

12、无符号整数)int pop2(unsigned int x)x = x - (x >> 1) & 0x55555555);/ 相当于 x = (x& 0x55555555) + (x >> 1) & 0x55555555)x = (x & 0x33333333) + (x >> 2) & 0x33333333);x = (x + (x >> 4) & 0x0F0F0F0F;/ 相当于(x &0x0F0F0F0F) + (x >> 4) & 0x0F0F0F0F),无进位x

13、 = x + (x >> 8);x = x + (x >> 16);return x & 0x0000003F;其它：int pop3(unsigned int x) / ?unsigned int n;/每三位计算1数目n = (x >> 1) &x = x - n;n = ( n >> 1) & x = x - n;033333333333033333333333x = (x + (x >> 3) & 030707070707; / 相邻的3位字段相加,形成6位字段 和x = x%63; / 将各个

14、6位字段相加return x;int pop4(unsigned int x) / ?unsigned int n;/每四位计算1数目n = (x >> 1) & 0x77777777;x = x - n;n = (x >> 1) & 0x77777777;x = x - n;n = (x >> 1) & 0x77777777;x = x - n;x = (x+ (x >> 4) & 0x0F0F0F0F; / 四位和变成八位和x = x*01010101; /将四个字节相加，和放在高阶字节上 return x &

15、gt;> 24;/稀疏字的1位计数法int pop(unsigned int x)int n = 0;while(x != 0)+n;x = x & (x-1);return n;/查表法int pop(unsigned int x)static char table256 = 0,1,1,7, 7, 8;return tablex & 0xFF + table(x >> 8) & 0xFF+table(x >> 16) & 0xFF + table(x >>24); 5.2字的奇偶性1 .计算1位的个数，然后由结果的最

16、右侧位决定2 .由r <- &oplus;(x >> i) (0<=i< n),结果由r的最右侧位决定y = x A (x >> 1)y = y a (y >> 2)y = y a (y >> 4)y = y a (y >> 8)y = y a (y >> 16)若将右移位变成左移位，则x的奇偶性出现在y的最左侧位，而y的第i位给出x从这一位到最右侧位奇偶性3. x = x a (x >> 1)x = (x a (x >> 2) & 0x11111111x = x

17、* 0x11111111/将各个四位数加到一起并把和放入到高阶十六进制位的数字中p = (x >> 28) & 1/ p=1(odd) or p=0(even)3 .3前导0计数int nlz1(unsigned intx)int nlz2(unsigned int x) int n =0；unsigned int y, n=32;if(x = 0) return32;y = x >> 16; if(y != 0) |n -= 16; x = y;y = x >> 8; if(y != 0) n -= 8; x = y;if(x <= 0x00

18、00FFFF)/ if(x & 0xFFFF0000)= 0)y = x >>4; if(y != 0) n -= 4; x = y;y =x >> 2; if(y != 0) n -= 2; x = y;n += 16; x = x <<n-2);16;y = x >> 1; if(y != 0) return ( return ( n-x);if(x <= 0X00FFFFFF) / if(x & OxFFOOOOOO) = 0)/ n=32; c = 16;(/ don += 8; x = x <<8;/

19、y = x >> c; if(y != O) n -= c; x = y;)/c = c >> 1;if(x <=OxOFFFFFFF)/ while(c != O);/ return ( n-x);n += 4; x = x <<4;int nlz3(int x)if(x <=Ox3FFFFFFF)int y=x, n= O;n += 2; x = x <<2;L:if(x < O) return n;if(y = O) return (32-n);if(x <=Ox7FFFFFFF)n += 1; n +=1;x =

20、x << 1; y=y >> 1;goto L:return -1;int nlz4(unsigned int x)x = x | (x >> 1);x = x | (x >> 2);x = x | (x >> 4);x = x | (x >> 8);x = x | (x >> 16);return pop(x); / 见 5.1 节与对数关系:(无符号整数 x!=0) floor(log2(x) = 31 - nlz(x);ceiling(log2(x) = 32 - nlz(x-1) 5.4后缀0计数1 .

21、 ntz(x) = 32 - nlz(x & (x-1) = pop(x & (x-1) = 32 - pop(x | -x)2 .二分法 int ntz(unsigned int x)int n = 1;if(x = 0) return 32;n += 16; x = x >> 16;n += 8; x = x >> 8;n += 4; x = x >> 4;n += 2; x = x >> 2;if(x & 0x0000FFFF) = 0) if(x & 0x000000FF) = 0) if(x &

22、0x0000000F) = 0) if(x & 0x00000003) = 0) return n - (x&1);第六章字搜索6.1寻找第一个0字节int zbytel(unsigned int x) /最左 0 字节if(x >> 24) = 0) return 0;if(x & 0x00FF0000) = 0) return 1;if(x & 0x0000FF00) = 0) return 2;if(x & 0x000000FF) = 0) return 3;els return 4; / 没有 0 字节int zbytel(unsig

23、ned int x) 将每个0字节变为0x80,每个非0字节变为0x00unsigned int y = (x & 0x7F7F7F7F) + 0x7F7F7F7F;y = (y | x | 0x7F7F7F7F); leading 1 on zero bytesint n = nlz(y) >> 3;/* (1) 不用nlz指令的分支方法if(y = 0) return 4;else if(y > 0x0000FFFF)return (y >> 31) A 1;elsereturn (y >> 15) a 3；return -1;(2) 查表

24、法/求对0x7F的余数，将原始值中最多的四个1位移动并压缩 到最右侧4个位上/ 0x80808080%127=15; 0x80000000%127=8;0x00008080%127=3 etc.static char table16 = 4, 3, 4, 4, 1, 1, 1, 1,0, 0, 0,0, 0, 0, 0, 0;return tabley % 127;*/ return n;该方法一种有趣变形：设a、b、c、d分别对应于谓词&ldquo;第i字节非零&rdquo;, zbytel(x) = a + ab + abc + abcdy = (x & 0x7F7

25、F7F7F) + 0x7F7F7F7F;y = y | x;/ leading 1 on nonzero bytesa = y >> 31;b = (y >> 23) & a;c = (y >> 15) & b;d = (y >> 7) & c;return a + b + c + d;另外为了搜索一个字中第一个 4位、随后12位或最后16位是否有0值，可以用 0x77FF7FF现代该方法中的掩码int zbyter(unsigned int x) /最右 0 字节unsigned int y = (x & 0x7

26、F7F7F7F) + 0x7F7F7F7F;y = (y | x | 0x7F7F7F7F);int n = ntz(y) >> 3;/ int n = (32 - nlz(y & (y-1) >> 3;return n;推广：(1)搜索等于任意给定值的字节：对变量x和给定值进行异或，再搜索x中的0字节；例如为了搜索x 中的ASCII空格(0x20),搜索xA0x20202020中的0字节；同样为了搜索两个字 x和y中相等字节的位置，可以搜索 xAy中的0字节(2)搜索给定范围内的值()寻找0到9之间值得最左侧字节的下标:y = (x & 0x7F7F7

27、F7F) + 0x76767676; y =(y | x | 0x7F7F7F7F); n = nlz(y) >> 3;寻找字中第一个大写字母(0x410x5A): d = (x | 0x80808080) - 0x41414141; d =(x | 0x7F7F7F7F) a d);y = (d & 0x7F7F7F7F) + 0x66666666; y = (y | d | 0x7F7F7F7F);|n =nlz(y) >> 3;6.2寻找第一个给定长度或更长的1位用int ffstr1(unsigned int x, intn)int k, p=0;whi

28、le(x != 0) k = nlz(x);x = x << k;p += k;k = nlz(x);if(k >= n) return p;x = x << k;p += k;return 32;int ffstr2(unsigned nt x, intn)int s;while( n > 1) s = n >> 1;x = x & (x << s);n = n - s; return nlz(x);例如计算一个32位字中搜索长度>=8的连续1位用x = x&(x << 1); x = x&

29、(x << 2); x = x&(x << 4); /顺序可以颠倒n = nlz(x);第7章位与字节的重排列7.1 位与字节的反转if(k & 1) x = (x & 0x55555555) << 1 | (x & OxAAAAAAAA) >> 1;if(k & 2) x = (x & 0x33333333) << 2 | (x & OxCCCCCCCC) >> 2;if(k & 4) x = (x & 0x0F0F0F0F) << 4

30、| (x & 0xF0F0F0F0) >> 4;if(k & 8) x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >> 8;if(k & 16)x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >> 16;k=31 反转字中的位，例如：rev(0x01234567) = 0xE6A2c480k=24 反转字中的字节，例如：rev(0x1234567) = 0x67452301k=16反转字中左右

31、两个半字，例如：rev(0x1234567) = 0x45670123k=7反转每个字节中的位，例如：rev(0x1234567) = 0x80C4A2E67.2 混洗位abcd efgh ijkl mnop ABCD EFGH IJKL MNOP x=(x&0x0000FF00) << 8 | (x>>8)& 0x0000FF00 | x&0xFF0000FFabcd efgh ABCD EFGH ijkl mnop IJKL MNOP x=(x&0x00F000F0) << 4 | (x>>4)& 0x

32、00F000F0 | x&0xF00FF00Fabcd ABCD efgh EFGH ijkl IJKL mnop MNOP x=(x&0x0C0C0C0C) << 2 | (x>>2)& 0x0C0C0C0C | x&0xC3c3c3c3abAB cdCD efEF ghGH ijIJ klKL mnMN opOP x=(x&0x22222222) << 1 | (x>>1)& 0x22222222 | x&0x99999999aAbB cCdD eEfF gGhH iIjJ kKlL m

33、MnN oOpP 外混洗结果在上面序列前面加上 x= (x>>16) | (x<<16) 可得到 AaBb CcDd EeFf GgHh IiJj KkLl MmNn OoPp内混洗结果以相反顺序可以实现操作的逆顺序另外针对字左半部所有位都为 0的情况，可以通过x = (x & 0xFF00) << 8) | (x & 0x00FF);x = (x << 4) | x) & 0x0F0F0F0F;x = (x << 2) | x) & 0x33333333;x = (x << 1) | x)

34、 & 0x55555555;将 0000 0000 0000 0000 abcd efgh ijkl mnop 变为 0a0b 0c0d 0e0f 0g0h 0i0j 0k0l 0m0 n 0o0p其逆过程为：x = (x >> 1) | x) & 0x33333333;x = (x >> 2) | x) & 0x0F0F0F0F;x = (x >> 4) | x) & 0x00FF00FF;x = (x >> 8) | x) & 0x0000FFFF;7.3 转置位矩阵a0 = 0123b0 = 048c

35、a1 = 4567 => b1 = 159da2 = 89abb2 = 26aea3 = cdefb3 = 37bf简单方法:b0 =(a0& 8)| (a1& 8)>> 1| (a2 & 8) >> 2 | (a3 &8) >>3;b1 =(a0& 4)<< 1|(a1& 4)| (a2 & 4) >> 1 | (a3 &4) >>2;b2 =(a0& 2)<< 2|(a1& 2)<< 1 | (a2 &

36、 2) | (a3 &2) >>1;b4 =(a0& 1)<< 3|(a1& 1)<< 2 | (a2 & 1) << 1 | (a3 &1);一种好的编码：m = mA(m<<j) , j的取值依次是16、8、4、2和1,而m的取值依次是： 0x0000FFFF、 0x00FF00FF、 0x0F0F0F0F、 0x33333333、 0x55555555 void transpose32(unsigned int A32) / 32*32 矩阵转换int j, k, m, t;m = 0x0

37、000FFFF;for(j=16; j!=0; j=j>>1, m=mA(m<<j) for(k=0; k<32; k=(k+j+1)&j) t = (Ak A (Ak+j >> j) & m;Ak = AkAt;Ak+j = Ak+j A (t << j);7.4 压缩或广义提取例：掩码：0000 1111 0011 0011 1010 1010 0101 0101字 X： abcd efgh ijkl mnop qrst uvwx yzAB CDEF结果： 0000 0000 0000 0000 efgh klop qs

38、uw zBDF1、简单循环算法unsigned int compress(unsigned int x, unsigned int m) unsigned int r=0, s=0, b;do b = m & 1;r = r | (x & b) << s);s += b;x = x >> 1;m = m >> 1;while(m != 0);return r;2、并行前缀方法unsigned int compress(unsigned int x, unsigned int m) unsigned mk, mp, mv, t, i;x = x

39、 & m; / clear irrelevant bitsmk = m << 1;for(i = 0; i < 5; +i) mp = mk A (mk << 1);/ parallel prefixmp = mp a (mp << 2)；mp = mp A (mp << 4);mp = mp A (mp << 8);mp = mp A (mp << 16);mv = mp & m;/ bits tomovem = m A mv | (mv >> (1 << i); / com

40、press mt = x & mv;x = x A t | (t >> (1 << i);/ compress xmk = mk & mp;return x;编程之美2.1节中的扩展题第1题：如果变量是32位的Dword,则如何统计该二进制数中1 的个数。对于该题，我原本的想法还是想采用书中解法三，也就是用统计1 中个数的算法v&(v-1) ，该算法时间复杂度为该32 二进制数中“1”的个数。后来，我参见了1 中的解法，该解法甚妙，复杂度只有若干个位运算，与“1的数目无关。由于 1 写的比较难懂，所以在这里解释一下他的解法。解法一：int Cou

41、nt(unsigned x)x = x - (x >> 1) & 0x55555555); / 1x = (x & 0x33333333) + (x >> 2) & 0x33333333); / 2x = (x + (x >> 4) & 0x0F0F0F0F; /3x = x + (x >> 8); /4x = x + (x >> 16); /5 return x & 0x0000003F; / 6我们以 0000 0000 0000 0000 0000 0000 1011 0101 为例第一行

42、 中， x>>1 是右移一位，(x>>1) 为 0000 0000 0000 0000 0000 0000 01011010该结果与0101 0101 0101 0101 0101 0101 0101 0101 相与，等于0000 0000 00000000 0000 0000 0101 0000实际上，(x >> 1) & 0x55555555)该步是想得到原数据x的偶数位的数据。(代码是先右移，再得奇数位，这个等价于：先得偶数位，再右移)然后， x-(x >> 1) & 0x55555555) 则是 用原数据减去原数据的偶数位。结果是 0000 0000 0000 0000 0000 0000 0110 0101其实， 之所有要相减就是为了得到第一位与第二位1 的个数的和，第三位与第四位 1 的个数的和，第五位与第六位1 的个数的和，以此类推。那么