《C语言程序设计与数据结构》课件第11章

C语言程序设计与数据结构第十一章位运算C语言程序设计与数据结构总体要求：♦理解掌握位运算的六种位运算符及其使用方法♦了解位段数据结构的定义及使用学习重点：♦六种位运算的综合使用11.1位运算符概述11.2基本位运算符及其功能11.3位域（位段）C语言程序设计与数据结构11.1位运算符概述♦所谓位运算是指对二进制位的运算，可以实现按位与、按位或、按位异或、按位取反以及左移、右移等运算。♦C语言提供了以下6种位运算符：1）&按位与2）¦按位或3）∧按位异或4)~按位求反5)按位左移6)按位右移♦位运算符除了~（按位求反）为单目运算符以外，其它均为双目运算符，即：要求位运算符两侧各有一个操作对象。♦在C语言中，位运算的对象只能是整型或字符型数据，不能是其它类型的数据。C语言程序设计与数据结构11.2基本位运算符及其功能♦11.2.1按位与(＆)运算符♦11.2.2按位或(｜)运算符♦11.2.3按位异或(∧)运算符♦11.2.4取反(～)运算符♦11.2.5左移()运算符♦11.2.6右移()运算符♦11.2.7位运算的复合赋值运算符♦11.2.9位运算符的优先级♦11.2.8不同长度的数据进行位运算C语言程序设计与数据结构11.2.1按位与(＆)运算符按位与运算符&是双目运算符。当两个数值进行按位与运算时，是对其值的二进制表示形式逐位进行比较操作，如果两个值对应位上都是1，则该位取值1，否则取值0，其真值表见表11-1：表11-1按位与运算真值表如有两个数4和8进行按位与运算，即4＆8则可表示为：00000100＆0000100000000000结果为0。如果参加＆运算的是负数（如-4&-8），则以补码形式表示为二进制数，然后按位进行“与”运算。aba&b001101010001C语言程序设计与数据结构下面介绍按位与（＆）运算的应用：(1)用于取一个数据的某些指定位。(2)将某个变量的值清零（所有二进制位全部为0），一种方法是将该变量与0进行按位与运算；另一种方法就是找到一个数x与该变量a进行“按位与”运算时，x应满足下面的特征：a的某个二进制位为0，则x相应的二进制位可以是0，也可以是1；a的某个二进制位为1，则x相应的二进制位必须是0。(3)用于保留一个数中某些指定位。方法是：取一个数x与该变量a“按位与”，对于在a中需要保留的二进制位，x中相应的二进制位应为1；其余位为0。C语言程序设计与数据结构11.2.2按位或(｜)运算符按位或运算符“|”是双目运算符。当两个数值作按位或运算时，是对其值的二进制表示形式逐位进行比较操作，如果两值对应位上两个都是0，则该位取值0，否则取值1，其真值表见表11-2：表11-2按位或运算真值表如有两个数24和9进行按位或运算，即24|9，则可表示为：00011000|0000100100011001结果为25。aba|b001101010111C语言程序设计与数据结构【例11.1】求0123|026（即对八进制数123和八进制数26按位或的值。）0000000001010011|00000000000101100000000001010111得到的结果值为八进制数127，即：0123|026=0127。按位或运算常用来对一个数据的某些位置1。方法是：找到一个数x与数据a进行“按位或”运算，数据a中哪一个二进制位希望变成1，则x中相应的二进制位置为1，其余为0。例如：如i|0377是将i的低8位置1，而高8位保留原值。C语言程序设计与数据结构11.2.3按位异或(∧)运算符按位异或运算符“∧”是双目运算符。其功能是参与运算的两个数值对应位相异或，当两个数值对应位相异时，结果为1；否则结果为0。其真值表如表11-3所示。表11-3按位异或运算真值表如有两个数24和9进行按位异或运算，即24∧9，则可表示为：00011000∧0000100100010001结果为17。【例11.2】求0123∧026（即对八进制数123和八进制数26按位异或）的值。0000000001010011∧00000000000101100000000001000101得到的结果值为八进制数105，即：0123∧026=0105aba∧b001101010110C语言程序设计与数据结构下面举例介绍按位异或（∧）运算的应用：(1)使特定位翻转,即1变为0，0变为1【例11.3】将八进制数0123对应的二进制数01010011的低4位翻转，即0变为1，1变为0。可以将它与二进制00001111进行按位异或就可以完成。0000000001010011∧00000000000011110000000001001100(2)与0相异或，保留原值【例11.4】024∧00=024，即：00011000∧0000000000011000(3)与1相异或，使该位置1【例11.5】024∧0377=0377，即：00011000∧1111111111111111(4)交换两个值，不用临时变量假设变量a=3，b=4，交换这两个变量中的值，不使用临时变量实现。实现a，b互换的方法是：a=a∧b;b=b∧aa=a∧b;请读者自己分析，为什么能实现交换的功能？C语言程序设计与数据结构11.2.4取反(～)运算符求反运算符～为单目运算符。其功能是对参与运算的数的各二进位按位求反，即1变0，0变1。其真值表如表11-4所示。表11-4按位反运运算真值表如：~(00001100)，其结果为：11110011【例11.6】求~052（即二进制数0000000000110100）按位求反的值。因为八进制数052，在内存中占两个字节，共16位，因此：~0000000000110100=1111111111001011得到的结果为八进制数0177713，即：~052=0177713。不要以为~052的值是-52。~运算符的优先级别比算术运算符、关系运算符、逻辑运算符和其他位运算符都高，例如：~a&b，先进行~a运算，然后进行&运算。a～b0110C语言程序设计与数据结构11.2.5左移()运算符左移运算符“”是双目运算符。其功能是把“”左边的运算数的各二进位全部左移若干位，由“”右边的数指定移动的位数，高位丢弃，低位补0。如：a2表示a左移两位。如a的值为20，则左移两位的结果如下：a：00010100a2：01010000即左移后a的值为80。【例11.7】定义两个整型变量a和b，其中a的值为10，将其a的二进制数左移3位送入b中。主要程序代码如下：inta,b;a=10;b=a3;二进制数左移过程如下：a:0000000000001010(a=10)b=a2:0000000001010000(b=80=8*10)C语言程序设计与数据结构提示：左移时，当左端移出舍弃的高位中不包含有效二进制数1时，每左移1位相当于移位对象乘以2，左移2位相当于移位对象乘以22=4。上例11.8中b=20，就是103=80,即乘了8。某些情况下，可以利用左移的这一特性代替乘法运算，以加快运算速度。如果左端（高位）移出舍弃的部分包含有效的二进制数1，这一功能特性则不起作用。【例11.8】定义两个字符型变量a和b，其中a的值为68，将其a的二进制数左移2位送入b中。主要程序代码如下：chara，b;a=68;b=a2;二进制数左移过程如下：a:01000100(a=68)b=a2:00010000(b=16)提示：当a左移1位后相当于乘2，左移2位后，将a中的二进制数1移出舍弃，从而使b的值为16（注意：a的值没有变）。C语言程序设计与数据结构11.2.6右移()运算符右移运算符“”是双目运算符。其功能是把“”左边的运算数的各二进位全部右移若干位，“”右边的数指定移动的位数。如：a2表示a右移两位。如a的值为10，则右移两位的结果如下：a：00001010a2：00000010提示：对于有符号数，在右移时，符号位将随同移动。当为正数时，最高位补0，而为负数时，符号位为1，最高位是补0或是补1取决于编译系统的规定，移入0的称为“逻辑右移”，移入1的称为“算术右移”。【例11.9】定义值为20的整型变量a，将a的二进制数右移2位并输出。程序代码如下：main(){inta=20;printf(%d\n,a2);}a在内存存储的二进制数值为：0000000000001111a2后，二进制数值为:0000000000000011输出的十进制数值为：5。提示：右移1位相当于该数除以2，右移2位相当与该数除以2*2=4。C语言程序设计与数据结构【例11.10】定义整型变量a，其中a的值为八进制数0174000，将其a的二进制数算术右移2位并输出。程序代码如下：main(){inta=0174000;printf(%d\n,a2);printf(%o\n,a2);}a在内存存储的二进制数值为:1111100000000000a2后，二进制数值为：1111111000000000输出的十进制数值为：-512。输出的八进制数值为：177000C语言程序设计与数据结构11.2.7位运算的复合赋值运算符位运算符与赋值运算符可以组成复合赋值运算符，常用的有：&=，|=，=，=，∧=。它们的执行过程：a&=b相当于a=a&ba|=b相当于a=a|ba=2相当于a=a2a=2相当于a=a2a∧=b相当于a=a∧b11.2.8不同长度的数据进行位运算如果两个数据长度不同（例如long型和int型）进行位运算时（如a&b，而a为long型，b为int型），系统会将二者按右端对齐，如果b为正数，则左端16位补满0，若b为负数，左端就补满1，如果b为无符号数，则左端补满0。C语言程序设计与数据结构11.2.9位运算符的优先级（1）位运算符自身的优先级为（从高到低）：（高）~、、、&、∧、¦（低）（2）位运算符与其它运算符相比较优先级为(按从高到低顺序)：（高）~算术运算符，关系运算符&，∧，¦逻辑运算符条件运算符赋值（自反赋值）运算符（低）逗号运算符【例11.11】计算表达式的值并输出。。main(){intx=5，y=1；intz;z=x&y==y?x¦y：x∧y;ptintf(z=%d\n,z);}运行结果为：z=5本题中计算顺序依次为==，&，？：，|，=。C语言程序设计与数据结构11.3位域（位段）有些信息在存储时，并不需要占用一个完整的字节，而只需占几个或一个二进制位。例如”真”或”假”用0或1表示时，只有0和1两种状态，用一位二进位即可。为了节省存储空间，并使处理简便，Ｃ语言又提供了一种数据结构，称为“位域”或“位段”。所谓“位域”是把一个字节中的二进位划分为几个不同的区域，并说明每个区域的位数。每个域有一个域名，允许在程序中按域名进行操作。这样就可以把几个不同的对象用一个字节的二进制位域来表示。C语言程序设计与数据结构11．3.1位域的定义和位域变量的说明位域的定义与结构定义相仿，其形式为：struct位域结构名{位域列表};其中位域列表的形式为：类型说明符位域名：位域长度例如：structbs{inta:8;intb:4;intc:4;};位域变量的说明与结构变量说明的方式相同。可采用先定义后说明，同时定义说明或者直接说明这三种方式。例如：structbs{inta:8;intb:4;intc:4;}data;说明data为bs变量，共占两个字节16位。其中位域a占8位，位域b占4位，位域c占4位。C语言程序设计与数据结构对于位域的定义有以下几点说明：一个位域必须存储在同一个字节中，不能跨两个字节。如一个字节所剩空间不够存放另一位域时，应从下一单元起存放该位域。也可以有意使某位域从下一单元开始。例如：structbs{unsigneda:6unsigned:0/*空域*/unsignedb