第二章 基础
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)-1
d.识别最右侧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 0000
精品文档
精品文档
r <- s+x r=10000 0000
t <- ((x^r)>>2)/s x^r=11111 0000, t=00000 0111
y <- r|t y=10000 0111
寻找一个和给定非负整数有相同数目的1位的下一个大数: x&(x-1) + 1
2.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)-x
2.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)^t
精品文档
精品文档
2.14 循环移位(x为无符号整数）
左循环移位n个位：y=(x< 右循环移位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^t b.同一寄存器的两个字段交换(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)< 精品文档 x&(-8) or (x>>3)<<3 上舍入到已知2的幂的倍数, t=(1< 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 精品文档 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)) & 0x11111111 x = x * 0x11111111 // 将各个四位数加到一起并把和放入到高阶十六进制位的数字中 p = (x >> 28) & 1 // p=1(odd) or p=0(even) 5.3 前导0计数 int nlz1(unsigned int x) int nlz2(unsigned int x) { { 精品文档 精品文档 int n = 0; unsigned int y, n=32; if(x == 0) return 32; 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; } } if(x <= 0x3FFFFFFF) { n += 2; x = x << 2; } if(x <= 0x7FFFFFFF) n += 1; } int nlz4(unsigned int x) 精品文档 int nlz3(int x) { int y=x, n= 0; L: if(x < 0) return n; if(y == 0) return (32-n); n += 1; x = x << 1; y = y >> 1; goto L: 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 bytes int n = nlz(y) >> 3; /* (1) 不用nlz指令的分支方法 if(y == 0) return 4; 精品文档 精品文档 else if(y > 0x0000FFFF) return (y >> 31) ^ 1; else return (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 + abcd y = (x & 0x7F7F7F7F) + 0x7F7F7F7F; y = y | x; // leading 1 on nonzero bytes a = 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) = 0xE6A2C480 精品文档 精品文档 k=24反转字中的字节，例如：rev(0x1234567) = 0x67452301 k=16反转字中左右两个半字，例如：rev(0x1234567) = 0x45670123 k=7反转每个字节中的位，例如：rev(0x1234567) = 0x80C4A2E6 7.2 混洗位 abcd efgh ijkl mnop ABCD EFGH IJKL MNOP x=(x&0x0000FF00) << 8 | (x>>8) & 0x0000FF00 | x&0xFF0000FF abcd efgh ABCD EFGH ijkl mnop IJKL MNOP x=(x&0x00F000F0) << 4 | (x>>4) & 0x00F000F0 | x&0xF00FF00F abcd ABCD efgh EFGH ijkl IJKL mnop MNOP x=(x&0x0C0C0C0C) << 2 | (x>>2) & 0x0C0C0C0C | x&0xC3C3C3C3 abAB cdCD efEF ghGH ijIJ klKL mnMN opOP x=(x&0x22222222) << 1 | (x>>1) & 0x22222222 | x&0x99999999 aAbB 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 = 048c 精品文档 精品文档 a1 = 4567 ==> b1 = 159d a2 = 89ab b2 = 26ae a3 = 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< void 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< 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 zBDF 精品文档 精品文档 1、简单循环算法 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 bits mk = ~m << 1; for(i = 0; i < 5; ++i) { mp = mk ^ (mk << 1); // parallel prefix mp = mp ^ (mp << 2); mp = mp ^ (mp << 4); mp = mp ^ (mp << 8); mp = mp ^ (mp << 16); mv = mp & m; // bits to move m = m ^ mv | (mv >> (1 << i)); // compress m t = x & mv; 精品文档 精品文档 x = x ^ t | (t >> (1 << i)); // compress x mk = mk & ~mp; } return x; } 编程之美2.1节中的扩展题第1题：如果变量是32位的Dword，则如何统计该二进制数中1的个数。 对于该题，我原本的想法还是想采用书中解法三，也就是用统计1中个数的算法v&(v-1)，该算法时间复杂度为该32二进制数中“1”的个数。 后来，我参见了[1]中的解法，该解法甚妙，复杂度只有若干个位运算，与“1”的数目无关。由于[1]写的比较难懂，所以在这里解释一下他的解法。 解法一： int Count(unsigned x) { x = x - ((x >> 1) & 0x55555555); // 1 精品文档 精品文档 x = (x & 0x33333333) + ((x >> 2) & 0x33333333); // 2 x = (x + (x >> 4)) & 0x0F0F0F0F; //3 x = x + (x >> 8); //4 x = x + (x >> 16); //5 return x & 0x0000003F; // 6 } 我们以0000 0000 0000 0000 0000 0000 1011 0101为例 第一行中，x>>1是右移一位，(x>>1) 为 0000 0000 0000 0000 0000 0000 0101 1010 该结果与0101 0101 0101 0101 0101 0101 0101 0101相与，等于 0000 0000 0000 0000 0000 0000 0101 0000 实际上，((x >> 1) & 0x55555555) 该步是想得到原数据x的偶数位的数据。（代码是先右移，再得奇数位，这个等价于：先得偶数位，再右移） 然后，x-((x >> 1) & 0x55555555) 则是 用原数据减去原数据的偶数位。结果是 0000 0000 0000 0000 0000 0000 0110 0101 精品文档 精品文档 其实，之所有要相减就是为了得到第一位与第二位1的个数的和，第三位与第四位1的个数的和，第五位与第六位1的个数的和，以此类推。 那么，为什么要用相减的方法来得到相邻两位的和呢？原理是： 相邻两位1的个数的和是：A-A/2 。原数据是A，右移相当于除2。 比如，如果原数据是1（01），那么一半就是0，相减后就是1，所以有1个“1”。如果原数据是3（11），那么一半就是1，相减后就是2，所有总共有2个“1”。 这样，经过第一行的运算，我们得到每两个相邻位的“1”的总和。 第二行，类似的，是求将原数据第一位第二位的“1“的个数的和 与 第三位第四位的“1”的个数的和 相加。这样，第二行执行后，我们可以得到每四位的“1”的个数的和 第三行，可以得到每八位的“1”的个数的和 第四行，可以得到每16位“1”的个数的和 第五行，可以得到32位数中所有1的个数的和。 第六行，由于32位的数据，1的个数最大也就32个，不可能超过2的6位方，所以只要取最后6位数据就是所有数据1的个数的和了。 这里用的是二分法，两两一组相加，之后四个四个一组相加，接着八个八个，最后就得到各位之和了。[1]. 精品文档 精品文档 解法二： int Count(unsigned x) { unsigned n; n = (x >> 1) & 033333333333; // 1 x = x - n; // 2 n = (n >> 1) & 033333333333; // 3 x = x - n; // 4 x = (x + (x >> 3)) & 030707070707; //5 x = modu(x, 63); // 6 return x; //7 } 这个解法更妙。 精品文档 精品文档 需要注意的是，033333333333和033333333333都是指 八进制的数。 第一行第二行连起来看，这与解法一很类似，目的是为了得到第一位与第二位的“1”的个数和。注意，第31、32位中1的个数和在这一步中被统计好了。 第一行和第三行、第四行连起来看，目的是为了得到第一位与第三位的“1”的个数的和。然后，再与上步的结果加起来，就得到第一位、第二位、第三位的“1”的个数的和。 所以，从第一行到第四行就是为了得到 每三位一组的“1”的个数的和。原理是： 相邻三位的结果是：A-A/2-A/4. 算法中有两次向移。 比如，第一位第二位第三位是011, 则第一次移位后为01，相减后为10，再移位后为0，相减还是10，所以有2个“1”。 再比如，第一位第二位第三位是101，则第一次移位后为10，相减后为011，再移位后为1，相减后是010，所以有2个“1”。 第五行是求相邻六位的1的个数 第六行，比较难懂。在第五行执行完后，我们得到了七组数据，第32、31位为一组，第30-25为一组，……第6-第1为一组。所以可以写成 x_0+x_1*64 + x_2 * 64 * 64 + x_3 * 64 * 64* 64+ x_4 * 64 * 64* 64* 64+ x_5 * 64 * 64* 64* 64* 64+ x_6 * 64 * 64* 64* 64* 64* 64 精品文档 精品文档 这个数除以63的余数 肯定 与 x_0 +……+x_6 相等（因为32位的数据最多也就32个1） [1]中的简短解释：首先是将二进制各位三个一组，求出每组中1的个数，然后相邻两组归并，得到六个一组的1的个数，最后很巧妙的用除63取余得到了结果。 这个程序只需要十条左右指令，而且不访存，速度很快。 精品文档 因篇幅问题不能全部显示，请点此查看更多更全内容