首页 » C语言解惑 » C语言解惑全文在线阅读

《C语言解惑》17.2 位运算典型实例

关灯直达底部

【例17.9】使用数据作标志的例子。


#include <stdio.h>struct {       unsigned a:1;       unsigned b:2;       unsigned c:3;       int d;} s;int main( ){     s.a=1;    s.b=2;     s.c=3;    s.d=4;     printf (/"%d %d %d %dn/", s.a, s.b, s.c, s.d);     return 0;}  

程序输出结果为:1234

当数据是整型而又取数不大时,为节省存储空间,可在一个字内放几个数据。例如,用数据作标志时,有1位就足够了,这叫标志位。标志位的值要么是1,要么是0。在C语言里,不满一个字的整型变量,也可以作结构成员。

由该例题可以看到,在结构定义中,成员后面有冒号和数字。冒号表示成员是不满一个字的整型数据。这样的成员就叫字段。为表示字段是无正负号的量,字段必须用类型关键字unsigned来定义。冒号后面的数字表示字段的长度。当然,其值要小于字长。如果字长为16位,这数字就小于16。

字段的大小不能超过字长。如果几个字段超过了一个字的大小,那么,编译程序就把该字段移到下一个字。这时,会有若干位不被使用。

此外,若想强制某字段放在一个字的开始部分,只要在该字段的前面写一个长度为0的字段即可,如:

unsigned a:1;

unsigned c:0;

unsigned b:3;

这样,字段b便成为一个字中的开始字段了。

如果不想使用的字段,就像上面那样,不写字段名,代替0而写出位数。这样的字段叫无名字段,它可用来填空。

使用字段,必须注意如下几点:

(1)在IBM PC及其兼容机上,不支持除无符号整数外的其他类型的字段。因此,在说明字段时,必须使用关键字unsigned,即使使用int都不行。

(2)字段不存在地址,不能使用运算符“&”。因而,也无指向字段的指针。

(3)字段在一个字上的分配方向,因机器而异。

(4)不能构造字段数组,必须一个字段一个字段地进行定义。

(5)字段和其他类型成员之间,可有不被使用的位。这也适用于结构成员之间。但是,什么情况下产生间隙与机器有关,例如,若ps为指向结构的指针,而pc为指向字符的指针,则按如下方式进行指针置换,


pc = ( char* ) ps;  

就能使用指向字符型的指针pc,以字节为单位引用结构。但是,在结构中有时也有间隙。因而,若以字节为单位引用结构,有时也能引用没有定义的存储单元。

【例17.10】统计一个数的二进制表示哪位是1及包含1的个数。

【解答】设这个数为num,先分析一个具体数字。假设num=100,表示成16进制是0x64,用二进制表示为:


0110 0100  

将它跟1进行&操作,1的二进制为01,用ret表示运算结果,即


ret = num & 1;  

则ret的结果就是最后一位(bit 0),判断ret是否为1,就是判断最后一位是否为1。同理,2的二进制是10,通过语句


ret = num & 2;  

就能判别倒数第2位(bit 1),以此类推,0100应为4,即


ret = num & 4;  

用来判断倒数第3位(bit 2)。这都是对1进行左移,即2的幂的关系。一个整型数是32位,使用循环语句从0循环到31即可以实现要求。下面给出参考程序及运行示范。


//参考程序#include <stdio.h>int main(){    int i=0,num=0,sum=0;    printf(/"Input a num:/");    scanf(/"%d/",&num);    for(i=0;i<32;i++)    {          if(num&(1<<i)){               printf ( /"bit %d is 1.n/", i );              sum++;          }    }    printf ( /"num %d(%#x) has %d bit is 1.n/", num,num,sum );    return 0;}Input a num:15bit 0 is 1.bit 1 is 1.bit 2 is 1.bit 3 is 1.num 15(0xf) has 4 bit is 1.Input a num:255bit 0 is 1.bit 1 is 1.bit 2 is 1.bit 3 is 1.bit 4 is 1.bit 5 is 1.bit 6 is 1.bit 7 is 1.num 255(0xff) has 8 bit is 1.Input a num:100bit 2 is 1.bit 5 is 1.bit 6 is 1.num 100(0x64) has 3 bit is 1.  

【例17.11】统计一个数二进制表示中1的个数。

【解答】有很多问题只要知道二进制数中有几个1,这在很多情况下还是很有用的。上例中的循环要经历32次,效率是很低的。但它的好处是知道哪一位为1,现在既然不要求这一点,就可以采用效率高的方法求解。

假设有数n,它最右边的i位是1,则n-1的第i位就是0,两者进行与(&)操作,正好第i位的1被清除。例如0xa的二进制是1010,第bit 1位是1,0xa-1=0x9,即1001,两者相与,(0x0a)&(0x0a-1)=0x8(1000)。则清除了0xa第bit 1位的1。

再用0x8&0x7,就把bit 3的1清0,而且0x8&0x7=0,即0xa有2个bit为1。

结论:一个数n与比它少1的数n-1进行与操作n&(n-1),就能清除数n最右边的1。

验证:0x6c&(0x6b)=0x68

  0110 1100

& 0110 1011

= 0110 1000

因为每次只清除最右边的1而保留该位左边的所有1,将n&(n-1)作为新的n,继续做下去,依次为0x60、0x40、0,执行4次,统计出0x6c(十进制108)有4个位是1。

设sum为1的个数计数器,num=num&(num-1)循环到num=0为止,就求出1的个数。


sum=0;  //1的个数,循环到num为0,次数就是1的个数while(num!=0){     num=num&(num-1);      sum++;}  

对于256,它只要1个循环,效率很高,而for循环都是执行32次循环。这种算法最好情况是没有1(不循环),最坏情况是全部是1(要循环32次)。

因为程序最后要用到num,所以使用它的副本temp,参考程序中输出每次相与之后的结果以便看出执行过程加深理解。下面给出程序及运行示范。


//参考程序#include <stdio.h>int main(){     int num=0, sum=0, temp;     printf(/"Input a num:/");     scanf(/"%d/", &num);     temp=num;     while(temp != 0)     {          temp=temp&(temp-1);          printf ( /"Now num = %#x n/", temp );          sum++;     }     printf ( /"num %d(%#x) has %d bit is 1.n/", num,num,sum );     return 0;}Input a num:10Now num = 0x8Now num = 0num 10(0xa) has 2 bit is 1.Input a num:108Now num = 0x68Now num = 0x60Now num = 0x40Now num = 0num 108(0x6c) has 4 bit is 1.Input a num:256Now num = 0num 256(0x100) has 1 bit is 1.Input a num:255Now num = 0xfeNow num = 0xfcNow num = 0xf8Now num = 0xf0Now num = 0xe0Now num = 0xc0Now num = 0x80Now num = 0num 255(0xff) has 8 bit is 1.Input a num:65535Now num = 0xfffeNow num = 0xfffcNow num = 0xfff8Now num = 0xfff0Now num = 0xffe0Now num = 0xffc0Now num = 0xff80Now num = 0xff00Now num = 0xfe00Now num = 0xfc00Now num = 0xf800Now num = 0xf000Now num = 0xe000Now num = 0xc000Now num = 0x8000Now num = 0num 65535(0xffff) has 16 bit is 1.