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

《《位运算及应用》PPT课件.ppt》由会员分享，可在线阅读，更多相关《《位运算及应用》PPT课件.ppt（21页珍藏版）》请在三一办公上搜索。

1、Bitwise Operation,位运算及应用,程序中的所有数在计算机内存中都是以二进制的形式储存的。位运算就是直接对整数在内存中的二进制位进行操作,6(10)110(2)11(10)1011(2),2(10)10(2),(1)什么是位运算,a&b a and ba|b a or ba b a xor ba not aa b a shr b,C P,(2)位运算的操作符,定义两个符号#和，这两个符号互为逆运算 也就是说(x#y)y=x x-x#yy-x yx-x y,a=a+b;b=a-b;a=a-b;,a:=a xor b;a=ab;b:=a xor b;b=ab;a:=a xor b;a

2、=ab;,(3)位运算的一个简单运用,var a:word;begin a:=100;a:=not a;writeln(a);end.#include int main()unsigned short a=100;a=a;printf(%dn,a);return 0;,(4)not 操作,a:=a shl 2;a=a2;,a=10110(2);a=54465(10);,a=10110(2);a=54465(10);,(5)shl shr,去掉最后一位(101101-10110)x shr 1在最后加一个0(101101-1011010)x shl 1在最后加一个1(101101-1011011

3、)x shl 1+1把最后一位变成1(101100-101101)x or 1把最后一位变成0(101101-101100)x or 1-1最后一位取反(101101-101100)x xor 1把右数第k位变成1(101001-101101,k=3)x or(1 shl(k-1)把右数第k位变成0(101101-101001,k=3)x and not(1 shl(k-1)右数第k位取反(101001-101101,k=3)x xor(1 shl(k-1)取末三位(1101101-101)x and 7取末k位(1101101-1101,k=5)x and(1 shl k-1)取右数第k位(

4、1101101-1,k=4)x shr(k-1)and 1把末k位变成1(101001-101111,k=4)x or(1 shl k-1)末k位取反(101001-100110,k=4)x xor(1 shl k-1)把右边连续的1变成0(100101111-100100000)x and(x+1)把右起第一个0变成1(100101111-100111111)x or(x+1)把右边连续的0变成1(11011000-11011111)x or(x-1)取右边连续的1(100101111-1111)(x xor(x+1)shr 1去掉右起第一个1的左边(100101000-1000)x and

5、(x xor(x-1),(6)位运算的常见变换操作,(7)位运算的简单运用,同样假设x是一个32位整数。我们需要查找x在二进制下，1的个数。比如，初始时x为108，那么最后c就变成了4，它表示108的二进制中有4个1。,program find;var i,x,c:longint;begin readln(x);c:=0;for i:=1 to 32 do beginc:=c+x and 1;x:=x shr 1;end;writeln(c);end.,int main()int x,c=0;scanf(%d,108(10),同样假设x是一个32位整数。经过下面5次赋值后，x的值就是原数的二进

6、制表示中数字1的个数。x:=(x and$55555555)+(x shr 1)and$55555555);x:=(x and$33333333)+(x shr 2)and$33333333);x:=(x and$0F0F0F0F)+(x shr 4)and$0F0F0F0F);x:=(x and$00FF00FF)+(x shr 8)and$00FF00FF);x:=(x and$0000FFFF)+(x shr 16)and$0000FFFF);我们下面仅说明这个程序是如何对一个8位整数进行处理的。,211(10),(4)(3)(2)(1),$55555555,$55555555,x,x

7、shr 1,整个程序是一个分治的思想。第一次我们把每相邻的两位加起来，得到每两位里1的个数，比如前两位10就表示原数的前两位有2个1。第二次我们继续两两相加，10+01=11，00+10=10，得到的结果是00110010，它表示原数前4位有3个1，末4位有2个1。最后一次我们把0011和0010加起来，得到的就是整个二进制中1的个数。程序中巧妙地使用取位和右移，比如第二行中$33333333的二进制为，用它和x做and运算就相当于以2为单位间隔取数。shr的作用就是让加法运算的相同数位对齐。,x,第一次运算结果,第二次运算结果,第三次运算结果,vijos P1578 渡河 2描述 Descr

8、iptionJohn住在Alaska,他要渡过一条很宽的河流去往一个临近的城市.John当然首先驾驶狗拉的雪橇来到河边,当然也拖来一条有三个座位的小船;随后他把船放进水中,设法将自己和所有的狗都摆渡到对岸.不过这件事远非想象中那么简单:因为有些狗相互之间有敌意,如果主人不在,它们很容易打起来,于是这些狗不能同时留在同一侧河岸.幸好John很了解他的狗,知道哪些狗之间是有敌意的.有一天John带了5条狗出门:Hurricane,Bear,Wonder,Angry one,和Argot.Bear 对Hurricane,Angry one,以及Argot都有敌意.Wonder 则不能与Hurrica

9、ne 和Angry one和睦相处.其它的狗都能相安无事.于是这条船足够John把所有的狗平安运到对岸(注意到一条狗在船上占据一个座位),而且他在河里摆渡 的次数最少是7次.他是这么干的:1.带Bear和Wonder过河;2.把Wonder留在对岸,带Bear回来;3.带Argot和Bear过河;4.带Bear和Wonder返回;5.带Angry one 和Hurricane过河;6.独自返回;7.最后带Bear和Wonder 过河.这样,当John不在的时候,没有两条敌对的狗同时在同一侧河岸.而如果Argot和Hurricane也相互敌对的话,John就没办法把狗都运到对岸了.然而John家

10、里养了不只这么多的狗,要是下回再多带些,他可能就得花上一整天来考虑如何渡河.为了节约时间,John找到了你,请你写一个程序,对给定数量的狗和它们相互之间的敌对关系,以及船上的座位数,确定John能否把狗摆渡到对岸,如果能,则输出最少需要的步数;如果不能,输出-1,(8)渡河问题的位运算应用,输入格式 Input Format第一行为一个整数M,表示船上的座位数;第二行为狗的总数N(假设将狗依次编号为1N);第三行有一个非负整数K,表示有K对狗之间有敌意;接下来的K行,每行有2个整数,表示互相有敌意的两条狗的编号.M=10,N=10,0=K=50输出格式 Output Format按照题目要求输

11、出单个整数.样例输入 Sample Input3551 22 44 33 12 5样例输出 Sample Output7注释 Hint显然人和每只狗都各占一个座位.,渡河问题一个人带了一只狼，一只羊和一棵白菜过河，河上有一只独木船，没除了人以外，只能带一样东西。另外如果人不在旁时狼就要吃羊，羊就要吃菜。问应该怎样安排过河，才能把所有的东西都带过河。在河上来回的次数又要最少?我们可以先模拟岸一侧的状态：共计16种，当然还可以剔除一些状况，比如0110之类，最后应该剩下10中情况。并根据渡河的条件将状态连线，经过一次渡河，某种情况可以变成另种情况，则两种情况连线。最后我们把渡河问题归结为根据图 G

12、找到0000状态和1111状态的最短路。,5(10),state:,state0 00001 0001 15 7 11 13 52 0010 1111 0111 1011 1101 01013 00114 01005 01016 0110 7 01118 10009 100110 1010 11 1011 1010 0010 0100 1000 000012 1100 10 2 4 8 0 15 1111 图G 留存状态和被剔除状态以及根据题意将状态连线的过程中，我们不妨用位运算来快捷操作,15(10),7(10),11(10),13(10),5(10),10(10),2(10),4(10),

13、8(10),0(10),final,initial,Solution:,1.寻找应该出现的状态(或说删除不应出现的状态)即建立节点。2.将状态和状态之间(符合条件)连线建图。3.求得最短路。,w=座位数=2 n=狗数=3 d=冲突对数=2对;狼吃羊 羊吃菜 fi=1;i=010000-Find State-L=1(n+1)-1;for k=1 to d do read(aa,bb);c=(1 aa)|(1 bb);for i=1 to L do if fi then if(i,aa=1(菜)bb=2(羊)；/编号1 00101 0100-c=0110/冲突的表现if i=14(10)/1110

14、(2)1110/i&0110/c-0110/c&0001/判断人是否在-00000 00001 00012 00103 00114 01005 01016 01107 01118 10009 100110 101011 101112 110013 110114 111015 1111,00011110这2个状态描述的是河岸两侧对应的状态其中一个不行另一个也一定不行,for i=1 to k-1 do for j=i+1 to k do c=ai aj;if(c 1 c表示两岸通过一次换乘，引发变动的位置 即谁，哪个位置参与了换乘2变动的个数要符合(=)座位数，以及换乘时人要在3,xor,(9)

15、N皇后问题位运算版,下面代码是n皇后问题的一个高效位运算程序。初始时，upperlim:=(1 shl n)-1;主程序调用test(0,0,0)后sum的值就是n皇后总的解数。if n=4 upperlim=1111(2);,procedure test(row,ld,rd:longint);varpos,p:longint;begin 1if rowupperlim then 2begin 3 pos:=upperlim and not(row or ld or rd);4 while pos0 do 5 begin 6p:=pos and-pos;7pos:=pos-p;8test(ro

16、w+p,(ld+p)shl 1,(rd+p)shr 1);9 end;10end11else inc(sum);end;,/upperlim=(1 1);9 1011else isum+;,(10)位运算操作注意事项,1.状态就是数(十进制数)，数就是状态。看起来都是“莫名其妙”的十进制，隐含的二进制表示的是状态2.取反的操作要极其注意，因为有可能你的操作数类型是16位或 32位或8位的(或有符号数或无符号数)。不要只关注十进制数本身的二进制状态，高位的0一旦被取反皆成1。3.如果一旦你觉得需要把十进制数转换(不管你采用的是除法或位移)成 二进制，你还需要把这个二进制存放在一个类似数组上面才能放心的 表示状态的时候(一些搜索题目的节点状态)，大概你的作法是错误的。4.当你需要n个1来表示一个初始或终止状态的时候 别忘了是 1n-1;1 shl n-1;5.x shl 2;(x2;)不是x*2 是 x*2*2 或者说 x shl y;(xy;)是 x*2y,Backdrops:-These are full sized backdrops,just scale them up!-Can be Copy-Pasted out of Templates for use anywhere!,Title Backdrop,Slide Backdrop,Print Backdrop,