位运算及其对程序的优化ppt.ppt

位运算及其对程序的优化,常州市第一中学 戴涵俊,序言,程序中所有的数据在计算机内存中都是以二进制的形式储存的。位运算，本质上就是直接对整数在内存中的二进制位进行运算，同时，数的各个二进制位互不影响。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。另外，位运算还有很多特殊的技巧，能够帮助我们简化代码、美化程序等等。本文就结合自己的学习和应用经验，介绍一些位运算及其对程序的优化方法。,正文,一、位运算的基本操作,二、位运算的实用技巧,三、位运算对一些数据结构的优化,四、位运算对一些算法的优化,一、位运算的基本操作,位运算主要有and，or，xor，not，shl，shr我们不妨通过一下的真值表来了解它们的运算法则,Shl：左移，就是把二进制数整体向左移动x个位，右边x位补成0Shr：右移，就是把二进制数整体向右移动x个位，原来高位的x个变成0，相当于div 2。,1.位运算介绍,由上面的介绍，我们不难发现这些位运算的基本用途：,and主要是用来取出某一个二进制位,or主要是用来强行给二进制的某一位赋值,xor运算通常用来取反,not操作就是直接把内存中的0和1全部取反,2.位运算的优先级,not and,shl,shr or,xor,比如以下几个运算，你能很快报出结果吗？not 1 or 1 not 1 and 1 1 and 1 shl 1 not 1 or 0 shl 1 xor 0 and 1=,1,0,2,2,3.例题,例1、一个文件中有9亿个不重复的9位整数，现在要求对这个文件进行排序（当然时间可以不止1秒，但要求出可行解，即在可以接受的时间和空间范围内）。,001101100110001110,4出现了,14没有出现,二、位运算的实用技巧,1.对于mod运算的优化,mod版本：for i:=1 to time do x:=y mod base;and 版本：for i:=1 to time do x:=y and(1 shl 20-1);,2.位运算的一些技术,三、位运算对一些数据结构的优化,1.循环队列,2.树状数组,循环队列比较方便的实现可以用一个头指针head，一个尾指针tail，每次取出来的是head mod base。这里不妨把base设置为2的整数次幂1，然后用and来取模。,低位技术（Lowbit）Li：=i and（i xor（i-1）。,3.集合,例题,例2.尼克在一家养猪场工作，这家养猪场共有M间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没有办法打开这些猪舍，客户们从早上开始一个接一个来购买生猪，他们到达后首先用手中的钥匙打开他所能打开的全部猪舍，然后从中选取他要买的生猪，尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中，每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。好在尼克事先知道每位客户手中有哪些钥匙，要买多少猪，以及客户到来的先后次序。请你写一个程序，帮助尼克求出最多能卖出多少头生猪。,猪舍,客户,s,t,这里用整数来表示猪舍的有无情况，这样最大可以有1000个二进制位，于是还要分段处理。不妨每段用一个64位的qword，把1000总共分成16段，对于每个猪舍编号k，先判断是哪一段的（用（k-1）div 64+1，可以写成shr 6加速），然后再在那一段进行赋值。于是，对于两段猪舍，看有无交集，只需要and一下，看是不是0就可以了。这样，我们把预处理的时间复杂度降到了O（100*100*16）。,例3、某山贼集团在绿荫村拥有强大的势力，整个绿荫村由N个连通的小村落组成，并且保证对于每两个小村落有且仅有一条简单路径相连。小村落用阿拉伯数字编号为1,2,3,4,n，山贼集团的总部设在编号为1的小村落中。山贼集团除了老大坐镇总部以外，其他的P个部门希望在村落的其他地方建立分部。P个分部可以在同一个小村落中建设，也可以分别建设在不同的小村落中。每个分部到总部的路径称为这个部门的管辖范围，于是这P个分部的管辖范围可能重叠，或者完全相同。在不同的村落建设不同的分部需要花费不同的费用。每个部门可能对他的管辖范围内的小村落收取保护费，但是不同的分部如果对同一小村落同时收取保护费，他们之间可能发生矛盾，从而损失一部分的利益，他们也可能相互合作，从而获取更多的利益。现在请你编写一个程序，确定P个分部的位置，使得山贼集团能够获得最大的收益。,fi,j:=maxfi,x+fk,yprofitj，其中i表示子树的根节点，k表示儿子节点，j表示根节点的状态集合，x or yj，profit为对应状态下的总的盈利值。,由上，我们需要快速知道给定的一个集合，它的所有子集是什么，如果纯粹地对每个集合进行暴力穷举，这个时间复杂度是4n，但是，我们知道一个结论，就是n个元素的全集，它的所有子集的所有子集个数总和为3n（这个比较容易证明，在此不再赘述）。所以，我们希望不要穷举没用的集合。一种方式比较容易想到，就是预处理每一个集合各自的子集，并用拉链存储。预处理时候再用队列优化，预处理用n*3n。在当时我就是这么做过的。,另外有一种更好的方式，不需要预处理，在参考了NOI专刊上的论文后感觉它与lowbit技术很好地结合了起来。比如当前的集合为A，那么我们依次枚举出它的子集：B:=A;While A0 do Begin A:=(A-1)and B;End；A1的意思就是把A集合中最后一个1变成0，最后一个1后面的0都变成1（最后是指右边），然后再and一个B，保证是原来A的子集。这样做就相当方便了。,4.哈希表,哈希表最关键的莫过于哈希函数了，一般是mod一个大质数。对于字符串的哈希，华丽的位运算体现了它独特的魅力。,在我的doc文档里面列举了一些字符串哈希函数，在此不再重复。,例题,例4、农民Brown和John的牛们计划协同逃出它们各自的农场。它们设计了一种加密方法用来保护它们的通讯不被他人知道。如果一头牛有信息要加密，比如International Olympiad in Informatics，它会随机地把C，O，W三个字母插到到信息中（其中C在O前面，O在W前面），然后它把C与O之间的文字和 O与W之间的文字的位置换过来。为了使解密更复杂，牛们会在一条消息里多次采用这个加密方法（把上次加密的结果再进行加密）。一天夜里，John的牛们收到了一条经过多次加密的信息。请你写一个程序判断它是不是这条信息经过加密（或没有加密）而得到的：Begin the Escape execution at the Break of Dawn,这里是两个例子：International Olympiad in Informatics-CnOIWternational Olympiad in InformaticsInternational Olympiad in Informatics-International Cin InformaticsOOlympiad W,四、位运算对一些算法的优化,1.状态压缩动态规划,例5、所有人知道秘密特务007，詹姆斯邦德，但是很少人知道，许多时候他并不亲自去做任务，而是让他的表兄弟们完成。现在每当詹姆斯收到任务，他就将任务分发给大家，于是他需要你的帮助。詹姆斯每月收到一张任务单。对于每一个任务，他都根据以往的经验，计算出他和其他几位兄弟完成的成功概率。你的程序应当找到一种分配方案，使得所有任务都被成功完成的概率最大。注：所有任务都被成功完成的概率，等于每个任务都被成功完成的概率之积。,Fi,j:=maxfi-1,k*ai,r|k or(1 shl(r-1)=j且k and(1 shl(r-1)=0；,2.搜索,（1）状态表示,（2）状态判重,下文例题中的TV一题，便是通过用二进制数结合位运算来表示状态并进行状态转移，这样不仅提高了搜索效率，而且还方便了程序实现。,搜索常常需要开一个哈希表来记录状态是否达到或者该状态的最优值，有了位运算，一方面，我们将状态表示成整数，通过直接寻址或者拉链储存状态；另外一方面，加入位运算的哈希函数更加强大，减少哈希过程中的冲突。,例6、大卫有一台旧电视机，上面的许多按钮已无法正常工作，当电视机新的时候，按下某一按钮，其他按钮都将被释放，只有被按的按钮工作。现在按下某个按钮后，有一些按钮将被释放，而另外的一些按钮将不改变原状态。大卫知道按下每一个按钮会产生什么样的效果。编写程序帮助大卫计算，从给定的状态到只有按钮3工作而其他按钮都被释放这个最终状态所需按下的按钮序列的最短长度。,例题,例7、给出n的一个全排列（n5就输出“5 or more”。,五、总结,位运算虽然表面上只是简单的几个操作，但是其中蕴含了很多的东西可以挖掘。掌握好位运算，首先，你对计算机的认识就更深了一步；其次，位运算作为一种底层操作，它所拥有的效率可以加速你的程序，减小常数时间操作对渐近时间复杂度的影响；第三，有了位运算，我们能够方便地将状态表示为整数，从而降低了编程复杂度和时空复杂度。当然，位运算也会有一些缺陷，比如在我们表示状态的时候虽然用整数可以解决很多事情，但是调试的时候却没有数组或者其它表示方式来得直观，对于一个整数，我们似乎还没有直接知道某几位的01情况；在移位操作时候还要格外注意不要移出界，正整数移成负数的可能会使得数组越界造成201错误；还有就是注意普通乘、除运算和位运算的优先级，在必要的地方加上括号。,谢谢！,