ACM入门之三-位运算课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,ACM 程序设计,入门之三-位运算,2,为什么要加强程序设计能力？,High thoughts must have high language.,Aristophane,(Greek, Comic dramatist),450 BC - 388 BC,3,为什么要加强程序设计能力？,Programming,之于计算机专业学生,Gun,之于士兵,对于非计算机专业学生,也是攻敌利器，是新时代,的发展必然趋势,4,为什么要加强程序设计能力？,计算机专业学生未来可能人生规划,国内就业机会,=,不好,=,好,出国深造的积极性,出国,留学,在国内,读研,=,高,=,差,个人,IT,能力,IT,公司,核心人才,在家,吃父母,=,强,=,差,个人研究能力,顺利毕业,高级研究员,拿不到学位,=,强,=,差,结论：必须具有较高的程序设计能力！除非你放弃专业,=一般,IT公司,一般人才,目录,2,项目经理 （管理职位）,4,软件售前工程师，产品经理,1,软件架构师,3,5,资深软件工程师,6,系统集成工程师,高级软件工程师,目录,软件测试工程师,8,10,数据库工程师（后台设计和实现）,9,7,QA,质量保证工程师,12,软件实施工程师,11,软件工程师,/,程序员（前台设计和实现，界面设计）,软件销售,7,典型案例,Rick Rashid,博士,微软公司主管研究的高级副总裁,美国国家工程院院士、,CMU,教授、,Mach,操作系统项目的负责人、参与开发最早的计算机网络游戏之一,Alto Trek,据称，每年亲自编写近,1.5,万行代码！,经典语录,编程：艺术与科学,Rick Rashid,位运算,最显专业的程序设计,8,9,位运算,有时我们需要对某个整数类型变量中的某一位（,bit,）进行操作，比如，判断某一位是否为,1,，或只改变其中某一位，而保持其他位都不变。,C/C+,语言提供了“位运算”的操作，能够做到类似的操作。,C/C+,语言提供了六种位运算符来进行位运算操作：,&,按位与,|,按位或,按位异或,取反,右移,10,按位与,按位与运算符“,&”,是双目运算符,功能：将参与运算的两操作数各对应的二进制位进行与操作，只有对应的两个二进位均为,1,时，结果的对应二进制位才为,1,，否则为,0,。,a&b， a，b不需要是二进制数，是整数变量即可,11,按位与,例如：表达式“,21 & 18 ”,的计算结果是,16(,即二进制数,10000),，因为：,21,用二进制表示就是：,0000 0000 0000 0000 0000 0000 0001 0101,18,用二进制表示就是,:,0000 0000 0000 0000 0000 0000 0001 0010,二者按位与所得结果是：,0000 0000 0000 0000 0000 0000 0001 0000,12,按位与,按位与运算通常用来,将某变量中的某些位清,0,或保留某些位不变,。,例如，如果需要将,int,型变量,n,的低,8,位全置成,0,，而其余位不变，则可以执行：,n = n ,也可以写成：,n ,如果,n,是,short,类型的，则只需执行：,n ,如何判断一个,int,型变量,n,的第,7,位（从右往左，从,0,开始数）是否是,1 ?,只需看表达式 “,n & 0x80”,的值是否等于,0x80,即可。,13,按位或,按位或运算符“,|”,是双目运算符。,功能：将参与运算的两操作数各对应的二进制位进行或操作，只有对应的两个二进位都为,0,时，结果的对应二进制位才是,0,，否则为,1,。,例如：表达式“,21 | 18 ”,的值是,23(,即二进制数,10111),。,按位或运算通常用来,将某变量中的某些位置,1,或保留某些位不变,。,例如，如果需要将,int,型变量,n,的低,8,位全置成,1,，而其余位不变，则可以执行：,n |= 0xff;,14,按位异或,按位异或运算符“,”,是双目运算符。,功能：将参与运算的两操作数各对应的二进制位进行异或操作，即只有对应的两个二进位不相同时，结果的对应二进制位才是,1,，否则为,0,。,例如：表达式“,21 18 ”,的值是,7(,即二进制数,111),。,异或运算的特点,如果,ab=c,，那么就有,cb = a,以及,ca=b,。,此规律可以用来进行最简单的加密和解密。,15,按位非,按位非运算符“,”,是单目运算符。,其功能是将操作数中的二进制位,0,变成,1,，,1,变成,0,。,例如，表达式“,21”,的值是无符号整型数,0xffffffea,，而下面的语句：,printf(%d,%u,%x,21,21,21);,输出结果就是,:,-22,4294967274,ffffffea,16,左移运算符,左移运算符“,”,是双目运算符。,其功能是将左操作数的各二进位全部左移若干位后得到的值，右操作数指明了要左移的位数。,左移时，,高位丢弃，左边低位补,0,。,左移运算符不会改变左操作数的值,。,17,左移运算符,例如，常数,9,有,32,位，其二进制表示是：,0000 0000 0000 0000 0000 0000 0000 1001,因此，表达式“,94”,的值，就是将上面的二进制数左移,4,位，得：,0000 0000 0000 0000 0000 0000 1001 0000,即为十进制的,144,。,实际上，左移,1,位，就等于是乘以,2,，左移,n,位，就等于是乘以,2,n,。而左移操作比乘法操作快得多。,特别注意：有符号数的左移溢出情况。,#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=c0,c”,是双目运算符。,其计算结果是把“, ”,的左操作数的各二进位全部右移若干位后得到的值，要移动的位数就是“,”,的右操作数。移出最右边的位就被丢弃。,对于有符号数，如,long,int,short,char,类型变量，在右移时，符号位（即最高位）将一起移动，并且大多数,C/C+,编译器规定，如果原符号位为,1,，则右移时右边高位就补充,1,，原符号位为,0,，则右移时高位就补充,0,。,20,右移运算符,对于无符号数，如,unsigned long,unsigned int, unsigned short, unsigned char,类型的变量，则右移时，高位总是补,0,。,右移运算符不会改变左操作数的值。,实际上，右移,n,位，就相当于左操作数除以,2,n,，并且将结果往小里取整。,#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,思考题-位运算的妙用,有两个,int,型的变量,a,和,n(0 = n n,位运算解决的常见问题,1.判断二进制下第i位是否是1,2.把二进制下第i位变为1 or 0,3.求一个数字二进制下有多少个1,异或运算的妙用,xor运算通常用于对二进制的特定一位进行取反操作，因为异或可以这样定义：0和1异或0都不变，异或1则取反。,xor运算的逆运算是它本身，也就是说两次异或同一个数最后结果不变，即(axorb)xorb=a。,xor运算可以用于简单的加密，比如我想对我MM说1314520，但怕别人知道，于是双方约定拿我的生日19880516作为密钥。1314520xor19880516=20665500，我就,把20665500告诉MM。MM再次计算20665500xor19880516的值，得到1314520，于是她就明白了我的,意思,。,HDU3782,xxx,定律,Problem Description,对于一个数,n,，如果是偶数，就把,n,砍掉一半；如果是奇数，把,n,变成,3*n+ 1,后砍掉一半，直到该数变为,1,为止。请计算需要经过几步能将,n,变到,1,，具体可见样例。,Input,测试包含多个用例，每个用例包含一个整数,n,当,n,为,0,时表示输入结束。（,1=n= 1;, else ,n = 1;,time+;,printf(%dn, time);,return 0;,27,求数组中出现次数超过一半的元素,思路1：对于每一个数字，枚举数组中所有的数字，统计有多少个数字跟它是一样的，如果超过了一半，就直接break并输出它。,这样子做，时间复杂度是O（N*N)，空间复杂度是O（N），并不是一个非常好的思路。,for (int i=1;i=n;i+), int num=0;,for (int j=1;jn/2),coutarriendl;,break;,求数组中出现次数超过一半的元素-循环法,求数组中出现次数超过一半的元素,思路,2,：利用C+中的map，快速的统计每一个数字出现的次数，每当读入一个数字的时候，maparri+，,直接统计出每一个数字出现的次数：,这个做法，时间复杂度是O（N*log（N），这里log（N）是每次用map查找一个数字所用到的时间。空间复杂度也是O（N），但是比思路1略大一点。,map vis;,for (int i=1;in/2),coutarriendl;,break;,求数组中出现次数超过一半的元素-Map法,求数组中出现次数超过一半的元素,思路,3,：利用中位数的性质。一个数字出现次数超过了一半，那么他们的中位数必然就是这个数字，因此可以利用中位数来求。最简单的办法就是，排序以后，直接输出最中间的那个数字。,需要注意的是，中位数并不是arrn/2，而是arr(n+1)/2，具体证明过程略。,排序的时间复杂度是O（nlogn），空间复杂度是O（n）,sort(arr+1,arr+n+1);,coutN/2，说明答案这一位上肯定是0，反之，答案这一位上肯定是1！,这样做，时间复杂度是O（N*32），空间复杂度却可以降低到O（33）O（1），因为数组的每一位不再需要保存了，直接读入一个处理一个就可以。,int num33;,for (int i=1;i=n;i+),int now=1;,for (int k=0;k0),numk+;,/位运算的操作，对这两个数字做与操作，,/例如，arri是1101，now是8也就是1000，那么他俩与之后的结果就是1000,/如果，arri是1101，now是2也就是0010，那么他俩与之后的结果就是0000,/换句话说，如果二进制下对应那一位是0，与出来的结果就是0，否则则是一个大于0的数字,int now=1,ans=0;,for (int k=0;kn/2),ans+=now;,coutansendl;,求数组中出现次数超过一半的元素-二进制法,求数组中出现次数超过一半的元素-打架法,来看这样一个例子：,5 1 5 4 1 1 3 1 2 1 1,一共11个数字，其中1一共出现了6次。那么如何快速的找到这个6呢？我们来考虑这样一个现实生活中的例子：有一群人在打群架，他们每个人有一个编号，代表自己所处的势力，现在这一群人按照顺序依次往广场中央走，如果广场内现在有和自己不是一个势力的人，那么他就和其中一个同归于尽，问，最后哪一个势力的人会获胜？我们按照这个意思，再来看一下刚才这个例子：,求数组中出现次数超过一半的元素-势力法,1）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5,2）势力1的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人,3）势力5的一个人走进广场中央，现在广场中央有一个人，势力是5,4）势力4的一个人走进广场中央，他发现广场中央有一个势力是5的人，于是同归于尽，现在广场上没有人,5）势力1的一个人走进广场中央，现在广场有一个人，势力是1,6）势力1的一个人走进广场中央，现在广场有两个人，势力是2,求数组中出现次数超过一半的元素-势力法,可以发现，每一次火拼，势力最大（也就是出现次数最多的那个数字）的那个每次最多只会死亡一个。而火拼最多会进行N/2次，出现频率最高的那个数字最多只会损失N/2个，而题上告诉我们出现次数已经超过了一半，因此广场上剩下的那个团伙的编号必然是出现次数做多的那个！这样一来，代码就非常好写了。,int now=0,num=0; /now表示现在广场上面的团伙的编号，num表示当前有几个这样的人,for (int i=1;i=n;i+),if (num=0) /如果广场上面没有人，那么就让这个人站在广场中央,num=1;,now=arri;,else,if (now=arri) /如果是同一伙人，加入团队,num+;,else /如果不是同一伙人，同归于尽其中一个,num-;,coutnowendl;,求数组中出现次数超过一半的元素-势力法,