《位运算及应用》PPT课件.ppt

BitwiseOperation,位运算及应用,程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作,6(10)110(2)11(10)1011(2),2(10)10(2),(1)什么是位运算,ab=a-b;a=a-b;,a:=axorb;a=ab;b:=axorb;b=ab;a:=axorb;a=ab;,(3)位运算的一个简单运用,vara:word;begina:=100;a:=nota;writeln(a);end.#includeintmain()unsignedshorta=100;a=a;printf(%dn,a);return0;,(4)not操作,a:=ashl2;a=a10110)xshr1在最后加一个0(101101-1011010)xshl1在最后加一个1(101101-1011011)xshl1+1把最后一位变成1(101100-101101)xor1把最后一位变成0(101101-101100)xor1-1最后一位取反(101101-101100)xxor1把右数第k位变成1(101001-101101,k=3)xor(1shl(k-1)把右数第k位变成0(101101-101001,k=3)xandnot(1shl(k-1)右数第k位取反(101001-101101,k=3)xxor(1shl(k-1)取末三位(1101101-101)xand7取末k位(1101101-1101,k=5)xand(1shlk-1)取右数第k位(1101101-1,k=4)xshr(k-1)and1把末k位变成1(101001-101111,k=4)xor(1shlk-1)末k位取反(101001-100110,k=4)xxor(1shlk-1)把右边连续的1变成0(100101111-100100000)xand(x+1)把右起第一个0变成1(100101111-100111111)xor(x+1)把右边连续的0变成1(11011000-11011111)xor(x-1)取右边连续的1(100101111-1111)(xxor(x+1)shr1去掉右起第一个1的左边(100101000-1000)xand(xxor(x-1),(6)位运算的常见变换操作,(7)位运算的简单运用,同样假设x是一个32位整数。我们需要查找x在二进制下，1的个数。比如，初始时x为108，那么最后c就变成了4，它表示108的二进制中有4个1。,programfind;vari,x,c:longint;beginreadln(x);c:=0;fori:=1to32dobeginc:=c+xand1;x:=xshr1;end;writeln(c);end.,intmain()intx,c=0;scanf(%d,108(10),同样假设x是一个32位整数。经过下面5次赋值后，x的值就是原数的二进制表示中数字1的个数。x:=(xand$55555555)+(xshr1)and$55555555);x:=(xand$33333333)+(xshr2)and$33333333);x:=(xand$0F0F0F0F)+(xshr4)and$0F0F0F0F);x:=(xand$00FF00FF)+(xshr8)and$00FF00FF);x:=(xand$0000FFFF)+(xshr16)and$0000FFFF);我们下面仅说明这个程序是如何对一个8位整数进行处理的。,211(10),(4)(3)(2)(1),$55555555,$55555555,x,xshr1,整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为00110011001100.，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。,x,第一次运算结果,第二次运算结果,第三次运算结果,vijosP1578渡河2描述DescriptionJohn住在Alaska,他要渡过一条很宽的河流去往一个临近的城市.John当然首先驾驶狗拉的雪橇来到河边,当然也拖来一条有三个座位的小船;随后他把船放进水中,设法将自己和所有的狗都摆渡到对岸.不过这件事远非想象中那么简单:因为有些狗相互之间有敌意,如果主人不在,它们很容易打起来,于是这些狗不能同时留在同一侧河岸.幸好John很了解他的狗,知道哪些狗之间是有敌意的.有一天John带了5条狗出门:Hurricane,Bear,Wonder,Angryone,和Argot.Bear对Hurricane,Angryone,以及Argot都有敌意.Wonder则不能与Hurricane和Angryone和睦相处.其它的狗都能相安无事.于是这条船足够John把所有的狗平安运到对岸(注意到一条狗在船上占据一个座位),而且他在河里摆渡的次数最少是7次.他是这么干的:1.带Bear和Wonder过河;2.把Wonder留在对岸,带Bear回来;3.带Argot和Bear过河;4.带Bear和Wonder返回;5.带Angryone和Hurricane过河;6.独自返回;7.最后带Bear和Wonder过河.这样,当John不在的时候,没有两条敌对的狗同时在同一侧河岸.而如果Argot和Hurricane也相互敌对的话,John就没办法把狗都运到对岸了.然而John家里养了不只这么多的狗,要是下回再多带些,他可能就得花上一整天来考虑如何渡河.为了节约时间,John找到了你,请你写一个程序,对给定数量的狗和它们相互之间的敌对关系,以及船上的座位数,确定John能否把狗摆渡到对岸,如果能,则输出最少需要的步数;如果不能,输出-1,(8)渡河问题的位运算应用,输入格式InputFormat第一行为一个整数M,表示船上的座位数;第二行为狗的总数N(假设将狗依次编号为1N);第三行有一个非负整数K,表示有K对狗之间有敌意;接下来的K行,每行有2个整数,表示互相有敌意的两条狗的编号.M=10,N=10,0=K=50输出格式OutputFormat按照题目要求输出单个整数.样例输入SampleInput3551224433125样例输出SampleOutput7注释Hint显然人和每只狗都各占一个座位.,渡河问题一个人带了一只狼，一只羊和一棵白菜过河，河上有一只独木船，没除了人以外，只能带一样东西。另外如果人不在旁时狼就要吃羊，羊就要吃菜。问应该怎样安排过河，才能把所有的东西都带过河。在河上来回的次数又要最少?我们可以先模拟岸一侧的状态：共计16种，当然还可以剔除一些状况，比如0110之类，最后应该剩下10中情况。并根据渡河的条件将状态连线，经过一次渡河，某种情况可以变成另种情况，则两种情况连线。最后我们把渡河问题归结为根据图G找到0000状态和1111状态的最短路。,5(10),state:,state00000100011571113520010111101111011110101013001140100501016011070111810009100110101011101110100010010010000000121100102480151111图G留存状态和被剔除状态以及根据题意将状态连线的过程中，我们不妨用位运算来快捷操作,15(10),7(10),11(10),13(10),5(10),10(10),2(10),4(10),8(10),0(10),final,initial,Solution:,1.寻找应该出现的状态(或说删除不应出现的状态)即建立节点。2.将状态和状态之间(符合条件)连线建图。3.求得最短路。,w=座位数=2n=狗数=3d=冲突对数=2对;狼吃羊羊吃菜fi=1;i=010000-FindState-L=1(n+1)-1;fork=1toddoread(aa,bb);c=(1aa)|(1bb);fori=1toLdoiffithenif(i,aa=1(菜)bb=2(羊)；/编号1001010100-c=0110/冲突的表现ifi=14(10)/1110(2)1110/iif(c1c表示两岸通过一次换乘，引发变动的位置即谁，哪个位置参与了换乘2变动的个数要符合(1);91011elseisum+;,(10)位运算操作注意事项,1.状态就是数(十进制数)，数就是状态。看起来都是“莫名其妙”的十进制，隐含的二进制表示的是状态2.取反的操作要极其注意，因为有可能你的操作数类型是16位或32位或8位的(或有符号数或无符号数)。不要只关注十进制数本身的二进制状态，高位的0一旦被取反皆成1。3.如果一旦你觉得需要把十进制数转换(不管你采用的是除法或位移)成二进制，你还需要把这个二进制存放在一个类似数组上面才能放心的表示状态的时候(一些搜索题目的节点状态)，大概你的作法是错误的。4.当你需要n个1来表示一个初始或终止状态的时候