位运算的一些应用技巧.pdf

位运算： 复习了一下c语言的位运算， （经他人指点）发现位运算如果用的灵活的话，是个很方便的东西。下面简 单的介绍一下吧： 一、按位与 （）； 1、运算规则： 1 0 0；0 1 0 ；0 0 0； 1 1 1； 2、特点： 与0运算结果为0，与1 运算结果保留原样； 3、举例； 3 5： 3： 0 0 0 0 0 0 1 1 5： （）0 0 0 0 0 10 1 0 0 0 0 0 0 0 1 4、用途： ① 将某一位置0，其他位不变。 例如： 将char型变量a的最低位置0； a a 0376； a 1 1 1 1 1 1 10 ② 去指定位。 例如： charc；short int a 取出a的低字节放在c中； c a 0377 a 11111111 ③ 进行“位屏蔽”运算 例子同上； ④ 通过 1 判断某个数的奇偶 （这个要比%2快） 例如： int i ； 若 i 1 0则 i 为 偶数； 若 i 1 1 则 i 为 奇数。 二、按位或 （|） 1、运算规则： 1 |0 1 ； 0 |1 1 ； 1 |1 1 ； 0 |0 0 2、特点： 只要有一个1结果即为 1，否则结果为 0。 3、举例： 3 |5： 3： 0 0 0 0 0 0 1 1 5： （|）0 0 0 0 0 10 1 0 0 0 0 0 1 1 1 4、用途： ① 将某一位置1，其他位不变。 例如：将short int 型变量a 的低字节置 1 a a |oxff a 11111111 三、按位异或 （^） 1、运算规则： 0 ^0 0； 1^ 1 0；0 ^ 1 1； 1^0 1 2、 2、特点： 若对应位相同，则结果为 0； 若对应位不同，则结果为 1。 3、举例： 3 ^ 5： 3： 0 0 0 0 0 0 1 1 5： （^）0 0 0 0 0 10 1 0 0 0 0 0 1 10 4、技巧： a ^a 0；a ^0 a；a ^ 11……11 为翻转 5、用途 ① 使某些特定位翻转。 ② 下一篇博客 （zoj 3432）会给出明确解释。 四、按位取反 （~） 注意：~1 不是 -1 而是 -2； 五、左移运算 ( ) 左移后低位补 0， 高位 舍弃。 六、右移运算 （ ） 右移后 低位舍弃 高位 无符号数 补0 有符号数 补“符号位” 位运算应用口诀 清零取位要用与，某位置一可用或 若要取反和交换，轻轻松松用异或 移位运算 要点 1 它们都是双目运算符，两个运算分量都是整形，结果也是整形。 2 左移：右边空出的位上补0，左边的位将从字头挤掉，其值相当于乘2。 3 右移：右边的位被挤掉。对于左边移出的空位，如果是正数则空位补0，若为负数， 可能补0或补 1，这取决于所用的计算机系统。 4 运算符，右边的位被挤掉，对于左边移出的空位一概补上0。 位运算符的应用 (源操作数s 掩码 mask) (1) 按位与-- 1 清零特定位 (mask中特定位置0，其它位为 1，s smask) 2 取某数中指定位 (mask中特定位置 1，其它位为0，s smask) (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