（本科）第10章 位运算ppt课件.pptx
课程主讲人：第10章 位运算C语言程序设计3C语言程序设计（第二版）4第10 章 位运算1C语言的发展与操作系统的发展密切相关，其最早的用途就是为了编制UNIX操作系统。到目前为止，几乎所有的操作系统和主流的应用软件均由C语言来编写。操作系统作为计算机系统中最基础和最底层的软件平台，是计算机硬件与计算机应用软件的桥梁。在C语言出现之前，操作各种硬件的主要开发工具为汇编语言。使用汇编语言可以直接操作硬件，并且汇编程序具有体积小、运行速度快的特点。为了能够编写出与汇编程序相当的程序，C语言引入了指针和位运算。2根据前面所介绍的知识可知，所有的数据在计算机中均是以二进制形式存储。计算机具有的基本计算功能仅仅为二进制加法和逻辑运算。前面介绍的各种运算都是以字节作为最基本位进行的。但在很多系统程序中常要求在位（bit）一级进行运算或处理。语言提供了位运算的功能，这使得语言也能像汇编语言一样用来编写系统程序。5第10 章 位运算知识点：二进制位运算C语言位运算符和运算表达式6种二进制位运算的功能技能点：掌握6种位运算使用的基本方法6第10 章 位运算10.1 案 例 引 入【例10-1】在一个整数中找出密码。一个公司把密码隐藏在一个整数中，密码是这个数按二进制形式从右端开始的第4位至第9位，编写程序找出密码，例如，给出数字2019，得到密码为111110。7第10 章 位运算任务分析：（1）首先将整数num要取出的从右端开始的49位移到最右端，即将num右移4位。可以用下面的方法实现：num 4。（2）接着设置一个低6位全为1、其余全为0的数，即0 x3f = 63 = 1111112。（3）最后将上面二者进行与运算，即(num 4) & 0 x3f，则求出所要的结果，再按二进制输出。8第10 章 位运算10.2 位 运 算 符10.2.1 二进制位运算概述大多数计算机系统的内存都是由许多被称为字节的单元组成的，每个字节都有一个地址。一个字节一般由8位二进制数组成，其中最右边的称为最低有效位，最左边的称为最高有效位，每个二进制的值是0或1。微机中一般以4个字节存放一个实数，2个字节存放一个整数。9第10 章 位运算计算机系统中数据编码一般有原码、反码和补码3种形式：（1）原码。原码就是符号位加上真值的绝对值, 即用第一位表示符号, 其余位表示值. 比如如果是8位二进制，例如：1的原码：+1原 = 00000001-1原 = 1000000110第10 章 位运算（2）反码。反码有两种情况：当原码为正数时，其反码就等于正数的原码（+原码 = +反码）。当原码为负数时，其反码就等于正数的原码按位取反，但是最高位的符号位不变。1的反码：+1反 = +1原 = 00000001-1反 = 11111110如果一个反码表示的是负数，要将其转换成原码再计算它真正的数值，否则是不知道它表示是什么数值。11第10 章 位运算（3）补码。补码有两种情况：当原码为正数时，其补码也等于正数的原码（+原码 = +反码 = +补码）。当原码为负数时，其补码等于正数的原码按位取反，符号位不变，最后在末尾加1（即在反码的末尾加1）。+1原 = 00000001=00000001=00000001-1原 = 10000001=11111110=11111111负数的补码和反码一样，需要转换为原码才能分辨其数值。在介绍位运算之前，首先介绍逻辑运算中的真值表，如表10-1所示。12第10 章 位运算 表10-1 逻辑运算真值表其中：0代表错误（伪），1代表正确（真）。ABA与BA或B非AA异或B00001001011110010111110013第10 章 位运算由表10-1中可知：（1）逻辑或运算表示在给定的逻辑变量中，A或B只要有一个为1，其逻辑或的值为1；只有当两者都为0，逻辑或才为0。即一真必真，两假才假。（2）逻辑与运算表示只有当参与运算的逻辑变量都取值为1时，其逻辑乘积才等于1，即一假必假，两真才真。14第10 章 位运算（3）逻辑非运算表示输出结果与输入相反，当输入为0时，输出为1，输入为1时，输出为0。（4）逻辑异或表示在给定的两个逻辑变量中，只有两个逻辑变量取值相同，异或运算的结果就为0；只有相异时，结果才为1。即一样时为0，不一样才为1。当两个变量之间进行逻辑运算时，只在对应位之间按上述规律进行逻辑运算，不同位之间没有任何关系，当然，也就不存在算术运算中的进位或借位问题。15第10 章 位运算10.2.2 各种位运算为了实现对应的逻辑运算，在C语言中提供对应的位逻辑运算符：&：按位与运算。 |：按位或运算。 ：按位异或运算。 ：取反运算。16第10 章 位运算另外，C语言中还提供位移运算符。：右移。基本的位操作符有与、或、异或、取反、左移、右移这6种，它们的运算规则如表10-2所示。17第10 章 位运算表10-2 位运算规则表符 号描 述运 算 规 则&与两个位都为1时，结果才为1|或两个位都为0时，结果才为0异或两个位相同为0，相异为1取反0变1，1变0 右移各二进位全部右移若干位，对无符号数，高位补0，有符号数，各编译器处理方法不一样，有的补符号位（算术右移），有的补0（逻辑右移）18第10 章 位运算注意以下几点：（1）在这6种操作符，只有取反是单目操作符，其他5种都是双目操作符。（2）位操作只能用于整形数据，其他类型进行位操作会被编译器报错。（3）对于移位操作，在微软的VC 6.0和VS 2008编译器都是采取算术移位操作，算术移位是相对于逻辑移位，它们在左移操作中都一样，低位补0即可，但在右移中，逻辑移位的高位补0，而算术移位的高位是补符号位。例如下面代码会输出-4和3。19第10 章 位运算int a = -15, b = 15; printf(%d %dn, a 2, b 2); int类型一般占4字节，32位。因此15=(00000000 00000000 00000000 00001111)2，右移二位，最高位由符号位填充将得到(00000000 00000000 00000000 0000 0011)2即3。-15=(11111111 11111111 11111111 1111 0001)2，右移二位，最高位由符号位填充将得到(11111111 11111111 11111111 1111 1100)2，即-4。20第10 章 位运算（4）位操作符的运算优先级比较低，因为尽量使用括号来确保运算顺序，否则很可能会得到莫名其妙的结果。比如要得到像1、3、5、9这些2 i + 1的数字，写成int a = 1 i + 1;是不对的，程序会先执行i + 1，再执行左移操作。应该写成int a = (1 i) + 1;。（5）另外，位操作还有一些复合操作符，如&=、|=、 =、=。21第10 章 位运算1按位与运算按位与运算符&是双目运算符，其功能是参与运算的两数各对应的二进位相与。只有对应的两个二进位均为1时，结果位才为1，否则为0。参与运算的数以补码方式出现。例如：int型常量9和5进行位与运算的运算过程如下：可见，9 & 5 = 1。 9 = 0000 0000 0000 1001&5 = 0000 0000 0000 0101= 0000 0000 0000 000122第10 章 位运算例如：int型常量-4和7进行位与运算的运算过程如下： 可见，-4 & 7 = 4。 4 = 1111 1111 1111 1100&7 = 0000 0000 0000 0111 0000 0000 0000 010023第10 章 位运算位与运算的主要用途如下：（1）清零：快速对某一段数据单元的数据清零，即将其全部的二进制位为0。例如整型数a = 321对其全部数据清零的操作为a = a & 0 x0。 可见，最后a全部数据清零。 321 = 0000 0001 0100 0001&0 = 0000 0000 0000 0000 0000 0000 0000 000024第10 章 位运算（2）获取一个数据的指定位。例如获得整型数a = 321的低八位数据的操作为a = a & 0 xFF。 321 = 0000 0001 0100 0001& 0 xFF = 0000 0000 1111 1111 0000 0000 0100 0001可见，最后a保留了低八位数据。25第10 章 位运算获得整型数a = 321的高八位数据的操作为a = a & 0 xFF00。321 = 0000 0001 0100 0001& 0XFF00 = 1111 1111 0000 0000 0000 0001 0000 0000可见，最后a保留了高八位数据。26第10 章 位运算（3）保留数据区的特定位。例如获得整型数a = 321的第7 8位（从0开始）位的数据操作为： 321 = 0000 0001 0100 0001& 384 = 0000 0001 1000 0000 0000 0001 0000 0000可见，最后a保留了第7 8位数据。27第10 章 位运算【例10-2】求a和b相与后的结果。28第10 章 位运算2按位或运算按位或运算符 | 是双目运算符，其功能是参与运算的两数各对应的二进位相或。只要对应的二个二进位有一个为1时，结果位就为1。参与运算的两个数均以补码出现。例如：9 | 5可写算式如下： 9 = 00001001| 5 = 0000010100001101可见，9 | 5 = 13。29第10 章 位运算【例10-3】求a和b相或后的结果。位或运算的主要用途如下。设定一个数据的指定位。例如整型数a = 321，将其低八位数据置为1的操作为a = a | 0XFF。 321 = 0000 0001 0100 0001|OXFF = 0000 0000 1111 1111 0000 0000 1111 1111注意：注意逻辑运算符|与位或运算符|的区别。30第10 章 位运算3按位异或运算按位异或运算符 是双目运算符，其功能是参与运算的两数各对应的二进位相异或，当两对应的二进位相异时，结果为1。参与运算数仍以补码出现。例如：9 5可写成算式如下：9 = 000010015 = 0000010100001100可见，9 5 = 12。31第10 章 位运算【例10-4】求a和b相异或后的结果程序代码如下：位异或运算的主要用途：（1）定位翻转。设定一个数据的指定位，将1换为0，0换为1。例如整型数a = 321,，将其低八位数据进行翻位的操作为a = a 0XFF。321 = 0000 0001 0100 0001 0 xFF = 0000 0000 1111 11110000 0001 1011 1110（2）数值交换。在例10-5中，无须引入第三个变量，利用位运算即可实现数据交换。32第10 章 位运算【例10-5】不使用第三变量的两数交换。可以这样理解：（1）a = b 即a = (a b)。（2）b = a 即b = b (a b)，由于运算满足交换律，b (a b) = b b a。由于一个数和自己异或的结果为0，并且任何数与0异或都会不变的，所以此时b被赋上了a的值。（3）a = b 就是a = a b，由于前面二步可知a = (a b)，b = a，所以a = a b即a = (a b) a。故a会被赋上b的值。33第10 章 位运算再来个实例说明下以加深印象。int a = 13, b = 6;a的二进制为：13 = 8 + 4 + 1 = 1101。b的二进制为：6 = 4 + 2 = 110。第一步：a = b a = 1101 110 = 1011。第二步：b = a b = 110 1011 = 1101;即b = 13。第三步：a = b a = 1011 1101 = 110;即a = 6。34第10 章 位运算4求反运算求反运算符为单目运算符，具有右结合性，其功能是对参与运算的数的各二进位按位求反。例如：9的运算为：（0000000000001001）。结果为：35第10 章 位运算【例10-6】求反运算。36第10 章 位运算5左移运算左移运算符是双目运算符，其功能把左边的运算数的各二进位全部左移若干位，由右边的数指定移动的位数，并在空出的位置上填0，最高位溢出并舍弃。37第10 章 位运算例如：a 是双目运算符，其功能是把左边的运算数的各二进位全部右移若干位，并舍弃出界的数字。右边的数指定移动的位数。例如：a = 15a 2表示把000001111右移为00000011（十进制3）。40第10 章 位运算应该说明的是，对于有符号数，在右移时，符号位将随同移动。当为正数时，最高位补0，而为负数时，符号位为1。最高位是补0或是补1 取决于编译系统的规定。Turbo C和很多系统规定为补1。可以看出，位右移运算可以实现除数为2的整除运算。注意：将所有对2的整除运算转换为位移运算，可提高程序的运行效率。41第10 章 位运算【例10-8】将一个数右移2位。42第10 章 位运算7其他位运算符在C语言中还提供复合的位运算符，如下：&=、!=、=、b = pbit-b & 3位域b中原有值为7，与3作按位与运算的结果为3（111 & 011 = 011，十进制值为3）。53第10 章 位运算同样，程序第18行中使用了复合位运算符|=，相当于：pbit-c = pbit-c | 1其结果为15。程序第19行用指针方式输出了这三个域的值。位域的作用以及位域结构体的存储。位域成员不能单独被取sizeof值。C99规定int、unsigned int和bool可以作为位域类型，但编译器几乎都对此作了扩展，允许其他类型存在。54第10 章 位运算使用位域的主要目的是压缩存储，其大致规则为：（1）如果相邻位域字段的类型相同，且其位宽之和小于类型的sizeof大小，则后面的字段将紧邻前一个字段存储，直到不能容纳为止。（2）如果相邻位域字段的类型相同，但其位宽之和大于类型的sizeof大小，则后面的字段将从新的存储单元开始，其偏移量为其类型大小的整数倍。55第10 章 位运算（3）如果相邻的位域字段的类型不同，则各编译器的具体实现有差异，VC6采取不压缩方式，Dev-C+采取压缩方式。（4）如果位域字段之间穿插着非位域字段，则不进行压缩。（5）整个结构体的总大小为最宽基本类型成员大小的整数倍。56第10 章 位运算10.4 程序设计举例【例10-11】判断奇偶数。判断奇偶数，只要根据最未位是0还是1来决定，为0就是偶数，为1就是奇数。因此可以用if (a & 1 = 0)代替if (a % 2 = 0)来判断a是不是偶数。57第10 章 位运算任务分析：（1）首先将整数num要取出的从右端开始的49位移到最右端，即将num右移4位。可以用下面的方法实现：num 4。（2）接着设置一个低6位全为1、其余全为0的数，即0 x3f = 63 = 1111112。（3）最后将上面二者进行与运算，即(num 4) & 0 x3f，则求出所要的结果，再按二进制输出。58第10 章 位运算【例10-12】改变符号。变换符号就是正数变成负数、负数变成正数。可以利用求补码的方法（按位取反+1）来处理。如对于-11和11，可以通过下面的变换方法将-11变成11：1111 0101（二进制），取反，为0000 1010（二进制），将其加1，为0000 1011（二进制）。同样可以将11变成-11：0000 1011（二进制），取反，为0000 1010（二进制），将其加1，为1111 0101（二进制）。59第10 章 位运算【例10-13】取绝对值。对于任何数，与0异或都会保持不变，与-1即0 xFFFFFFFF异或就相当于取反。因此，a与i异或后再减i（因为i为0或-1，所以减i即是要么加0要么加1），也可以得到绝对值。60第10 章 位运算【例10-14】高低位互换。给出一个32位的无符号整数。称这个二进制数的前16位为“高位”，后16位为“低位”。现在写一程序将它的高低位交换。例如，数0 x1234ABCD用二进制表示为：0001 0010 0011 0100 1010 1011 1100 1101将它的高低位进行交换，我们得到了一个新的二进制数：1010 1011 1100 1101 0001 0010 0011 0100它即是0 xABCD1234。这个问题用位操作解决起来非常方便，设x=0 x1234ABCD，由于x为无符号数，右移时会执行逻辑右移，即高位补0，因此x右移16位将得到0000 0000 0000 0000 0001 0010 0011 0100。而x左移8位将得到0000 0000 0000 0000 1010 1011 1100 1101。可以发现只要将x 16与x 1) | (n & 055555555) 2 ) | (n & 0 x33333333) 4 ) | (n & 0 x0F0F0F0F) 8 ) | (n & 0 x00FF00FF) 16 ) | (n & 0 x0000FFFF) 16) = 0) count = count + 16; n = n 24) = 0) count = count + 8; n = n 28) = 0)71第10 章 位运算 count = count + 4; n = n 30) = 0) count = count + 2; n = n 31) = 0) count = count + 1; n = n 1 ) + (n & 0 x55555555); n = (n & 0 xCCCCCCCC) 2 ) + (n & 0 x33333333); n = (n & 0 xF0F0F0F0) 4 ) + (n & 0 x0F0F0F0F); n = (n & 0 xFF00FF00) 8 ) + (n & 0 x00FF00FF); n = (n & 0 xFFFF0000) 16 ) + (n & 0 x0000FFFF); return n;77第10 章 位运算1位运算是语言的一种特殊运算功能，它是以二进制位为单位进行运算的。位运算符只有逻辑运算和移位运算两类。位运算符可以与赋值符一起组成复合赋值符。如&=，|=，=，=，=等。2利用位运算可以完成汇编语言的某些功能，如置位，位清零，移位等。还可进行数据的压缩存储和并行运算。3域在本质上也是结构类型，不过它的成员按二进制位分配内存。其定义、说明及使用的方式都与结构相同。4位域提供了一种手段，使得可在高级语言中实现数据的压缩，节省了存储空间，同时也提高了程序的效率。小 结
