计算二进制数中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位和后缀0的掩码(0101 1000-0000 1111) x(x-1) (表示异或)e.向右传播最

2、右侧的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

3、 t 2)/s xr=11111 0000, t=00000 0111 y - r|t y=10000 0111寻找一个和给定非负整数有相同数目的1位的下一个大数: x&(x-1) + 1 2.4 绝对值函数先计算y 31，然后使用 abs: (xy)-y or (x+y)y or x-(x1 & y) nabs: y-(xy) or (y-x)y or (x1 & y)-x2.7 符号函数sign(x) = -1(x0), 使用比较谓词指令(x0)-(x=0)-(x31)|(-x31)2.9 符号传递ISIGN(x,y) = abs(x)(y=0), -abs(x) (y31) = (abs

4、(x)+t)t2.14 循环移位(x为无符号整数）左循环移位n个位：y=(x(32-n)右循环移位n个位：y=(xn)|(x(0x20 - shift) | (val (0x40 - shift) | (val k)&m; t2 = t1 k; val = xt1t2 |-| 上述基于异或的交换方法，当m为0时退化为无操作，当m为全1时则是交换x和y的值第三章 2的幂边界（非负整数） 3.1 上、下舍入到已知2的幂的倍数假设舍入的因子以调整量的log2的形式给出，k=log2(调整量) (例如k=3，调整量=8)下舍入到已知2的幂的倍数, x&(-1)k)3)3上舍入到已知2的幂的倍数, t=

5、(1k)-1; (x+t)&t 或者 t=(-1) 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

6、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

7、 - x/2 - x/4 -.-x/231 (x/231 = 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

8、& 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

9、 = 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 table256

10、= 0, 1, 1,., 7, 7, 8;return tablex & 0xFF + table(x 8) & 0xFF +table(x 16) & 0xFF + table(x 24);5.2 字的奇偶性1.计算1位的个数，然后由结果的最右侧位决定2.由r i) (0=i 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 /

11、 将各个四位数加到一起并把和放入到高阶十六进制位的数字中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 4; if(y != 0) n -= 4; x = y; y = x 2; if(y !

12、= 0) n -= 2; x = y; n += 16; x = 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 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 = 0x3FFFFFF

13、F) 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; 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) =

14、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 =

15、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字节变

16、为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个位上 / 0x8

17、0808080%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分别对应于谓词“第i字节非零”，则zbytel(x) = a + ab + abc + abcdy = (x & 0x7F7F7F7F) + 0x7F7F7F7F;y = y | x; / leading 1 on non

18、zero 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; r

19、eturn n;推广：(1) 搜索等于任意给定值的字节： 对变量x和给定值进行异或，再搜索x中的0字节；例如为了搜索x中的ASCII空格(0x20)，搜索x0x20202020中的0字节； 同样为了搜索两个字x和y中相等字节的位置，可以搜索xy中的0字节(2) 搜索给定范围内的值( )寻找0到9之间值得最左侧字节的下标:y = (x & 0x7F7F7F7F) + 0x76767676; y = (y | x | 0x7F7F7F7F); n = nlz(y) 3;寻找字中第一个大写字母(0x410x5A)：d = (x | 0x80808080) - 0x41414141; d = (x |

20、 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 = n) return p; x = x 1) s = n 1; x = x & (x =8的连续1位串 x = x&(x 1); x = x&(x 2); x = x&(x 4); / 顺序可以颠倒 n = nlz(x)

21、;第7章 位与字节的重排列7.1 位与字节的反转if(k & 1) x = (x & 0x55555555) 1;if(k & 2) x = (x & 0x33333333) 2;if(k & 4) x = (x & 0x0F0F0F0F) 4;if(k & 8) x = (x & 0x00FF00FF) 8;if(k & 16)x = (x & 0x0000FFFF) 16;k=31反转字中的位，例如：rev(0x01234567) = 0xE6A2C480k=24反转字中的字节，例如：rev(0x1234567) = 0x67452301k=16反转字中左右两个半字，例如：rev(0x12

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

23、2) & 0x0C0C0C0C | x&0xC3C3C3C3abAB cdCD efEF ghGH ijIJ klKL mnMN opOP x=(x&0x22222222) 1) & 0x22222222 | x&0x99999999aAbB cCdD eEfF gGhH iIjJ kKlL mMnN oOpP 外混洗结果在上面序列前面加上x= (x16) | (x16)可得到AaBb CcDd EeFf GgHh IiJj KkLl MmNn OoPp 内混洗结果以相反顺序可以实现操作的逆顺序 另外针对字左半部所有位都为0的情况，可以通过x = (x & 0xFF00) 8) | (x &

24、0x00FF);x = (x 4) | x) & 0x0F0F0F0F;x = (x 2) | x) & 0x33333333;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

25、 & 8) 2 | (a3 & 8) 3;b1 = (a0 & 4) 1 | (a3 & 4) 2;b2 = (a0 & 2) 2 | (a1 & 2) 1;b4 = (a0 & 1) 3 | (a1 & 1) 2 | (a2 & 1) 1 | (a3 & 1);一种好的编码：m = m(m1, m=m(mj) for(k=0; k j) & m; Ak = Akt; Ak+j = Ak+j (t j); 7.4 压缩或广义提取例：掩码：0000 1111 0011 0011 1010 1010 0101 0101 字X： abcd efgh ijkl mnop qrst uvwx yzAB

26、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) 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;

27、 / 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 (1 (1 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

28、 x & 0x0000003F; / 6我们以0000 0000 0000 0000 0000 0000 1011 0101为例第一行中，x1是右移一位，(x1) 为 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) & 0x55

29、555555) 则是 用原数据减去原数据的偶数位。结果是 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位