《计算进制数中的个数》由会员分享，可在线阅读，更多相关《计算进制数中的个数（15页珍藏版）》请在金锄头文库上搜索。
1、第二章 基础 2.1 操作最右侧位 a.最右侧的 1-0(0101 1000-0101 0000) x t2 = t1 k)3) 1); while(y x) y = x;x = x | (x 2); y = y 1; x = x 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
2、 | (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 / 相当于 x = (x x = (x + (x 4) / 相当于(x x = x + (x 16); return x 其它： int pop3(unsigned int x) / ? unsigned int n n; / 每三位计算 1 数目 n n = (x 1) x = x - n n; n n = (n n 1) x = x - n n;x = (x + (x
3、3) / 相邻的 3 位字段相加，形成 6 位字 段和x = x%63; / 将各个 6 位字段相加return x; int pop4(unsigned int x) / ? unsigned int n n;/ 每四位计算 1 数目n n = (x 1) x = x - n n;n n = (x 1) x = x - n n;n n = (x 1) x = x - n n;x = (x+ (x 4) / 四位和变成八位和x = x*01010101; / 将四个字节相加，和放在高阶字节上return x 24; / 稀疏字的 1 位计数法 int pop(unsigned int x) i
4、nt n n = 0; while(x != 0)+n n;x = x return n n; / 查表法 int pop(unsigned int x) static char table256 = 0, 1, 1,., 7, 7, 8; return tablex 5.2 字的奇偶性 1.计算 1 位的个数，然后由结果的最右侧位决定 2.由 r i) (0 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 (
5、x 1)x = (x (x 2) unsigned int y, n n=32;if(x = 0) return 32; y = x 16; if(y != 0) n n -= 16; x = y;y = x 8; if(y != 0) n n -= 8; x = y;if(x 4; if(y != 0) n n -= 4; x = y; y = x 2; if(y != 0) n n -= 2; x = y;n n += 16; x = x 1; if(y != 0) return (n n-2); return (n n-x);if(x c; if(y != 0) n n -= c; x
6、= y; / c = c 1;if(x 1;goto L: int nlz4(unsigned int x) 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 if(x = 0) return 32;if(x
7、 x = x 16;if(x x = x 8;if(x x = x 4;if(x x = x 2;return n n - (x 第六章 字搜索 6.1 寻找第一个 0 字节 int zbytel(unsigned int x) / 最左 0 字节 if(x 24) = 0) return 0;if(x if(x if(x els return 4; / 没有 0 字节 int zbytel(unsigned int x) / 将每个 0 字节变为 0x80，每个非 0 字节变为 0x00 unsigned int y = (x y = (y | x | 0x7F7F7F7F); / lead
8、ing 1 on zero bytesint n 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 table16 = 4, 3, 4, 4, 1, 1, 1, 1
9、, 0, 0, 0, 0, 0, 0, 0, 0;return tabley % 127;*/return n n; 该方法一种有趣变形：设 a、b、c、d 分别对应于谓词第 i 字节非零 ，则 zbytel(x) = a + ab + abc + abcd y = (x y = y | x; / leading 1 on nonzero bytes a = y 31; b = (y 23) c = (y 15) d = (y 7) return a + b + c + d; 另外为了搜索一个字中第一个 4 位、随后 12 位或最后 16 位是否有 0 值，可以 用 0x77FF7FFF 取代
10、该方法中的掩码int zbyter(unsigned int x) / 最右 0 字节 unsigned int y = (x y = (y | x | 0x7F7F7F7F);int n n = ntz(y) 3;/ int n n = (32 - nlz(y return n n; 推广： (1) 搜索等于任意给定值的字节：对变量 x 和给定值进行异或，再搜索 x 中的 0 字节；例如为了搜索 x 中的 ASCII 空格(0x20)，搜索 x0x20202020 中的 0 字节； 同样为了搜索两个字 x 和 y 中相等字节的位置，可以搜索 xy 中的 0 字节 (2) 搜索给定范围内的值(
11、 ) 寻找 0 到 9 之间值得最左侧字节的下标:y = (x y = (y | x | 0x7F7F7F7F); n n = nlz(y) 3;寻找字中第一个大写字母(0x410x5A)：d = (x | 0x80808080) - 0x41414141; d = (x | 0x7F7F7F7F) d);y = (d y = (y | d | 0x7F7F7F7F); n n = nlz(y) 3;6.2 寻找第一个给定长度或更长的 1 位串 int ffstr1(unsigned int x, int n n) int k, p=0;while(x != 0) k = nlz(x);x =
12、 x = n n)return p;x = x 1)s = n n 1;x = x if(k if(k if(k if(k k=31 反转字中的位，例如：rev(0x01234567) = 0xE6A2C480 k=24 反转字中的字节，例如：rev(0x1234567) = 0x67452301 k=16 反转字中左右两个半字，例如：rev(0x1234567) = 0x45670123 k=7 反转每个字节中的位，例如：rev(0x1234567) = 0x80C4A2E67.2 混洗位 abcd efgh ijkl mnop ABCD EFGH IJKL MNOP x=(x x = (x
13、 2) | x) x = (x 4) | x) x = (x 8) | x) 7.3 转置位矩阵 a0 = 0123 b0 = 048c a1 = 4567 = b1 = 159d a2 = 89ab b2 = 26ae a3 = cdef b3 = 37bf 简单方法: b0 = (a0 b1 = (a0 b2 = (a0 b4 = (a0 Ak = Akt;Ak+j = Ak+j (t 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 / clear i
