《位运算技巧总结.docx》由会员分享，可在线阅读，更多相关《位运算技巧总结.docx（10页珍藏版）》请在金锄头文库上搜索。
1、位运算应用口诀清零取反要用与，某位置一可用或(1&0=0,1|1=1、01=1)若要取反和交换，轻轻松松用异或 (与1异或相当于取反，与0异或相当于不变。11=0、01=1，10=1、00=0)移位运算要点 1 它们都是双目运算符，两个运算分量都是整形，结果也是整形。2 右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统。4 运算符，右边的位被挤掉，对于左边移出的空位一概补上0。位运算符的应用 (源操作数s 掩码mask)(1) 按位与- &1 清零特定位 (mask中特定位置0，其它位为1，s=s&mask)2 取某数中指定位
2、(mask中特定位置1，其它位为0，s=s&mask)(2) 按位或- |常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0 s=s |mask)(3) 位异或- 1 使特定位的值取反 (mask中特定位置1，其它位为0 s=smask)2 不引入第三变量，交换两个变量的值 (设 a=a1,b=b1)目 标 操 作 操作后状态a=a1b1 a=ab a=a1b1,b=b1b=a1b1b1 b=ab a=a1b1,b=a1a=b1a1a1 a=ab a=b1,b=a1二进制补码运算公式：-x = x + 1 = (x-1)x = -x-1-(x) = x+1(-x) =
3、 x-1x+y = x - y - 1 = (x |y)+(x&y)x-y = x + y + 1 = (x |y)-(x&y)xy = (x |y)-(x&y)x |y = (x&y)+yx&y = (x |y)-xx=y: (x-y |y-x)x!=y: x-y |y-xx y: (x-y)(xy)&(x-y)x)x =y: (x |y)&(xy) |(y-x)x y: (x&y) |(x |y)&(x-y)/无符号x,y比较x k&1(3) 将int型变量a的第k位清0，即a=a&(1 k)(4) 将int型变量a的第k位置1， 即a=a |(1 k)(5) int型变量循环左移k次，即
4、a=a 16-k (设sizeof(int)=16)(6) int型变量a循环右移k次，即a=ak |a 1);(8)判断一个整数是不是2的幂,对于一个数 x = 0，判断他是不是2的幂boolean power2(int x)return (x&(x-1)=0)&(x!=0)；(9)不用temp交换两个整数void swap(int x , int y)x = y;y = x;x = y;(10)计算绝对值int abs( int x )int y ;y = x 31 ;return (xy)-y ; /or: (x+y)y(11)取模运算转化成位运算 (在不产生溢出的情况下)a % (2n
5、) 等价于 a & (2n - 1)(12)乘法运算转化成位运算 (在不产生溢出的情况下)a * (2n) 等价于 a n例: 12/8 = 123(14) a % 2 等价于 a & 1 (15) if (x = a) x= b; else x= a; 等价于 x= a b x;(16) x 的 相反数 表示为 (x+1)实例功能 | 示例 | 位运算-+-+-去掉最后一位 | (101101-10110) | x 1在最后加一个0 | (101101-1011010) | x 1011011) | x 101101) | x | 1把最后一位变成0 | (101101-101100) |
6、x | 1-1最后一位取反 | (101101-101100) | x 1把右数第k位变成1 | (101001-101101,k=3) | x | (1 101001,k=3) | x & (1 101101,k=3) | x (1 101) | x & 7取末k位 | (1101101-1101,k=5) | x & (1 1,k=4) | x (k-1) & 1把末k位变成1 | (101001-101111,k=4) | x | (1 100110,k=4) | x (1 100100000) | x & (x+1)把右起第一个0变成1 | (100101111-100111111)
7、| x | (x+1)把右边连续的0变成1 | (11011000-11011111) | x | (x-1)取右边连续的1 | (100101111-1111) | (x (x+1) 1去掉右起第一个1的左边 | (100101000-1000) | x & (x (x-1)判断奇数 (x&1)=1判断偶数 (x&1)=0 例如求从x位（高）到y位（低）间共有多少个1public static int FindChessNum(int x, int y, ushort k)int re = 0;for (int i = y; i (i - 1) & 1);return re; 1. 位运算的
8、简单应用表达式位运算等价x+y(x|y)+(x&y)x-y(x|y)-(x&y)xy(x|y)-(x&y)x|y(x&y)+yx&y(x|y)-xx=y(x-y|y-x)x!=yx-y|y-xx y(x-y)(xy)&(x-y)x)x y(x&y)|(x|y)&(x-y) /无符号x,y比较x 0000 1010(二进制) 加1- 0000 1011(二进制)同样可以这样的将11变成-110000 1011(二进制) 取反- 0000 1010(二进制) 加1- 1111 0101(二进制)可以得到如下代码：1int changeSign(int n) 2return n + 1;35. 取绝
9、对值对于任何数，与0异或都会保持不变，与-1即0xFFFFFFFF异或就相当于取反,因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1）也可以得到绝对值因此可以得 到如下代码：1int abs(int n) 2return (n (n 31) - (n 31);36. 高低位互换给出一个32位的无符号整数。称这个二进制数的前16位为“高位”，后16位为“低位”。现在写一程序将它的高低位交换。例如，数0x1234ABCD用二进制表示为：0001 0010 0011 0100 1010 1011 1100 1101将它的高低位进行交换，我们得到了一个新的二进制数：1010 1011 1100 1101 0001 0010 0011 0100它即是0xABCD1234。这个问题用位操作解决起来非常方便，设x=0x1234ABCD由于x为无符号数，右移时会执行逻辑右移即高位补0，因此x右移16位将得到0000 0000 0000 0000 0001 0010 0011 0100。而x左移8位将得到0000 0000 0000 0000 1010 1011
