《ACM入门之三-位运算课件》由会员分享，可在线阅读，更多相关《ACM入门之三-位运算课件（39页珍藏版）》请在金锄头文库上搜索。
1、ACM程序设计入门之三-位运算2为什么要加强程序设计能力？oHighthoughtsmusthavehighlanguage.Aristophane(Greek, Comic dramatist)450 BC - 388 BC3为什么要加强程序设计能力？oProgramming之于计算机专业学生Gun之于士兵o对于非计算机专业学生也是攻敌利器，是新时代的发展必然趋势4为什么要加强程序设计能力？o计算机专业学生未来可能人生规划国内就业机会国内就业机会= =不好不好= =好好出国深造的积极性出国深造的积极性出国出国留学留学在国内在国内读研读研= =高高= =差差个人个人ITIT能力能力ITIT公司
2、公司核心人才核心人才在家在家吃父母吃父母= =强强= =差差个人研究能力个人研究能力顺利毕业顺利毕业高级研究员高级研究员拿不到拿不到学位学位= =强强= =差差结论：必须具有较高的程序设计能力！除非你放弃专业结论：必须具有较高的程序设计能力！除非你放弃专业=一般一般IT公司公司一般人才一般人才目录 2项目经理项目经理项目经理项目经理 （管理职位）（管理职位）（管理职位）（管理职位）4软件售前工程师，产品经理软件售前工程师，产品经理软件售前工程师，产品经理软件售前工程师，产品经理1软件架构师软件架构师软件架构师软件架构师35资深软件工程师资深软件工程师资深软件工程师资深软件工程师6系统集成工程师
3、系统集成工程师系统集成工程师系统集成工程师高级软件工程师高级软件工程师高级软件工程师高级软件工程师目录软件测试工程师软件测试工程师软件测试工程师软件测试工程师810数据库工程师（后台设计和实现）数据库工程师（后台设计和实现）数据库工程师（后台设计和实现）数据库工程师（后台设计和实现）97QAQA 质量保证工程师质量保证工程师质量保证工程师质量保证工程师12软件实施工程师软件实施工程师软件实施工程师软件实施工程师11软件工程师软件工程师软件工程师软件工程师/ /程序员（前台设计和实现，界面设计）程序员（前台设计和实现，界面设计）程序员（前台设计和实现，界面设计）程序员（前台设计和实现，界面设计）
4、 软件销售软件销售软件销售软件销售7典型案例oRickRashid博士n微软公司主管研究的高级副总裁n美国国家工程院院士、CMU教授、Mach操作系统项目的负责人、参与开发最早的计算机网络游戏之一AltoTrekn据称，每年亲自编写近1.5万行代码！o经典语录n编程：艺术与科学Rick Rashid位运算最显专业的程序设计89位运算o有时我们需要对某个整数类型变量中的某一位（bit）进行操作，比如，判断某一位是否为1，或只改变其中某一位，而保持其他位都不变。C/C+语言提供了“位运算”的操作，能够做到类似的操作。C/C+语言提供了六种位运算符来进行位运算操作：o&按位与|按位或o按位异或取反o
5、右移10按位与o按位与运算符“&”是双目运算符功能：将参与运算的两操作数各对应的二进制位进行与操作，只有对应的两个二进位均为1时，结果的对应二进制位才为1，否则为0。a&b，a，b不需要是二进制数，是整数变量即可11按位与o例如：表达式“21&18”的计算结果是16(即二进制数10000)，因为：o21用二进制表示就是：00000000000000000000000000010101o18用二进制表示就是:00000000000000000000000000010010o二者按位与所得结果是：0000000000000000000000000001000012按位与o按位与运算通常用来将某变量
6、中的某些位清0或保留某些位不变。o例如，如果需要将int型变量n的低8位全置成0，而其余位不变，则可以执行：n=n&0xffffff00;也可以写成：n&=0xffffff00;如果n是short类型的，则只需执行：n&=0xff00;o如何判断一个int型变量n的第7位（从右往左，从0开始数）是否是1?n只需看表达式“n&0x80”的值是否等于0x80即可。13按位或按位或o按位或运算符“|”是双目运算符。n功能：将参与运算的两操作数各对应的二进制位进行或操作，只有对应的两个二进位都为0时，结果的对应二进制位才是0，否则为1。o例如：表达式“21|18”的值是23(即二进制数10111)。o
7、按位或运算通常用来将某变量中的某些位置1或保留某些位不变。o例如，如果需要将int型变量n的低8位全置成1，而其余位不变，则可以执行：nn|=0xff;14按位异或o按位异或运算符“”是双目运算符。n功能：将参与运算的两操作数各对应的二进制位进行异或操作，即只有对应的两个二进位不相同时，结果的对应二进制位才是1，否则为0。o例如：表达式“2118”的值是7(即二进制数111)。o异或运算的特点n如果ab=c，那么就有cb=a以及ca=b。n此规律可以用来进行最简单的加密和解密。15按位非o按位非运算符“”是单目运算符。n其功能是将操作数中的二进制位0变成1，1变成0。o例如，表达式“21”的值
8、是无符号整型数0xffffffea，而下面的语句：printf(%d,%u,%x,21,21,21);o输出结果就是:-22,4294967274,ffffffea16左移运算符o左移运算符“”是双目运算符。n其功能是将左操作数的各二进位全部左移若干位后得到的值，右操作数指明了要左移的位数。n左移时，高位丢弃，左边低位补0。o左移运算符不会改变左操作数的值。17左移运算符o例如，常数9有32位，其二进制表示是：00000000000000000000000000001001o因此，表达式“94”的值，就是将上面的二进制数左移4位，得：000000000000000000000000100100
9、00即为十进制的144。o实际上，左移1位，就等于是乘以2，左移n位，就等于是乘以2n。而左移操作比乘法操作快得多。o特别注意：有符号数的左移溢出情况。#include main() int n1 = 15; short n2 = 15;unsigned short n3 = 15;unsigned char c = 15;n1 = 15; n2 = 15;n3 = 15;c = 6; printf( n1=%x,n2=%d,n3=%d,c=%x,c4=%d,n1,n2,n3,c,c 4);上面程序的输出结果是上面程序的输出结果是:n1=78000,n2=-32768,n3=32768,c=c
10、0,c”是双目运算符。n其计算结果是把“”的左操作数的各二进位全部右移若干位后得到的值，要移动的位数就是“”的右操作数。移出最右边的位就被丢弃。o对于有符号数，如long,int,short,char类型变量，在右移时，符号位（即最高位）将一起移动，并且大多数C/C+编译器规定，如果原符号位为1，则右移时右边高位就补充1，原符号位为0，则右移时高位就补充0。20右移运算符o对于无符号数，如unsignedlong,unsignedint,unsignedshort,unsignedchar类型的变量，则右移时，高位总是补0。o右移运算符不会改变左操作数的值。o实际上，右移n位，就相当于左操作数
11、除以2n，并且将结果往小里取整。#include main()int n1 = 15; short n2 = -15;unsigned short n3 = 0xffe0;unsigned char c = 15;n1 = n12; 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右移运算符实例22思考题思考题-位运算的妙用位运算的妙用o有两个int型的变量a和n(0=n=31)，o要求写一个表达式，使该表达式的值和a的第n位相同
12、。o例如：a=12345，n=3，a的第n位为：3答案：答案： (a & (1 n 位运算解决的常见问题o1.判断二进制下第i位是否是1o2.把二进制下第i位变为1or0o3.求一个数字二进制下有多少个1异或运算的妙用oxor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。oxor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(axorb)xorb=a。xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520xor19880516=206655
13、00，我就把20665500告诉MM。MM再次计算20665500xor19880516的值，得到1314520，于是她就明白了我的意思。HDU3782xxx定律定律oProblemDescriptionn对于一个数n，如果是偶数，就把n砍掉一半；如果是奇数，把n变成3*n+1后砍掉一半，直到该数变为1为止。请计算需要经过几步能将n变到1，具体可见样例。oInputn测试包含多个用例，每个用例包含一个整数n,当n为0时表示输入结束。（1=n=10000）oOutputn对于每组测试用例请输出一个数，表示需要经过的步数,每组输出占一行。25HDU3782xxx定律定律-数据样例oSampleIn
14、putn3/5；8；4；2；1；n1n0oSampleOutputn5n026nProblemDescriptionn对于一个数n，如果是偶数，就把n砍掉一半；n如果是奇数，把n变成3*n+1后砍掉一半；n直到该数变为1为止。标准程序o#includeo#includeo#includeointmain()ointn,time;owhile(scanf(%d,&n),n)otime=0;owhile(n!=1)oif(n&1)on=3*n+1;on=1;oelseon=1;ootime+;ooprintf(%dn,time);ooreturn0;o27求数组中出现次数超过一半的元素求数组中出现
15、次数超过一半的元素o思路1：对于每一个数字，枚举数组中所有的数字，统计有多少个数字跟它是一样的，如果超过了一半，就直接break并输出它。o这样子做，时间复杂度是O（N*N)，空间复杂度是O（N），并不是一个非常好的思路。ofor(inti=1;i=n;i+)ointnum=0;ofor(intj=1;jn/2)oocoutarriendl;obreak;oo求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-循环法循环法求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素o思路2：利用C+中的map，快速的统计每一个数字出现的次数，每当读入一个数字的时候，maparri+，
16、o直接统计出每一个数字出现的次数：o这个做法，时间复杂度是O（N*log（N），这里log（N）是每次用map查找一个数字所用到的时间。空间复杂度也是O（N），但是比思路1略大一点。omapvis;ofor(inti=1;in/2)oocoutarriendl;obreak;oo求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-Map法法求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素o思路3：利用中位数的性质。一个数字出现次数超过了一半，那么他们的中位数必然就是这个数字，因此可以利用中位数来求。最简单的办法就是，排序以后，直接输出最中间的那个数字。o需要注意的是，中位
17、数并不是arrn/2，而是arr(n+1)/2，具体证明过程略。o排序的时间复杂度是O（nlogn），空间复杂度是O（n）osort(arr+1,arr+n+1);ocoutN/2，说明答案这一位上肯定是0，反之，答案这一位上肯定是1！o这样做，时间复杂度是O（N*32），空间复杂度却可以降低到O（33）O（1），因为数组的每一位不再需要保存了，直接读入一个处理一个就可以。ointnum33;ofor(inti=1;i=n;i+)oointnow=1;ofor(intk=0;k0)onumk+;o/位运算的操作，对这两个数字做与操作，o/例如，arri是1101，now是8也就是1000，那么
18、他俩与之后的结果就是1000o/如果，arri是1101，now是2也就是0010，那么他俩与之后的结果就是0000o/换句话说，如果二进制下对应那一位是0，与出来的结果就是0，否则则是一个大于0的数字oointnow=1,ans=0;ofor(intk=0;kn/2)oans+=now;ocoutansendl;求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-二进制法二进制法求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-打架法打架法o来看这样一个例子：o51541131211o一共11个数字，其中1一共出现了6次。那么如何快速的找到这个6呢？我们来考虑这样一个现
19、实生活中的例子：有一群人在打群架，他们每个人有一个编号，代表自己所处的势力，现在这一群人按照顺序依次往广场中央走，如果广场内现在有和自己不是一个势力的人，那么他就和其中一个同归于尽，问，最后哪一个势力的人会获胜？我们按照这个意思，再来看一下刚才这个例子：求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-势力法势力法o1）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5o2）势力1的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人o3）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5o4）势力4的一个人走进广场中央，他发现广场中
20、央有一个势力是5的人，于是同归于尽，现在广场上没有人o5）势力1的一个人走进广场中央，现在广场有一个人，势力是1o6）势力1的一个人走进广场中央，现在广场有两个人，势力是2o求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-势力法势力法o可以发现，每一次火拼，势力最大（也就是出现次数最多的那个数字）的那个每次最多只会死亡一个。而火拼最多会进行N/2次，出现频率最高的那个数字最多只会损失N/2个，而题上告诉我们出现次数已经超过了一半，因此广场上剩下的那个团伙的编号必然是出现次数做多的那个！这样一来，代码就非常好写了。ointnow=0,num=0;/now表示现在广场上面的团伙的编号，num表示当前有几个这样的人ofor(inti=1;i=n;i+)ooif(num=0)/如果广场上面没有人，那么就让这个人站在广场中央oonum=1;onow=arri;ooelseooif(now=arri)/如果是同一伙人，加入团队onum+;oelse/如果不是同一伙人，同归于尽其中一个onum-;ooocoutnowendl;求数组中出现次数超过一半的元素求数组中出现次数超过一半的元素-势力法势力法
