位操作技巧实例大全.docx

位操作技巧实例大全检测一个无符号数是不为2^n-1(^为幂)： x(x+1)将最右侧0位改为1位： x | (x+1)二进制补码运算公式：-x = ~x + 1 = ~(x-1)~x = -x-1?-(~x) = x+1~(-x) = x-1x+y = x - ~y - 1 = (x|y)+(xy)?x-y = x + ~y + 1 = (x|~y)-(~xy)?x^y = (x|y)-(xy)x|y = (x~y)+yxy = (~x|y)-~xx==y:??? ~(x-y|y-x)x!=y:??? x-y|y-xx y:??? (x-y)^((x^y)((x-y)^x))x=y:??? (x|~y)((x^y)|~(y-x))x y:??? (~xy)|((~x|y)(x-y))//无符号x,y比较x=y:??? (~x|y)((x^y)|~(y-x))//无符号x,y比较?使用位运算的无分支代码：计算绝对值int abs( int x )?{??? int y ;??? y = x 31 ;??? return (x^y)-y ;//or: (x+y)^y}符号函数：sign(x) = -1, x0; 0, x == 0 ; 1, x 0int sign(int x){??? return (x31) | (unsigned(-x))31 ;//x=-2^31时失败(^为幂)}三值比较：cmp(x,y) = -1, xy; 0, x==y; 1, x yint cmp( int x, int y ){??? return (xy)-(x-y) ;}doz=x-y, x=y; 0, xyint doz(int x, int y ){??? int d ;??? d = x-y ;??? return d ((~(d^((x^y)(d^x))))31) ;}int max(int x, int y )?{??? int m ;??? m = (x-y)31 ;???? return y m | x ~m ;}不使用第三方交换x,y:1.x ^= y ; y ^= x ; x ^= y ;2.x = x+y ; y = x-y ; x = x-y ;3.x = x-y ; y = y+x ; x = y-x ;4.x = y-x ; x = y-x ; x = x+y ;双值交换:x = a, x==b; b, x==a//常规编码为x = x==a ? b :a ;1.x = a+b-x ;2.x = a^b^x ;下舍入到2的k次方的倍数:1.x ((-1)k)2.(((unsigned)x)k)k上舍入：1. t = (1k)-1 ; x = (x+t)~t ;2.t = (-1)k ; x = (x-t-1)t ;位计数,统计1位的数量：1.int pop(unsigned x){??? x = x-((x1)0 ;??? x = (x0 + ((x2) 0) ;??? x = (x+(x4)) 0x0f0f0f0f ;??? x = x + (x8) ;??? x = x + (x16) ;??? return x 0x0000003f ;}2.int pop(unsigned x) {??? static char table[256] = { 0,1,1,2, 1,2,2,3, ...., 6,7,7,8 } ;??? return table[x0xff]+table[(x8)0xff]+table[(x16)0xff]+table[(x24)] ;}奇偶性计算:x = x ^ ( x1 ) ;x = x ^ ( x2 ) ;x = x ^ ( x4 ) ;x = x ^ ( x8 ) ;x = x ^ ( x16 ) ;结果中位于x最低位，对无符号x,结果的第i位是原数第i位到最左侧位的奇偶性位反转：unsigned rev(unsigned x){??? x = (x 0 1 | (x1) 0;??? x = (x 0 2 | (x2) 0;??? x = (x 0x0f0f0f0f) 4 | (x4) 0x0f0f0f0f ;??? x = (x24) | ((x0xff00)8) | ((x8) 0xff00) | (x24) ;??? return x ;}递增位反转后的数：unsigned inc_r(unsigned x){??? unsigned m = 0;??? x ^= m ;??? if(