1、江苏省淮阴中学 张坤,位运算及其应用,位运算的简单介绍,计算机中的数据在内存中都是以二进制的形式储存的。位运算，实际上就是直接对整数在内存中的二进制位进行运算，同时，数的各个二进制位互不影响。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。另外，位运算还有很多特殊的技巧，能够帮助我们简化代码、美化程序等等。,位运算的本质思想是什么？,一、位运算的基本操作, and,通过上表不难发现，只有当x和y都为1时and后值才为1。and运算主要是用来取出某个二进制位。例如：A and (1 shl 5)就是取出A的二进制数从右往左
2、第6位。,2018/7/22, or,or运算通常用来强行给二进制的某一位赋值，注意or运算可能导致变量越界，对于有符号类型，or可能把符号位取反，无符号类型可能直接就变成0了，这有可能会导致数据的丢失，使得程序崩溃。因此，执行or运算，应该尽量保证变量不超界，或者更保险地，是非负数。, xor,当两个位不同时得到1，否则为0。因此xor通常可以用来取反。有意思的是xor的逆运算是其本身。, not,not操作就是直接把内存中的0和1全部取反。对于有符号类型，符号位也会取反，这是需要注意的，比如x2147483647，x：longint; not（x）就得到了2147483648，即01111
3、11是表示maxlongint，1000000是表示的maxlongint-1。, shl,左移，就是把二进制数整体向左移动x个位，并且右数x个单位是0；如果移出界，那么移出部分就丢失了，而不会runtime error。对于有符号类型，移位当然会移到符号位上去，比如x230,x：longint；那么x shl 1就得到2147483648；, shr,右移，就是把二进制数整体向右移动x个位，原来的最高x个位就变为0；shr相当于div 2。,如何处理溢出的情况,尽量避免溢出的情况无符号int无符号long long,位运算基本操作总结,and主要是用来取出某一个二进制位or主要是用来强行给二
4、进制的某一位赋值xor运算通常用来取反not操作就是直接把内存中的0和1全部取反,二、位运算运算符的优先级,位运算的优先级,位运算的优先级特别注意的地方,15-1等价于1415+2等价于17虽然掌握各个运算符的优先级并不困难，但是为了避免出错，增强程序的可读性，利于调试，我们还是在需要的地方添加括号来保证优先运算。,三、位运算的一些技巧,位运算的一些技巧,四、位运算的应用,位运算的应用的一些举例,高效代替布尔型数组树状数组表示集合,例题举例,例题一：寻找（seek.*，1秒，256M）,问题描述：给你n个数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇
5、数次的那一个数。,例题一：寻找（seek.*，1秒，256M）,输入格式：输入文件第一行N；接下来N行，每行一个数，表示一个数。（数的范围为int,1N5000000）。输出格式：输出一行一个整数，表示出现了奇数次的那一个数。输入样例：93 3 1 2 4 2 5 5 4输出样例：1,例题一：寻找（seek.*，1秒，256M）,从头到尾异或一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑到异或运算满足交换律，先异或和后异或都是一样的，因此这个算法显然正确。,例题二：寻找2（seek2.*，1秒，256M）,问题描述：给你n个数，其中
6、有且仅有两个数出现了奇数次，其余的数都出现了偶数次。用线性时间常数空间找出出现了奇数次的那一个数。,例题二：寻找2（seek2.*，1秒，256M）,输入格式：输入文件第一行N；接下来N行，每行一个数，表示一个数。（数的范围为int,1N5000000）。输出格式：从小到大输出一行两个整数，表示出现了奇数次的那两个数。输入样例：103 3 1 2 4 2 7 5 5 4输出样例：1 7,例题二：寻找2（seek2.*，1秒，256M）,有什么想法？为什么第一题的算法无计可施？,例题二：寻找2（seek2.*，1秒，256M）,从头到尾异或一遍，你就得到了需要求的两个数异或后的值。这两个数显然不
7、相等，异或出来的结果不为0。我们可以据此找出两个数的二进制表达中不同的一位，然后把所有这n个数分成两类，在那一位上是0的分成一类，在那一位上是1的分到另一类。对每一类分别使用前一个问题的算法。,例题二：寻找2（seek2.*，1秒，256M）,正确性证明？,例题三：起床困难综合症(sleep.*，1秒，256M),问题描述：21 世纪，许多人得了一种奇怪的病：起床困难综合症，其临床表现为：起床难，起床后精神不佳。作为一名青春阳光好少年，atm 一直坚持与起床困难综合症作斗争。通过研究相关文献，他找到了该病的发病原因：在深邃的太平洋海底中，出现了一条名为 drd 的巨龙，它掌握着睡眠之精髓，能随
8、意延长大家的睡眠时间。正是由于 drd 的活动，起床困难综合症愈演愈烈，以惊人的速度在世界上传播。为了彻底消灭这种病，atm 决定前往海底，消灭这条恶龙。,例题三：起床困难综合症(sleep.*，1秒，256M),历经千辛万苦，atm 终于来到了 drd 所在的地方，准备与其展开艰苦卓绝的战斗。drd 有着十分特殊的技能，他的防御战线能够使用一定的运算来改变他受到的伤害。具体说来，drd 的防御战线由 n扇防御门组成。每扇防御门包括一个运算op和一个参数t，其中运算一定是OR,XOR,AND中的一种，参数则一定为非负整数。如果还未通过防御门时攻击力为x，则其通过这扇防御门后攻击力将变为x op
9、 t。最终drd 受到的伤害为对方初始攻击力x依次经过所有n扇防御门后转变得到的攻击力。由于atm水平有限，他的初始攻击力只能为0到m之间的一个整数（即他的初始攻击力只能在0,1,m中任选，但在通过防御门之后的攻击力不受 m的限制）。为了节省体力，他希望通过选择合适的初始攻击力使得他的攻击能让 drd 受到最大的伤害，请你帮他计算一下，他的一次攻击最多能使 drd 受到多少伤害。,例题三：起床困难综合症(sleep.*，1秒，256M),输入格式： 第1行包含2个整数，依次为n,m，表示drd有n扇防御门，atm的初始攻击力为0到m之间的整数。接下来n行，依次表示每一扇防御门。每行包括一个字
10、符串op和一个非负整数t，两者由一个空格隔开，且op在前，t在后，op表示该防御门所对应的操作，t表示对应的参数。输出格式：一行一个整数，表示atm的一次攻击最多使 drd 受到多少伤害。,例题三：起床困难综合症(sleep.*，1秒，256M),输入样例：3 10AND 5OR 6XOR 7输出样例：1样例说明：atm可以选择的初始攻击力为0,1,10。假设初始攻击力为4，最终攻击力经过了如下计算,4 AND 5 = 44 OR 6 = 66 XOR 7 = 1类似的，我们可以计算出初始攻击力为1,3,5,7,9时最终攻击力为0，初始攻击力为0,2,4,6,8,10时最终攻击力为1，因此at
11、m的一次攻击最多使 drd 受到的伤害值为1。2=m=109，0=t1);else ans+;DFS(1,0,0,0),例题五：与（and.*，1秒，256M）,问题描述：给你一个长度为n的序列A，请你求出一对Ai，Aj（1=ij=n）使Ai“与”Aj最大。Ps：“与”表示位运算and，在c+中表示为&。输入格式:第一行为n。接下来n行，一行一个数字表示Ai。输出格式:输出最大的Ai“与”Aj的结果。,例题五：与（and.*，1秒，256M）,输入样例：38102输出样例：8样例说明:8 and 10 = 88 and 2 = 010 and 2 = 2数据范围：20%的数据保证n=50001
12、00%的数据保证 n=3*105，0=Ai=109,例题五：与（and.*，1秒，256M）,输入样例：38102输出样例：8样例说明:8 and 10 = 88 and 2 = 010 and 2 = 2数据范围：20%的数据保证n=5000100%的数据保证 n=3*105，0=Ai=109,例题五：与（and.*，1秒，256M）,从最高位开始，如有大等于2个数该位为1，则该位为0的数全部删除，否则跳过该位,例题六：最小表示（graph.*，1秒，256M）,问题描述：还记得去年JYY所研究的强连通分量的问题吗？去年的题目里，JYY研究了对于有向图的“加边”问题。对于图论有着强烈兴趣的J
13、YY，今年又琢磨起了“删边”的问题。对于一个N个点（每个点从1到N编号），M条边的有向图，JYY发现，如果从图中删去一些边，那么原图的连通性会发生改变；而也有一些边，删去之后图的连通性并不会发生改变。JYY想知道，如果想要使得原图任意两点的连通性保持不变，我们最多能删掉多少条边呢？为了简化一下大家的工作量，这次JYY保证他给定的有向图一定是一个有向无环图（JYY：大家经过去年的问题，都知道对于给任意有向图的问题，最后都能转化为有向无环图上的问题，所以今年JYY就干脆简化一下大家的工作）。,例题六：最小表示（graph.*，1秒，256M）,输入格式：输入一行包含两个正整数N和M。接下来M行，每
14、行包含两个1到N之间的正整数x_i和y_i，表示图中存在一条从x_i到y_i的有向边。输入数据保证，任意两点间只会有至多一条边存在。N=30,000,M=1;i-)/按拓扑序从大到小遍历每个点 将该点指向的所有点按拓扑序从小到大排序； for(int j=1;j=num;j+) int y=aj.en; /依次取出每个点 if(bituy)ans+; bitu|=bity; ,上机题目：拔河比赛（competition.*，1秒，256M）,问题描述 一个学校举行拔河比赛，所有的人被分成了两组，每个人必须（且只能够）在其中的一组，且两个组内的所有人体重加起来尽可能地接近。输入格式 数据的第1行
15、是一个n，表示参加拔河比赛的总人数，接下来的n行表示第1到第n个人的体重，每个人的体重weight都是整数。输出格式 包含两个整数：分别是两个组的所有人的体重和，用一个空格隔开。注意如果这两个数不相等，则请把小的放在前面输出。,上机题目：拔河比赛（competition.*，1秒，256M）,样例输入310090200样例输出190 200数据范围60%的数据保证 n=100，1=weight=500。100%的数据保证 n=500，1=weightn; H0=true; for(int i=1;ix;s+=x;H=H|(Hx); int x=0; for(int i=1;i=s;i+)if(
16、Hi,上机题目：黑客的攻击（Hacker.*，1秒，256M）,问题描述 假设你是一个黑客，入侵了一个有着n台计算机(编号为0,1,.,n-1)的网络。一共有n种服务，每台计算机都运行着所有的服务。对于每台计算机，你都可以选择一项服务，终止这台计算机和所有和它相邻计算机的该项服务（如果其中的一些服务已经停止，则这些服务继续处于停止状态）。你的目标是让尽量多的服务完全瘫痪（即：没有任何计算机运行该项服务),上机题目：黑客的攻击（Hacker.*，1秒，256M）,输入格式 第一行为整数n；以下n行每行描述一台计算机的相邻计算机，其中第一个数m为相邻的计算机个数，接下来m个数为这些计算机的编号。输
17、出格式 输出完全瘫痪的服务器的最大数量样例输入41 11 01 31 2样例输出2数据范围n16。,上机题目：黑客的攻击（Hacker.*，1秒，256M）,一些想法：只有当一个集合里的点能够瘫痪服务器时，这个集合才是有意义的。我们想要知道最多能瘫痪的服务器数量，实际上就是图中所有的点划分成多个集合，每个集合的值都是0或1，表示是否能瘫痪该种服务。,上机题目：黑客的攻击（Hacker.*，1秒，256M）,如何判断哪些集合能够瘫痪一种服务？暴力？位运算！,上机题目：黑客的攻击（Hacker.*，1秒，256M）,如何划分集合？暴力？位运算！,上机题目：黑客的攻击（Hacker.*，1秒，256
18、M）,具体实现：/预处理出每个点相邻的节点for(int i=0;in;i+) scanf(%d, ,上机题目：黑客的攻击（Hacker.*，1秒，256M）,具体实现：/预处理出每个集合划分所能够覆盖的点的集合for(int i=0;i(1n);i+) coversi=0; /用来表示若干计算机的集合 for(int j=0;jn;j+) if(i,上机题目：黑客的攻击（Hacker.*，1秒，256M）,具体实现：/Dp的过程memset(dp,0,sizeof(dp);for(int i=1;i0;j=(j-1),上机题目：黑客的攻击（Hacker.*，1秒，256M）,for(int i=1;i0;j=(j-1)&i),总结,位运算是直接对二进制位整体进行运算。由于位运算直接对位进行操作，因此处理速度非常快。位运算(二进制运算)常常用于表示集合的状态，0表示存在，1表示不存在。位运算在信息学竞赛中往往有优化常数，简化代码的作用。,谢谢大家,
