本文共 4915 字，大约阅读时间需要 16 分钟。
基础一 位运算 位运算的运算分量只能是整型或字符型数据，位运算把运算对象看作是由二进位组成的位串信息，按位完成指定的运算，得到位串信息的结果。 位运算符有： &(按位与)、|(按位或)、^(按位异或)、~ (按位取反)。 其中，按位取反运算符是单目运算符，其余均为双目运算符。 位运算符的优先级从高到低，依次为~、&、^、|， 其中~的结合方向自右至左，且优先级高于算术运算符，其余运算符的结合方向都是自左至右，且优先级低于关系运算符。 (1)按位与运算符(&) 按位与运算将两个运算分量的对应位按位遵照以下规则进行计算： 0 & 0 = 0, 0 & 1 = 0, 1 & 0 = 0, 1 & 1 = 1。 即同为 1 的位，结果为 1，否则结果为 0。 例如，设3的内部表示为 00000011 5的内部表示为 00000101 则3&5的结果为 00000001 按位与运算有两种典型用法，一是取一个位串信息的某几位，如以下代码截取x的最低7位：x & 0177。二是让某变量保留某几位，其余位置0，如以下代码让x只保留最低6位：x = x & 077。以上用法都先要设计好一个常数，该常数只有需要的位是1，不需要的位是0。用它与指定的位串信息按位与。(2)按位或运算符(|) 按位或运算将两个运算分量的对应位按位遵照以下规则进行计算： 0 | 0 = 0, 0 | 1 = 1, 1 | 0 = 1, 1 | 1 = 1 即只要有1个是1的位，结果为1，否则为0。 例如，023 | 035 结果为037。 按位或运算的典型用法是将一个位串信息的某几位置成1。如将要获得最右4为1，其他位与变量j的其他位相同，可用逻辑或运算017|j。若要把这结果赋给变量j，可写成： j = 017|j(3)按位异或运算符(^) 按位异或运算将两个运算分量的对应位按位遵照以下规则进行计算： 0 ^ 0 = 0, 0 ^ 1 = 1, 1 ^ 0 = 1, 1 ^ 1 = 0即相应位的值相同的，结果为 0，不相同的结果为 1。 例如，013^035结果为026。 异或运算的意思是求两个运算分量相应位值是否相异，相异的为1，相同的为0。按位异或运算的典型用法是求一个位串信息的某几位信息的反。如欲求整型变量j的最右4位信息的反，用逻辑异或运算017^j，就能求得j最右4位的信息的反,即原来为1的位，结果是0,原来为0的位，结果是1。 (4)按位取反运算符(~) 按位取反运算是单目运算，用来求一个位串信息按位的反，即哪些为0的位，结果是1，而哪些为1的位，结果是0。例如, ~7的结果为0xfff8。 取反运算常用来生成与系统实现无关的常数。如要将变量x最低6位置成0，其余位不变，可用代码x = x & ~077实现。以上代码与整数x用2个字节还是用4个字节实现无关。 当两个长度不同的数据进行位运算时(例如long型数据与int型数据)，将两个运算分量的右端对齐进行位运算。如果短的数为正数，高位用0补满；如果短的数为负数，高位用1补满。如果短的为无符号整数，则高位总是用0补满。 位运算用来对位串信息进行运算，得到位串信息结果。如以下代码能取下整型变量k的位串信息的最右边为1的信息位：((k-1)^k) & k。移位运算 移位运算用来将整型或字符型数据作为二进位信息串作整体移动。有两个运算符： << (左移) 和 >> (右移)移位运算是双目运算，有两个运算分量,左分量为移位数据对象，右分量的值为移位位数。移位运算将左运算分量视作由二进位组成的位串信息,对其作向左或向右移位，得到新的位串信息。 移位运算符的优先级低于算术运算符，高于关系运算符，它们的结合方向是自左至右。(1)左移运算符(<<) 左移运算将一个位串信息向左移指定的位，右端空出的位用0补充。例如014<<2,结果为060,即48。 左移时，空出的右端用0补充，左端移出的位的信息就被丢弃。在二进制数运算中，在信息没有因移动而丢失的情况下，每左移1位相当于乘2。如4 << 2，结果为16。(2)右移运算符(>>) 右移运算将一个位串信息向右移指定的位，右端移出的位的信息被丢弃。例如12>>2,结果为3。与左移相反，对于小整数，每右移1位，相当于除以2。在右移时，需要注意符号位问题。对无符号数据，右移时，左端空出的位用0补充。对于带符号的数据，如果移位前符号位为0(正数)，则左端也是用0补充；如果移位前符号位为1(负数)，则左端用0或用1补充，取决于计算机系统。对于负数右移，称用0 补充的系统为“逻辑右移”，用1补充的系统为“算术右移”。 基础二 位运算应用口诀清零取反要用与，某位置一可用或若要取反和交换，轻轻松松用异或移位运算要点 1 它们都是双目运算符，两个运算分量都是整形，结果也是整形。 2 " < <" 左移：右边空出的位上补0，左边的位将从字头挤掉，其值相当于乘2。 3 ">>"右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数，可能补0或补1，这取决于所用的计算机系统。 4 ">>>"运算符，右边的位被挤掉，对于左边移出的空位一概补上0。位运算符的应用 (源操作数s 掩码mask)(1)按位与-- & 1 清零特定位 (mask中特定位置0，其它位为1，s=s&mask) 2 取某数中指定位 (mask中特定位置1，其它位为0，s=s&mask)(2)按位或-- ¦ 常用来将源操作数某些位置1，其它位不变。 (mask中特定位置1，其它位为0 s=s ¦mask)(3) 位异或-- ^ 1 使特定位的值取反 (mask中特定位置1，其它位为0 s=s^mask) 2 不引入第三变量，交换两个变量的值 (设 a=a1,b=b1) 目 标 操 作 操作后状态 a=a1^b1 a=a^b a=a1^b1,b=b1 b=a1^b1^b1 b=a^b a=a1^b1,b=a1 a=b1^a1^a1 a=a^b a=b1,b=a1二进制补码运算公式： -x = ~x + 1 = ~(x-1) ~x = -x-1 -(~x) = x+1 ~(-x) = x-1 x+y = x - ~y - 1 = (x ¦y)+(x&y) x-y = x + ~y + 1 = (x ¦~y)-(~x&y) x^y = (x ¦y)-(x&y) x ¦y = (x&~y)+y x&y = (~x ¦y)-~x x==y:(x-y ¦y-x) x!=y:x-y ¦y-x x < y:(x-y)^((x^y)&((x-y)^x)) x <=y:(x ¦~y)&((x^y) ¦~(y-x)) x < y:(~x&y) ¦((~x ¦y)&(x-y))//无符号x,y比较 x <=y:(~x ¦y)&((x^y) ¦~(y-x))//无符号x,y比较 应用举例 (1)判断int型变量a是奇数还是偶数 a&1== 0 偶数 a&1== 1 奇数(2)取int型变量a的第k位 (k=0,1,2……sizeof(int))，即a>>k&1(3)将int型变量a的第k位清0,即a=a&~(1 < <k)(4)将int型变量a的第k位置1,即a=a ¦(1 < <k)(5)int型变量循环左移k次,即a=a < <k ¦a>>16-k (设sizeof(int)=16)(6)int型变量a循环右移k次,即a=a>>k ¦a < <16-k (设sizeof(int)=16)(7)整数的平均值对于两个整数x,y，如果用 (x+y)/2 求平均值，会产生溢出，因为 x+y 可能会大于INT_MAX，但是我们知道它们的平均值是肯定不会溢出的，我们用如下算法： int average(int x, int y) //返回X,Y 的平均值 { return (x&y)+((x^y)>>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 (x^y)-y ; //or: (x+y)^y }(11)取模运算转化成位运算 (在不产生溢出的情况下) a % (2^n) 等价于 a & (2^n - 1)(12)乘法运算转化成位运算 (在不产生溢出的情况下) a * (2^n) 等价于 a < < n(13)除法运算转化成位运算 (在不产生溢出的情况下) a / (2^n) 等价于 a>> n 例: 12/8 == 12>>3(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 < < 1在最后加一个1 ¦ (101101->1011011) ¦ x < < 1+1把最后一位变成1 ¦ (101100->101101) ¦ x ¦ 1把最后一位变成0 ¦ (101101->101100) ¦ x ¦ 1-1最后一位取反 ¦ (101101->101100) ¦ x ^ 1把右数第k位变成1 ¦ (101001->101101,k=3) ¦ x ¦ (1 < < (k-1))把右数第k位变成0 ¦ (101101->101001,k=3) ¦ x & ~ (1 < < (k-1))右数第k位取反 ¦ (101001->101101,k=3) ¦ x ^ (1 < < (k-1))取末三位 ¦ (1101101->101) ¦ x & 7取末k位 ¦ (1101101->1101,k=5) ¦ x & ((1 < < k)-1)取右数第k位 ¦ (1101101->1,k=4) ¦ x >> (k-1) & 1把末k位变成1 ¦ (101001->101111,k=4) ¦ x ¦ (1 < < k-1)末k位取反 ¦ (101001->100110,k=4) ¦ x ^ (1 < < k-1)把右边连续的1变成0 ¦ (100101111->100100000) ¦ x & (x+1)把右起第一个0变成1 ¦ (100101111->100111111) ¦ 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位（低）间共有多少个1转载地址：http://efmbi.baihongyu.com/