ACM入门之三-位运算PPT课件.ppt

ACM程序设计 入门之三 位运算 1 2 为什么要加强程序设计能力 Highthoughtsmusthavehighlanguage Aristophane Greek Comicdramatist 450BC 388BC 2 3 为什么要加强程序设计能力 Programming之于计算机专业学生 Gun之于士兵对于非计算机专业学生 也是攻敌利器 是新时代的发展必然趋势 3 4 为什么要加强程序设计能力 计算机专业学生未来可能人生规划 结论 必须具有较高的程序设计能力 除非你放弃专业 一般 IT公司一般人才 4 目录 2 项目经理 管理职位 4 软件售前工程师 产品经理 1 软件架构师 3 5 资深软件工程师 6 系统集成工程师 高级软件工程师 5 目录 软件测试工程师 8 10 数据库工程师 后台设计和实现 9 7 QA质量保证工程师 12 软件实施工程师 11 软件工程师 程序员 前台设计和实现 界面设计 软件销售 6 7 典型案例 RickRashid博士微软公司主管研究的高级副总裁美国国家工程院院士 CMU教授 Mach操作系统项目的负责人 参与开发最早的计算机网络游戏之一AltoTrek据称 每年亲自编写近1 5万行代码 经典语录编程 艺术与科学 RickRashid 7 位运算 最显专业的程序设计 8 8 9 位运算 有时我们需要对某个整数类型变量中的某一位 bit 进行操作 比如 判断某一位是否为1 或只改变其中某一位 而保持其他位都不变 C C 语言提供了 位运算 的操作 能够做到类似的操作 C C 语言提供了六种位运算符来进行位运算操作 按位与 按位或 按位异或 取反 右移 9 10 按位与 按位与运算符 是双目运算符功能 将参与运算的两操作数各对应的二进制位进行与操作 只有对应的两个二进位均为1时 结果的对应二进制位才为1 否则为0 a b a b不需要是二进制数 是整数变量即可 10 11 按位与 例如 表达式 21 18 的计算结果是16 即二进制数10000 因为 21用二进制表示就是 0000000000000000000000000001010118用二进制表示就是 00000000000000000000000000010010二者按位与所得结果是 00000000000000000000000000010000 11 12 按位与 按位与运算通常用来将某变量中的某些位清0或保留某些位不变 例如 如果需要将int型变量n的低8位全置成0 而其余位不变 则可以执行 n n如何判断一个int型变量n的第7位 从右往左 从0开始数 是否是1 只需看表达式 n 0 x80 的值是否等于0 x80即可 12 13 按位或 按位或运算符 是双目运算符 功能 将参与运算的两操作数各对应的二进制位进行或操作 只有对应的两个二进位都为0时 结果的对应二进制位才是0 否则为1 例如 表达式 21 18 的值是23 即二进制数10111 按位或运算通常用来将某变量中的某些位置1或保留某些位不变 例如 如果需要将int型变量n的低8位全置成1 而其余位不变 则可以执行 n 0 xff 13 14 按位异或 按位异或运算符 是双目运算符 功能 将参与运算的两操作数各对应的二进制位进行异或操作 即只有对应的两个二进位不相同时 结果的对应二进制位才是1 否则为0 例如 表达式 21 18 的值是7 即二进制数111 异或运算的特点如果a b c 那么就有c b a以及c a b 此规律可以用来进行最简单的加密和解密 14 15 按位非 按位非运算符 是单目运算符 其功能是将操作数中的二进制位0变成1 1变成0 例如 表达式 21 的值是无符号整型数0 xffffffea 而下面的语句 printf d u x 21 21 21 输出结果就是 22 4294967274 ffffffea 15 16 左移运算符 左移运算符 是双目运算符 其功能是将左操作数的各二进位全部左移若干位后得到的值 右操作数指明了要左移的位数 左移时 高位丢弃 左边低位补0 左移运算符不会改变左操作数的值 16 17 左移运算符 例如 常数9有32位 其二进制表示是 00000000000000000000000000001001因此 表达式 9 4 的值 就是将上面的二进制数左移4位 得 00000000000000000000000010010000即为十进制的144 实际上 左移1位 就等于是乘以2 左移n位 就等于是乘以2n 而左移操作比乘法操作快得多 特别注意 有符号数的左移溢出情况 17 includemain intn1 15 shortn2 15 unsignedshortn3 15 unsignedcharc 15 n1 15 n2 15 n3 15 c 6 printf n1 x n2 d n3 d c x c 4 d n1 n2 n3 c c 4 上面程序的输出结果是 n1 78000 n2 32768 n3 32768 c c0 c 4 3072 左移运算符实例 18 19 右移运算符 右移运算符 是双目运算符 其计算结果是把 的左操作数的各二进位全部右移若干位后得到的值 要移动的位数就是 的右操作数 移出最右边的位就被丢弃 对于有符号数 如long int short char类型变量 在右移时 符号位 即最高位 将一起移动 并且大多数C C 编译器规定 如果原符号位为1 则右移时右边高位就补充1 原符号位为0 则右移时高位就补充0 19 20 右移运算符 对于无符号数 如unsignedlong unsignedint unsignedshort unsignedchar类型的变量 则右移时 高位总是补0 右移运算符不会改变左操作数的值 实际上 右移n位 就相当于左操作数除以2n 并且将结果往小里取整 20 includemain intn1 15 shortn2 15 unsignedshortn3 0 xffe0 unsignedcharc 15 n1 n1 2 n2 3 n3 4 c 3 printf n1 x n2 d n3 x c x n1 n2 n3 c 上面的程序输出结果是 n1 3 n2 2 n3 ffe c 1 右移运算符实例 21 22 思考题 位运算的妙用 有两个int型的变量a和n 0 n 31 要求写一个表达式 使该表达式的值和a的第n位相同 例如 a 12345 n 3 a的第n位为 3 答案 a 1 n 22 位运算解决的常见问题 1 判断二进制下第i位是否是12 把二进制下第i位变为1or03 求一个数字二进制下有多少个1 23 异或运算的妙用 xor运算通常用于对二进制的特定一位进行取反操作 因为异或可以这样定义 0和1异或0都不变 异或1则取反 xor运算的逆运算是它本身 也就是说两次异或同一个数最后结果不变 即 axorb xorb a xor运算可以用于简单的加密 比如我想对我MM说1314520 但怕别人知道 于是双方约定拿我的生日19880516作为密钥 1314520 xor19880516 20665500 我就把20665500告诉MM MM再次计算20665500 xor19880516的值 得到1314520 于是她就明白了我的意思 24 HDU3782xxx定律 Output对于每组测试用例请输出一个数 表示需要经过的步数 每组输出占一行 25 25 HDU3782xxx定律 数据样例 SampleInput3 5 8 4 2 1 10SampleOutput50 26 ProblemDescription对于一个数n 如果是偶数 就把n砍掉一半 如果是奇数 把n变成3 n 1后砍掉一半 直到该数变为1为止 26 标准程序 include include includeintmain intn time while scanf d 27 27 求数组中出现次数超过一半的元素 思路1 对于每一个数字 枚举数组中所有的数字 统计有多少个数字跟它是一样的 如果超过了一半 就直接break并输出它 这样子做 时间复杂度是O N N 空间复杂度是O N 并不是一个非常好的思路 28 for inti 1 in 2 cout arr i endl break 求数组中出现次数超过一半的元素 循环法 29 求数组中出现次数超过一半的元素 思路2 利用C 中的map 快速的统计每一个数字出现的次数 每当读入一个数字的时候 map arr i 直接统计出每一个数字出现的次数 这个做法 时间复杂度是O N log N 这里log N 是每次用map查找一个数字所用到的时间 空间复杂度也是O N 但是比思路1略大一点 30 mapvis for inti 1 in 2 cout arr i endl break 求数组中出现次数超过一半的元素 Map法 31 求数组中出现次数超过一半的元素 思路3 利用中位数的性质 一个数字出现次数超过了一半 那么他们的中位数必然就是这个数字 因此可以利用中位数来求 最简单的办法就是 排序以后 直接输出最中间的那个数字 需要注意的是 中位数并不是arr n 2 而是arr n 1 2 具体证明过程略 排序的时间复杂度是O nlogn 空间复杂度是O n 32 sort arr 1 arr n 1 cout arr n 1 2 求数组中出现次数超过一半的元素 中位数法 33 求数组中出现次数超过一半的元素 按二进制下的每一位来统计 假设输入一共有5个数字 分别是1 2 1 1 3 那么他们用二进制表示分别是 01 10 01 01 11 统计一下每一个二进制位上1出现的次数 在二进制下第一位 1出现了4次 二进制下第二位 1出现了2次 这一位上1的次数出现次数没有 N 2 说明答案这一位上肯定是0 反之 答案这一位上肯定是1 这样做 时间复杂度是O N 32 空间复杂度却可以降低到O 33 O 1 因为数组的每一位不再需要保存了 直接读入一个处理一个就可以 34 intnum 33 for inti 1 i0 num k 位运算的操作 对这两个数字做与操作 例如 arr i 是1101 now是8也就是1000 那么他俩与之后的结果就是1000 如果 arr i 是1101 now是2也就是0010 那么他俩与之后的结果就是0000 换句话说 如果二进制下对应那一位是0 与出来的结果就是0 否则则是一个大于0的数字 intnow 1 ans 0 for intk 0 kn 2 ans now cout ans endl 求数组中出现次数超过一半的元素 二进制法 35 求数组中出现次数超过一半的元素 打架法 来看这样一个例子 51541131211一共11个数字 其中1一共出现了6次 那么如何快速的找到这个6呢 我们来考虑这样一个现实生活中的例子 有一群人在打群架 他们每个人有一个编号 代表自己所处的势力 现在这一群人按照顺序依次往广场中央走 如果广场内现在有和自己不是一个势力的人 那么他就和其中一个同归于尽 问 最后哪一个势力的人会获胜 我们按照这个意思 再来看一下刚才这个例子 36 求数组中出现次数超过一半的元素 势力法 1 势力5的一个人走进广场中央 现在广场中央有一个人 势力是52 势力1的一个人走进广场中央 他发现广场中央有一个势力是5的人 于是同归于尽 现在广场上没有人3 势力5的一个人走进广场中央 现在广场中央有一个人 势力是54 势力4的一个人走进广场中央 他发现广场中央有一个势力是5的人 于是同归于尽 现在广场上没有人5 势力1的一个人走进广场中央 现在广场有一个人 势力是16 势力1的一个人走进广场中央 现在广场有两个人 势力是2 37 求数组中出现次数超过一半的元素 势力法 可以发现 每一次火拼 势力最大 也就是出现次数最多的那个数字 的那个每次最多只会死亡一个 而火拼最多会进行N 2次 出现频率最高的那个数字最多只会损失N 2个 而题上告诉我们出现次