c程序第12章-位运算.ppt

单击此处编辑母版标题样式,单击此处编辑母版副标题样式,第,12,章 位运算,12.1,位运算符和位运算,12.2,位运算举例,12.3,位段,习题,C,语言是为描述系统而设计的，因此它应当具有汇编语言所能完成的一些功能。,C,语言既具有高级语言的特点，又具有低级语言的功能，因而具有广泛的用途和很强的生命力。第,9,章介绍的指针运算和本章将介绍的位运算就很适合于编写系统软件的需要，是,C,语言的重要特色。在计算机用于检测和控制领域中要用到位运算的知识，因此读者应当学习和掌握本章的内容。,所谓位运算是指进行二进制位的运算。在系统软件中，常要处理二进位的问题。例如，将一个存储单元中的各二进位左移或右移一位，两个数按位相加等。,C,语言提供位运算的功能，与其他高级语言,(,如,PASCAL),相比，它显然具有很大的优越性。,12.1.1,“按位与”运算符,(&),参加运算的两个数据，按二进位进行“与”运算。如果两个相应的二进位都为,1,，则该位的结果值为,1,，否则为,0,。即,0&0=0,；,0&1=0,；,1&0=0,；,1&1=1,；,例如：,3&5,并不等于,8,，应该是按位与。,3=00000011,(&)5=00000101,00000001,12.1,位运算符和位运算,因此，,3&5,的值得,1,。如果参加,&,是负数运算的是负数,(,如,-3&-5),，则以补码形式表示为二进制数，然后按位进行“与”运算。,按位与有一些特殊的用途：,(1),清零。如果想将一个单元清零，即使其全部二进位为,0,，只要找一个二进制数，其中各个位符合以下条件：原来的数中为,1,的位，新数中相应位为,0,。然后使二者进行,&,运算，即可达到清零目的。,如：原有数为,00101011,，另找一个数，设它为,10010100,，它符合以上条件，即在原数为,1,的位置上，它的位值均为,0,。将两个数进行,&,运算：,00101011,(&)10010100,00000000,其道理是显然的。当然也可以不用,10010100,这个数而用其他数,(,如,01000100),也可以，只要符合上述条件即可。,(2),取一个数中某些指定位。如有一个整数,a(2,个字节,),，想要其中的低字节。只需将,a,与,(737)8,按位与即可。见图,12.1,。,图,12.2,图,12.1,c=a&b,，,b,为八进制数的,377,，运算后,c,只保留,a,的低字节，高字节为,0,。,如果想取两个字节中的高字节，只需,c=a&0177400,(0177400,表示八进制数的,177400),。见图,12.2,。,(3),要想将哪一位保留下来，就与一个数进行,&,运算，此数在该位取,1,，如：有一数,01010100,，想把其中左面第,3,、,4,、,5,、,7,、,8,位保留下来，可以这样运算：,01010100 (,十进制数,84),(&)00111011 (,十进制数,59),00010000(,十进制数,16),即,a=84,，,b=59,，,c=a&b=16,。,12.1.2,按位或运算符,(|),两个相应的二进位中只要有一个为,1,，该位的结果值为,1,。即,0|0=0,；,0|1=1,；,1|0=1,；,1|1=1,。例如,:060|017,将八进制数,60,与八进制数,17,进行按位或运算。,00110000,(|)00001111,00111111,低,4,位全为,1,。如果想使一个数,a,的低,4,位改为,1,，只需将,a,与,017,进行按位或运算即可。,按位或运算常用来对一个数据的某些位定值为,1,。如：,a,是一个整数,(16,位,),，有表达式,a|0377,则低,8,位全置为,1,。高,8,位保留原样。,12.1.3,“异或”运算符,(),异或运算符,也称,XOR,运算符。它的规则是若参加运算的两个二进位同号，则结果为,0(,假,),；异号则为,1(,真,),。即,00=0,；,01=1,；,10=1,；,11=0,；如：,00111001 (,十进制数,57,，八进制数,071),()00101010 (,十进制数,42,，八进制数,052),00010011 (,十进制数,19,，八进制数,023),即,071052,，结果为,023(,八进制数),。,“异或”的意思是判断两个相应的位值是否为“异”，为“异”,(,值不同,),就取真,(1),，否则为假,(0),。,下面举例说明,运算符的应用：,(1),使特定位翻转,假设有,01111010,，想使其低,4,位翻转，即,1,变为,0,，,0,变为,1,。可以将它与,00001111,进行,运算，即,01111010,()00001111,0111,0101,结果值的低,4,位正好是原数低,4,位的翻转。要使哪几位翻转就将与其进行,运算的该几位置为,1,即可。这是因为原数中值为,1,的位与,1,进行,运算得,0,，原数中的位值,0,与,1,进行,运算的结果得,1,。,(2),与,0,相保留原值如,01200=012,00001010,()00000000,00001010,因为原数中的,1,与,0,进行,运算得,1,，,00,得,0,，故保留原数。,(3),交换两个值，不用临时变量,假如,a=3,，,b=4,。,想将,a,和,b,的值互换，可以用以下赋值语句实现：,a=ab,；,b=ba,；,a=ab,；,可以用下面的竖式来说明：,a=011,()b=100,a=111(ab,的结果，,a,已变成,7),(),b=,100,b=011(ba,的结果，,b,已变成,3),(),a=111,a=100(ab,的结果，,a,变成,4),即等效于以下两步：,b=b(ab)=bab=abb=a0=a,它相当于上面的前两个赋值语句：“,a=ab,；”,和“,b=ba,；”。,bb,的结果为,0,，因为同一个数与,本身相,，结果必为,0,。现在,b,已得到,a,的值,3,。在上式中除了第一个,b,以外，其余的,a,、,b,都是指原来的,a,、,b,。,再执行,a=ab=(ab)(bab)=abbab=aabbb=b,。,a,得到,b,原来的值。,12.1.4,“取反”运算符,(,),是一个单目,(,元,),运算符，用来对一个二进制数按位取反，即将,0,变,1,，,1,变,0,。例如,025,是对八进制数,25(,即二进制数,00010101),按位求反。,000000000010101,(,),111111111101010,即八进制数,177752,。因此，,025,的值为八进制数,177752,。不要以为,025,的值是,-025,。,下面举一例说明运算符的应用。,若一个整数,a,为,16,位，想使最低一位为,0,，可以用,a=a&0177776,177776,即二进制数,1111111111111110,，如果,a,的值为八进制数,75,，,a&0177776,的运算可以表示如下：,0000000000111101,(&)1111111111111110,0000000000111100,a,的最后一个二进位变成,0,。但如果将,C,源程序移植到以,32位存放一个整数的计算机系统,(,如,AX 11/780),上，由于一个整数用,4,个字节,(32,位表示,),，想将最后一位变成,0,就不能用,a&0177776,了。读者可以自己算一下，当,a=017776543603,时，,a&0177776,的结果是什么？,为了适应以,32,位存放一个整数的计算机系统，应改用,a&037777777776,这样改动使移植性差了，可以改用,a=a&,1,它对以,16,位和以,32,位存放一个整数的情况都适用，不必作修改。因为在以,2,个字节存储一个整数时，,1,的二进制形式为,0000000000000001,，,1,是,111111,1111111110(,注意,1,不等于,-1,，弄清运算符和负号运算符的不同,),。在以,4,个字节存储一个整数时，,1,是,11111111111111111111111111111110,。,运算符的优先级别比算术运算符、关系运算符、逻辑运算符和其他位运算符都高，例如：,a&b,，,先进行,a,运算，然后进行,&,运算。,12.1.5,左移运算符,(,),用来将一个数的各二进位全部左移若干位。例如,:,a=a,2,将,a,的二进制数左移,2,位，右补,0,。若,a=15,，,即二进制数,00001111,，左移,2,位得,00111100,，即十进制数,60(,为简单起见，我们用,8,位二进制数表示十进制数,15,，如果用,16,位，结果是一样的,),。,高位左移后溢出，舍弃不起作用。,左移,1,位相当于该数乘以,2,，左移,2,位相当于该数乘以,22=4,。上面举的例子,15,2=60,，即乘了,4,。但此结论只适用于该数左移时被溢出舍弃的高位中,不包含,1,的情况。例如，假设以一个字节,(8,位,),存一个整数，若,a,为无符号整型变量，则,a=64,时，左移一位时溢出的是,0,，而左移,2,位时，溢出的高位中包含,1,。左移比乘法运算快得多,有些,C,编译程序自动将乘,2,的运算用左移一位来实现,将乘,2,n,的幂运算处理为左移,n,位。,12.1.6,右移运算符,(),a2,表示将,a的各二进位右移,2,位。移到右端的低位被舍弃,对无符号数,高位补,0,。如,a=017,时,:,11,a,为,00001111,，,a2,为,00000011|,11,此二位舍弃,右移一位相当于除以,2,右移,n,位相当于除以,2,n,。,在右移时,需要注意符号位问题。对无符号数,右移时左边高位移入,0,。对于有符号的值,如果原来符号位为,0(,该数为正,),则左边也是移入,0,如同上例表示的那样。如果符号位原来为,1(,即负数,),则左边移入,0,还是,1,要取决于所用的计算机系统。有的系统移入,0,有的移入,1,。移入,0,的称为“逻辑右移”,即简单右移。移入,1,的称为“算术右移”。例如,a,的值为八进制数,113755,。,a:1001011111101101,a1:0100101111110110(,逻辑右移时,),a1:1100101111110110(,算术右移时,),在有些系统上,a1,得八进制数,045766,而在另一些系统上可能得到的是,145766,。,Turbo C,和其他一些,C,编译采用的是算术位移,即对有符号数右移时,如果符号位原来为,1,，左面移入高位的是,1,。,12.1.7,位运算赋值运算符,位运算符与赋值运算符可以组成复合赋值运算符如,:&=,|=,=,=,=,例如,a&=b,相当于,a=a&b,。,a =2,相当于,:,a=a 4,设置一个低,4,位全为,1,其余全为,0,的数。可用下面方法实现,:,(0 4),0,的全部二进制为全,1,，左移,4,位，这样右端低,4,位为,0,。见下面所示：,0:0000000000,0:1111111111,04:1111110000,(0 4)&(0 4),根据上一节介绍的方法，与低,4,位为,1,的数进行,&,运算，就能将这,4,位保留下来。,程序如下：,main(,),unsigned a,，,b,，,c,，,d,；,scanf,(%o,，,&a),；,b=a,4,；,c=,(,0,4),；,d=b&c,；,printf,(%o,，,%dn%o,，,%dn,，,a,，,a,，,d,，,d),；,运行情况如下：,331,331,，,217(,a,的值,),15,，,13 (,d,的值,),输入,a,的值为八进制数,331,，即十进制数,217,，其二进制形式为,11011001,。经运算最后得到的,d,为,00001101,，即八进制数,15,，十进制数,13,。,图,12.4,可以任意指定从右面第,m,位开始取其右面,n,位。只需将程序中的“,b=a,4”,改成“,b=a,(m-n+1)”,以及将“,c=,(,0,4)”,改成“,c=,(,0,n)”,即可。,例,12.2,循环移位。要求将,a,进行右循环移位。见图,12.4,。图,12.4,表示将,a,右循环移,n,位。即将,a,中原来左面,(16-,n),位右移,n,位，原来右端,n,位移到最左面,n,位。今假设用两个字节存放一个整数。为实现以上目的可以用以下步骤：,将,a,的右端,n,位先放到,b,中的高,n,位中。可以用下面语句实现：,b=a,(16-n),；,将,a,右移,n,位，其左面高位,n,位补,0,。可以用下面语句实现：,c=a,n,；,将,c,与,b,进行按位或运算。即,c=c|b,；,程序如下：,main(,),unsigned a,，,b,，,c,；,int,n,；,scanf,(a=%o,，,n=%d,，,&a,，,&n),；,b=a,(16-n),；,c=a,n,；,c=c|b,；,printf,(%on%o,，,a,，,c),；,运行情况如下：,a=157653,，,n=3,0,157653,75765,运行开始时输入八进制数,157653,，即二进制数,1101111110101011,，循环右移,3,位后得二进制数,0111101111110101,，即八进制数,75765,。同样可以左循环位移。,12.3,位段,以前曾介绍过对内存中信息的存取一般以字节为单位。实际上，有时存储一个信息不必用一个或多个字节，例如，“真”或“假”用,0,或,1,表示，只需,1,位即可。在计算机用于过程控制、参数检测或数据通信领域时，控制信息往往只占一个字节中的一个或几个二进位，常常在一个字节中放几个信息。那么，怎样向一个字节中的一个或几个二进位赋值和改变它的值呢？可以用以下两种方法：,(1),可以人为地在一个字节,data,中设几项。例如：,a,、,b,、,c,、,d,分别占,2,位、,6,位、,4,位、,4,位,(,见图,12.5),。如果想将,c,的值变为,12(,设,c,原来为,0),，可以这样：,图,12.5,将数,12,左移,4,位，使,1100,成为右面起第,4,7,位。,将,data,与“,12,4”,进行“按位或”运算，即可使,c,的值变成,12,。,如果,c,的原值不为,0,，应先使之为,0,。可以用下面方法：,data=data&0177417,0177417,的二进制表示为,11,11111,1,0000,1111,a b c d,也就是使第,4,7,位全为,0,其他位全为,1,。它与,data,进行,&,运算,使第,4,7,位为,0,其余各位保留,data,的原状。这个,177417,称为“屏蔽字”,即把,c,以外的信息屏蔽起来,不受影响,只使,c,改变为,0,。但要找出和记住,177417,这个数比较麻烦。可以用,data=data 15,是,c,的最大值,c,共占,4,位,最大值为,1111,即,15,。,154,是将,1111,移到,4,7,位。再取反,就使,4,7,位变成,0,其余位全是,1,。即,15:0000000000001111,15 4:0000000011110000,(15 4):1111111100001111,这样可以实现对,c,清,0,而不必计算屏蔽码。,将上面几步结合起来,可以得到,data=,data&(15 4),|(n,赋予,4,7,位为,0,n,为应赋给,c,的值,(,例如,12).,n&15,的作用是只取,n,的右端,4,位的值,其余各位置,0,即把,n,放到最后,4,位上,(,n&15)4,就是将,n,置在,4,7,位上。见下面,:,data&(154):11011011|0000|1010,(n&15)4:00000000|1100|0000,(,按位或运算,)11011011|1100|1010,可见,data,的其他位保留原状未改变,而第,4,7,位改变为,12(,即,1100),了。,但是用以上办法给一个字节中某几位赋值太麻烦了。可以用下面介绍的位段结构体的方法。,(2),位段,C,语言允许在一个结构体中以位为单位来指定其成员所占内存长度，这种以位为单位的成员称为“位段”或称“位域”,(,bit field),。,利用位段能够用较少,的位数存储数据。,例如：,struct,packed-data,unsigned,a2,；,unsigned,b6,；,unsigned,c4,；,unsigned,d4,；,int,i,；,data,；,见图,12.6,。其中,a,、,b,、,c,、,d,分别占,2,位、,6,位、,4,位、,4,位。,i,为整型。共占,4,个字节。,图,12.6,也可以使各个位段不恰好占满一个字节。如：,struct,packed-data,unsigned,a2,；,unsigned,b3,；,unsigned,c4,；,int,i,；,；,struct,packed-data,data,；,图,12.7,见图,12.7,。其中,a,、,b,、,c,共占,9,位，占,1,个字节多，不到,2,个字节。它的后面为,int,型，占,2,个字节。在,a,、,b,、,c,之后,7,位空间闲置不用，,i,从另一字节开头起存放。,注意，在存储单元中位段的空间分配方向，因机器而异。在微机使用的,C,系统中，一般是由右到左进行分配的，如图,12.8,。但用户可以不必过问这种细节。对位段中的数据引用的方法。如：,图,12.8,data,a=2,；,data,b=7,；,data,c=9,；,注意位段允许的最大值范围。如果写,data,a=8,；,就错了。因为,data.a,只占,2,位，最大值为,3,。在此情况下，自动取赋予它的数的低位。例如，,8,的二进制数形式为,1000,，而,data,a,只有,2,位，取,1000,的低,2,位，故,data,a,得值,0,。,关于位段的定义和引用，有几点要说明：,(1),位段成员的类型必须指定为,unsigned,或,int,类型。,(2),若某一位段要从另一个字开始存放。可以用以下形式定义：,unsigned,a1,；,unsigned,b2,；,一个存储单元,unsigned0,；,unsigned,c3,；,(,另一存储单元,),本来,a,、,b,、,c,应连续存放在一个存储单元,(,字,),中，由于用了长度为,0,的位段，其作用是使下一个位段从下一个存储单元开始存放。因此，现在只将,a,、,b,存储在一个存储单元中，,c,另存放在下一个单元。,(,上述“存储单元”可能是一个字节，可能是,29,字节，视不同的编译系统而异。,),(3),一个位段必须存储在同一存储单元中，不能跨两个单元。如果第一个单元空间不能容纳下一个位段，则该空间不用，而从下一个单元起存放该位段。,(4),可以定义无名字段。如：,unsigned,a1,；,unsigned 2,；,(,这两位空间不用,),unsigned b3,；,unsigned c4,；,见图,12.9,。在,a,后面的是无名位段，该空间不用。,图,12.9,(5),位段的长度不能大于存储单元的长度，也不能定义位段数组。,(6),位段可以用整型格式符输出。如：,printf,(%d,，,%d,，,%d,，,data,a,，,data,b,，,data,c),；,当然，也可以用,%,u,、,%o,、,%x,等格式符输出。,(7),位段可以在数值表达式中引用，它会被系统自动地转换成整型数。如：,data,a+5/data,b,是合法的。,习题,12.1,编写一个函数,getbits,，,从一个,16,位的单元中取出某几位,(,即该几位保留原值，其余位为,0),。函数调用形式为,getbits,(value,，,n1,，,n2),。,value,为该,16,位,(,两个字节,),中的数据值，,n1,为欲取出的起始位，,n2,为欲取出的结束位。如,:,getbits,(0101675,，,5,，,8),表示对八进制,101675,这个数，取出它的从左面起第,5,位到第,8,位。,12.2,写一函数，对一个,16,位的二进制数取出它的奇数位,(,即从左边起第,1,、,3,、,5,、,、,15,位,),。,12.3,编一程序，检查一下你所用的计算机系统的,C,编译在执行右移时是按照逻辑位移的原则还是按算术右移原则？如果是逻辑右移，请你编一函数实现算术右移？如果是算术右移，请编写一函数以实现逻辑右移。,12.4,编一函数用来实现左右循环移位。函数名为,move,，,调用方法为,move(value,，,n),其中,value,为要循环位移的数，,n,为位移的位数。如,n,0,表示为左移；,n,0,为右移。如,n=4,，,表示要右移,4,位；,n=-3,，,为要左移,3,位。,