全国计算机等级考试 位运算.pdf

位 运 算位 运 算 2 26 位运算概述 C语言通过位运算的操作 可以直接对计算机硬件和物理地址访问 从而 应用于系统软件 位运算的作用是 按照二进制位对运算对象 仅是int char及其变体类 型的变量 进行操作 优先级 按位取反运算高于移位运算 它们又高于关系运算 其余运算 符低于关系运算符 4按位异或 1按位取反 2左移 右移 5按位或 3按位与 printf d a getch 025是个八进制数字 计算 025 0000000000010101 025 1111111111101010 负数 结果 025 22 4 26 按位与按位与 printf d a printf d a b 计算 025 0000000000010101 y x 0 x0f printf x y 258相同为0 例如 int a 025 b 0 x32 printf d a b 计算 0258 0000000000010101 0 x3216 0000000000110010 0000000000100111 结果 3910 1 1 0 0 0 0 1 0 1 0 1 1 11 26 按位异或的特性按位异或的特性 1 与二进制1异或 具有翻转性翻转性 0 1 1 1 1 0 2 与二进制0异或 具有保持性保持性 0 0 0 1 0 1 12 26 按位异或的特性按位异或的特性 3 与同一个二进制数连续两次异或后恢 复原值不变 具有恢复性恢复性 即 a b b a 1011 1001 0010 1001 1011 4 异或运算具有交换性交换性 即 a b b a 13 26 按位异或按位异或 的应用的应用 特定位翻转0111 1010 例如 x 0 x0f实现低4位的翻转 0000 1111 0111 0101 交换算法交换算法 交换两个整数的值时可以不用第三个参数 交换两个整数的值时可以不用第三个参数 a a b b a b 相当于相当于a b b a a a b 相当于相当于a a b b a a b 例如 对于 a 11 b 9 交换结果 a 9 b 13 a b1011 1001 0010 a a b0010 1001 1011 b 11 a b1011 0010 1001 a 9 14 26 main int a 11 b 9 a a b b a b a a b printf d d a b getch 或者写成 或者写成 main int a 11 b 9 a b a b printf d d a b getch 15 26 三种交换算法的总结三种交换算法的总结 优点 速度快 不会数值溢出 缺点 只能用于整型量交换 缺点 只能用于整型量交换 a a b b a b a a b 或 或 a b a b 优点 不增加变量 缺点 可能数值溢出 不能用 于非数值交换 a a b b a b a a b 优点 不会溢出 可用于多种 数据类型 指针 字符串等 缺点 多用一个变量 t a a b b t 16 26 加密解密加密解密 include main char a int b 0 x32 while a getchar n a a b putch a getch 输入 输入 DWm E 17 26 移位运算符移位运算符 双目运算双目运算 左移位左移位 规则 高位不论0或1都丢弃 低位空位以0填充 特征 高位丢弃的没有1时 左移i位 变成2i倍 例如 int a 50 0 x32 printf d a 3 运算 0 x32 00000000 00110010 规则 规则 低位不论0或1都丢弃 高位空位对于有符号的数填 充符号位 正数填正数填0 负数填 负数填1 对于无符号的数则填0 特征 特征 低位丢弃的没有1时右移i位 变成2 i倍 即缩小了2i倍 例如 int a 50 b 53 0 x32和0 x35 printf d a 1 printf d b 2 0000000000110010 0000000000011001 0 所以a 1结果为25 50 2 25 00000000 00110101 00000000 0000110101 所以b 2结果为13 53 4 13 19 26 注意点 位运算进行后 如果没有发生赋值动作 则 变量的值不变 例如 int a 0 x32 printf d n a 2 printf d n a a的值不变 想一下 想一下 1 1 等于什么 等于什么 20 26 1 1 等于什么 等于什么 由于 1是有符数 在内存中以补码表示 即 1111 1111 1111 1111 按右移规则 低位丢弃 高位填符号位 则 1 1 仍为 1111 1111 1111 1111 即 即 1右移任何位均为右移任何位均为 1不变 不变 21 26 位运算应用举例位运算应用举例 任意从键盘上输入字母 将大写字母变成小写字母 小写字母变成大写字母 任意从键盘上输入字母 将大写字母变成小写字母 小写字母变成大写字母 解 A 65 10000012 a 97 11000012 注意 65和97的ASCII码仅第6位不同而已 a A 32 32 1000002 大写字母变成小写字母就是大写字母的ASCII码减32 即25位翻转即可 由于特定位翻转可用与二进制由于特定位翻转可用与二进制1异或 所以与异或 所以与25异或即可 异或即可 算法即为 算法即为 ch 040 或或 ch 0 x20 22 26 main char x do x getch putch x putch x 040 while x 13 回车的回车的ASCII码码 由于由于 32 1000002 408 所以用异或所以用异或040可实现大小写字母转换可实现大小写字母转换 23 26 main int a 5 b 39 max max a b max a b 上句与本句相同上句与本句相同 printf max d d d a b max getch 算法设计 算法设计 max a b 1 31 利用利用 printf Input a integer scanf d for i 1 i 1 x 2 getch 将键盘输入的一个整数以将键盘输入的一个整数以8位二进制逆序形式输出位二进制逆序形式输出 25 26 算法分析算法分析 对于无符整数对于无符整数x 将将x同同27做做 将将x左移一位形成新的左移一位形成新的x x x 1 将将x重复同重复同27的的 再将再将x左移一位形成新的左移一位形成新的x x x 1 注意注意 这里这里x是无符数是无符数 所以右移时高位是补所以右移时高位是补0的的 C语言中整数在内存中的存贮情况 即 语言中整数在内存中的存贮情况 即 将键盘上输入的一个整数以将键盘上输入的一个整数以8位二进制形式输出 位二进制形式输出 26 26 main unsigned int x t i printf Input a integer scanf d for i 1 i 7 output x s lowest bit x x 1 getch 27 26 将键盘上输入的任意一个整数转成八进制形式输出 采用位运算进行 不使用系统提供的 将键盘上输入的任意一个整数转成八进制形式输出 采用位运算进行 不使用系统提供的 o输出方式 输出方式 x与与15位的位的1110 0 与运算与运算t x 重复与重复与15位的位的1110 0与运算与运算 在在t中获得获得中获得获得x的第的第4 5 6位位 又将又将t 右移右移12位至低位至低3位再输出位再输出 再将再将x左移左移3位位x x 3 注意注意 这里这里x是无符数是无符数 所以右移时高位是补所以右移时高位是补0的的 main unsigned int x t i clrscr printf Input a integer scanf d for i 1 i 12 output x s lowest bit x x 3 getch 28 26 将键盘上输入的任意一个整数转成十六进制形式输出 采用位运算进行 不使用系统提供的 将键盘上输入的任意一个整数转成十六进制形式输出 采用位运算进行 不使用系统提供的 x输出方式 输出方式 x与与16位的位的11110 0 与运算与运算t x 重复与重复与16位的位的11110 0与运算与运算 在在t中获得获得中获得获得x的第的第5 6 7 8位位 又 将 又 将t右移右移12位