第二章基础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位和后缀0的掩码(0101 1000->0000 1111) x^(x-1) (^表示异或)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.寻找一个和给定非负整数有相同数目的1位的下一个大数（将集合表示成数，元素为数位）：s <-x&(-x) x=01111 0000, s=00001 0000r <-s+x r=10000 0000t <-((x^r)>>2)/s x^r=11111 0000, t=00000 0111y <-r|t y=10000 0111寻找一个和给定非负整数有相同数目的1位的下一个大数: x&(x-1) + 12.4 绝对值函数先计算y <- x>>31，然后使用 abs: (x^y)-y or (x+y)^y or x-(x<<1 & y)nabs:y-(x^y) or (y-x)^y 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)^t)-t (t=y>>31)= (abs(x)+t)^t2.14 循环移位(x为无符号整数）左循环移位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){shift &= 0x3f;val = (val>>(0x40 - shift)) | (val << shift);return val;}2.19 交换寄存器x = x oper y, y = y oper x, x = x oper y; oper可为+、-、异或和异或的补(≡)a.交换寄存器的相应字段：给定x和y以及掩码m，当第i为的掩码m(i)=1时，交换x和y的第i位内容，否则不变第一种方法：x = x^y; y = y^(x&m); x = x^y 第二种方法：tmp = (x&~m)|(y&m); y = (y&~m)|(x&m); x = tmp第三种方法：x = x≡y; y = y≡(x|m); y =x≡y 第四种方法：tmp = (x^y)&m; x = x^t; y = y^tb.同一寄存器的两个字段交换(x为非负整数)x: |-----------------------------------| 假设C和D段占k位,m 是对应于D段的各位值为1的掩码，现需要交换B和D段：| A | B | C| D | E | t1 = [x^(x>>k)]&m; t2 = t1 << k; val = x^t1^t2|-----------------------------------|上述基于异或的交换方法，当m为0时退化为无操作，当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)&(-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 >>16); 循环次数是前导0数目循环次数是x中1位的数目return 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) & 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/2^31 (x/2^31 = 0, x为无符号整数)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 = x + (x >> 8);x = x + (x >> 16);return x & 0x0000003F;}其它：int pop3(unsigned int x) // ?{unsigned int n;// 每三位计算1数目n = (x >> 1) & 033333333333;x = x - n;n = (n >> 1) & 033333333333;x = x - n;x = (x + (x >> 3)) & 030707070707; // 相邻的3位字段相加，形成6位字段和x = x%63; // 将各个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 >> 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 table[256] = {0, 1, 1,......, 7, 7, 8};return table[x & 0xFF] + table[(x >> 8) & 0xFF]+table[(x >> 16) & 0xFF] + table[(x >> 24)];}5.2 字的奇偶性1.计算1位的个数，然后由结果的最右侧位决定2.由r <- ⊕(x >> i) (0<=i<n)，结果由r的最右侧位决定y = x ^ (x >> 1)y = y ^ (y >> 2)y = y ^ (y >> 4)y = y ^ (y >> 8)y = y ^ (y >> 16)若将右移位变成左移位，则x的奇偶性出现在y的最左侧位，而y的第i位给出x从这一位到最右侧位奇偶性 3. x = x ^ (x >> 1)x = (x ^ (x >> 2)) & 0x11111111x = x * 0x11111111 // 将各个四位数加到一起并把和放入到高阶十六进制位的数字中p = (x >> 28) & 1 // p=1(odd) or p=0(even)5.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 <= 0x0000FFFF) // 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 <<16;y = x >> 1; if(y != 0) return (n-2);}return (n-x);if(x <= 0x00FFFFFF) // if((x & 0xFF000000) == 0) // n = 32; c = 16;{// do{n += 8; x = x <<8;// y = x >> c; if(y != 0) {n -= c; x = y;} }// c = c >> 1;if(x <=0x0FFFFFFF)// }while(c != 0);{// return (n-x);n += 4; x = x <<4;}}int nlz3(int x)if(x <=0x3FFFFFFF){{int y=x, n= 0;n += 2; x = x <<2; L: if(x < 0) return n;}if (y == 0) return (32-n);if(x <=0x7FFFFFFF)n += 1;n +=1;x = x << 1; }y = y >> 1;goto L:int nlz4(unsigned intx)return -1;{} 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. 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;if((x & 0x0000FFFF) == 0) {n += 16; x = x >> 16;}if((x & 0x000000FF) == 0) {n += 8; x = x >> 8;}if((x & 0x0000000F) == 0) {n += 4; x = x >> 4;}if((x & 0x00000003) == 0) {n += 2; x = x >> 2;}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(unsigned int x) // 将每个0字节变为0x80，每个非0字节变为0x00{unsigned 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) ^ 1;elsereturn (y >> 15) ^ 3;return -1;(2) 查表法// 求对0x7F的余数，将原始值中最多的四个1位移动并压缩到最右侧4个位上// 0x80808080%127=15; 0x80000000%127=8;0x00008080%127=3 etc.static char table[16] = {4, 3, 4, 4, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0};return table[y % 127];*/return n;}该方法一种有趣变形：设a、b、c、d分别对应于谓词“第i字节非零”，则zbytel(x) = a + ab + abc + abcdy = (x & 0x7F7F7F7F) + 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值，可以用0x77FF7FFF取代该方法中的掩码int zbyter(unsigned int x) // 最右0字节{unsigned int y = (x & 0x7F7F7F7F) + 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)，搜索x^0x20202020中的0字节；同样为了搜索两个字x和y中相等字节的位置，可以搜索x^y中的0字节(2) 搜索给定范围内的值( )寻找0到9之间值得最左侧字节的下标:y = (x & 0x7F7F7F7F) + 0x76767676; y = ~(y | x | 0x7F7F7F7F); n = nlz(y) >> 3;寻找字中第一个大写字母(0x41~0x5A)：d = (x | 0x80808080) - 0x41414141; d = ~((x | 0x7F7F7F7F) ^ d);y = (d & 0x7F7F7F7F) + 0x66666666; y = ~(y | d | 0x7F7F7F7F); n = nlz(y) >> 3;6.2 寻找第一个给定长度或更长的1位串int ffstr1(unsigned int x, int n){int k, p=0;while(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, int n){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&(x << 2); x = x&(x << 4); // 顺序可以颠倒n = nlz(x);第7章位与字节的重排列7.1 位与字节的反转if(k & 1) x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >> 1;if(k & 2) x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >> 2;if(k & 4) x = (x & 0x0F0F0F0F) << 4 | (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反转字中左右两个半字，例如：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) & 0x00F000F0 | 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 mMnN 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) & 0x55555555;将0000 0000 0000 0000 abcd efgh ijkl mnop 变为 0a0b 0c0d 0e0f 0g0h 0i0j 0k0l 0m0n 0o0p其逆过程为：x = ((x >> 1) | x) & 0x33333333;x = ((x >> 2) | x) & 0x0F0F0F0F;x = ((x >> 4) | x) & 0x00FF00FF;x = ((x >> 8) | x) & 0x0000FFFF;7.3 转置位矩阵a0 = 0123 b0 = 048ca1 = 4567 ==> b1 = 159da2 = 89ab b2 = 26aea3 = cdef b3 = 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 & 2) | (a3 & 2) >> 1;b4 = (a0 & 1) << 3 | (a1 & 1) << 2 | (a2 & 1) << 1 | (a3 & 1);一种好的编码：m = m^(m<<j)，j的取值依次是16、8、4、2和1，而m的取值依次是：0x0000FFFF、0x00FF00FF、0x0F0F0F0F、0x33333333、0x55555555void transpose32(unsigned int A[32]) { // 32*32矩阵转换 int j, k, m, t;m = 0x0000FFFF;for(j=16; j!=0; j=j>>1, m=m^(m<<j)) {for(k=0; k<32; k=(k+j+1)&~j) {t = (A[k] ^ (A[k+j] >> j)) & m;A[k] = A[k]^t;A[k+j] = A[k+j] ^ (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 qsuw 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 & m; // clear irrelevant bitsmk = ~m << 1;for(i = 0; i < 5; ++i) {mp = mk ^ (mk << 1); // parallel prefixmp = mp ^ (mp << 2);mp = mp ^ (mp << 4);mp = mp ^ (mp << 8);mp = mp ^ (mp << 16);mv = mp & m; // bits to movem = m ^ mv | (mv >> (1 << i)); // compress mt = x & mv;x = x ^ t | (t >> (1 << i)); // compress xmk = mk & ~mp;}return x;}编程之美2.1节中的扩展题第1题：如果变量是32位的Dword，则如何统计该二进制数中1的个数。
