搜索
高等教育出版社第10单元位运算及标准模板库作者：林厚从信息学奥赛课课通（C++）高等教育出版社信息学奥赛课课通（C++）第1课位运算学习目标1.理解与掌握C++中的位运算。2.灵活应用位运算优化程序。高等教育出版社信息学奥赛课课通（C++）任何信息在计算机中都是采用二进制表示的，数据在计算机中是以补码形式存储的，位运算就是直接对整数在内存中的二进制位进行运算。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。同时，一个整数的各个二进制位互不影响，利用位运算的一些技巧可以帮助我们简化程序代码。高等教育出版社信息学奥赛课课通（C++）1.位运算符C++提供了按位与（&）、按位或（|）、按位异或（^）、取反（~）、左移（）、右移（）这6种位运算符。这些运算符只能用于整型操作数，即只能用于带符号或无符号的char、short、int与long类型。高等教育出版社信息学奥赛课课通（C++）1.位运算符（1）按位与（&）“a&b”是指将参加运算的两个整数a和b，按二进制位进行“与”运算。如果两个相应的二进制位数字都为１，则该位的结果为1；否则为0。这里的1可以理解为逻辑中的true,0可以理解为逻辑中的false。“按位与”其实与逻辑上“与”的运算规则一致。高等教育出版社信息学奥赛课课通（C++）1.位运算符（2）按位或（|）“a|b”是指将参加运算的两个整数a和b，按二进制位进行“或”运算。如果两个相应的二进制位数字有一个为１，则该位的结果为1；否则为0。“按位或”其实与逻辑上“或”的运算规则一致。高等教育出版社信息学奥赛课课通（C++）1.位运算符（3）按位异或（^）“a^b”是指将参加运算的两个整数a和b，按二进制位进行“异或”运算。如果两个相应的二进制位数字不相同，则该位的结果为1；否则为0。高等教育出版社信息学奥赛课课通（C++）1.位运算符（4）取反（~）“~a”是指将整数a的各个二进制位都取反，即1变为0，0变为1。“~”是一元运算符。高等教育出版社信息学奥赛课课通（C++）1.位运算符（5）左移（）“ab”是指将整数a的各个二进制位左移b位，高位丢弃，低位用0补齐。需要注意的是b必须是非负整数。在高位没有1丢弃的情况下，a1相当于a*2。高等教育出版社信息学奥赛课课通（C++）1.位运算符（6）右移（）“ab”是指将整数a的各个二进制位右移b位，低位丢弃。对于无符号数，高位补0。对于有符号数，某些机器将对左边空出的部分用符号位填补（即“算术移位”），而另一些机器则对左边空出的部分用0填补（即“逻辑移位”）。同样，b必须是非负整数。a1相当于a/2。高等教育出版社信息学奥赛课课通（C++）1.位运算符位运算符也可以与赋值运算符组成复合运算符。例如a&=b相当于a=a&b，a=2相当于a=a2。位运算符也是有优先级的，“~”的运算优先级高于“乘除”而与“！”、“++”、“--”一致，“”和“”的运算优先级低于“加减”，“&”的运算优先级低于“关系运算”而高于“^”,“^”的优先级高于“|”，而“|”的优先级高于“&&”和“||”。为了避免出错，增强程序的可读性，利于调试，建议在需要的地方添加括号来保证优先运算。比如15-1，建议写成1(5-1)，等价于14。高等教育出版社信息学奥赛课课通（C++）2.位运算应用举例位运算的应用场合非常广泛，如高效代替布尔型数组，表示集合、搜索算法中的状态判重（hash）、动态规划算法中的状态压缩等。高等教育出版社信息学奥赛课课通（C++）例1、阅读程序，写出程序的运行结果，体会位运算的思想。//p10-1-1#includebits/stdc++.husingnamespacestd;intmain(){intx=3,y=8,z;x^=y;y^=x;x^=y;coutx““yendl;z=(x&y)+((x^y)1);coutzendl;return0;}高等教育出版社信息学奥赛课课通（C++）例2、整数幂判断一个数n是不是2的整数幂，比如64=26，所以输出“yes”，而65无法表示成2的整数幂形式，所以输出“no”。n在int范围以内。【问题分析】我们考虑一个数如果是2的整数幂会有什么特殊性。观察发现64转换成二进制为01000000，只有一个位是1。将这个数减去1，就变成00111111的形式，我们将这2个数做按位与运算，发现结果为0。分析发现，如果一个数不能表示成2的整数幂形式，则以上过程的运算结果一定不为0。所以，可以利用位运算将算法的时间复杂度优化成O(1)。高等教育出版社信息学奥赛课课通（C++）//p10-1-2b#includebits/stdc++.husingnamespacestd;intmain(){intn;cinn;if(n&(n-1))cout“no“endl;elsecout“yes“endl;return0;}高等教育出版社信息学奥赛课课通（C++）例3、找数【问题描述】给出n个整数，n为奇数，其中有且仅有一个数出现了奇数次，其余的数都出现了偶数次。用线性时间复杂度、常数空间复杂度找出出现了奇数次的那个数。【输入格式】第一行一个整数n，1≤n≤5×106。接下来n行，每行一个数。【输出格式】输出一行一个整数，表示出现了奇数次的那一个数。【输入样例】9331242554【输出样例】1高等教育出版社信息学奥赛课课通（C++）【问题分析】从头到尾“异或”一遍，最后得到的那个数就是出现了奇数次的数。这是因为异或有一个神奇的性质：两次异或同一个数，结果不变。再考虑“异或”运算满足交换律，先异或、后异或都是一样的，因此这个算法显然正确。参考程序见教材510-511页。高等教育出版社信息学奥赛课课通（C++）实践巩固高等教育出版社信息学奥赛课课通（C++）第2课vector学习目标1.了解C++的标准模板库。2.掌握vector容器的使用方法。高等教育出版社信息学奥赛课课通（C++）标准模板库（StandardTemplateLibrary，STL）C++功能强大，为开发者提供了标准模板库，其中封装了很多实用的容器。容器可以理解成能够实现很多功能的系统函数，或者说用来存放数据的对象，开发者可以根据接口规范（调用格式）直接调用，而不用关心其内部实现的原理和具体代码，十分方便快捷。常见的容器有vector、stack、queue、map、set等。高等教育出版社信息学奥赛课课通（C++）vectorvector直接翻译为“向量”，一般说成“变长数组”，也即“长度根据需要而自动改变的数组。在信息学竞赛中，有些题目需要定义很大的数组，这样会出现“超出内存限制”的错误。比如，如果一个图的顶点太多，使用邻接矩阵就会超出内存限制，使用指针实现邻接表又很容易出错，而使用vector实现简洁方便，还可以节省存储空间。使用vector，首先需要添加vector头文件，即#includevector，同时，必须要有“usingnamespacestd”。高等教育出版社信息学奥赛课课通（C++）1.vector的定义定义一个vector的方法如下：vectortypenamename;以上定义相当于定义了一个一维数组name[size]，只是size不确定，其长度可以根据需要而变化。其中typename可以是任何基本类型，例如int、double、char、结构体等，也可以是STL标准容器，例如vector、queue等。高等教育出版社信息学奥赛课课通（C++）访问vector中的元素一般有两种方式。第一种是通过“下标”访问。例如，对于容器vectorintv，可以使用v[index]来访问它的第index个元素。其中，0≤index≤v.size()-1，v.size()表示vector中元素的个数。第二种方式是通过“迭代器”访问。可以将迭代器（iterator）理解为一种类似指针的变量。其定义为：vectortypename::iteratorit;2.vector的访问例如：vectorint::iteratorit=v.begin();for(inti=0;i=5;i++)printf(%d,*(it+i));高等教育出版社信息学奥赛课课通（C++）3.vector的常用函数（1）push_back()push_back(x)用来在vector后面添加一个元素x，时间复杂度为0(1)。（2）size()如果是一维数组，size()用来获得vector中元素的个数；如果是二维数组，size()用来获得vector中第二维的元素个数，时间复杂度为0(1)。（3）pop_back()pop_back()用来删除vector的尾元素，时间复杂度为0(1)。高等教育出版社信息学奥赛课课通（C++）3.vector的常用函数（4）clear()clear()用来清空vector中的所有元素，时间复杂度为0(n)，其中n为vector中元素的个数。（5）insert()insert(it，x)用来向vector任意迭代器it处插入一个元素x，时间复杂度为0(n)。（6）erase()erase()用来删除vector中的元素，有两种用法。一种是erase(it)，删除迭代器it处的元素；另一种是erase(first，last)，删除左闭右开区间[first，last)内的所有元素。高等教育出版社信息学奥赛课课通（C++）4.vector的应用举例例1、中间数【问题描述】依次读入若干正整数，如果是奇数个就输出最中间的那个数；否则，输出中间两个数的和。以0作为结束标志，但0不计数。【问题分析】参考程序见教材516-517页。高等教育出版社信息学奥赛课课通（C++）例2、上网统计【问题描述】在一个网络系统中有N个用户、M次上网记录。每个用户可以自己注册一个用户名，每个用户名是一个只含小写字母且长度小于1000的字符串。每个上网的账号每次上网都会浏览网页，网页名是以一个只含小写字母且长度小于1000的字符串，每次上网日志里都会有记录，现在请统计每个用户每次浏览了多少个网页。【输入格式】第1行包含两个用1个空格隔开的正整数N（1≤N≤1000）和M（1≤M≤5000）。第2~M+1行，每行包含2个用1个空格隔开的字符串，分别表示用户名和浏览的网页名。【输出格式】共N行，每行的第一个字符串是用户名，接下来的若干字符串是这个用户依次浏览的网页名（之间用一个空格隔开）。按照用户名出现的次序排序输出。高等教育出版社信息学奥赛课课通（C++）【输入样例】57goodstudyerbookshopalikespaceaspacewebgoodstudyerbookshopblikespacebspaceweblikespacecspaceweblikespaceajuiceshopgameplayergameweb【输出样例】goodstudyerbookshopabookshopblikespaceaspacewebjuiceshoplikespacebspaceweblikespacecspacewebgameplayergameweb高等教育出版社信息学奥赛课课通（C++）【问题分析】由于用户名和浏览的网页名长度不固定，用vector解决比较方便，可以分别通过“下标”访问和“迭代器”访问。参考程序见教材517-519页。高等教育出版社信息学奥赛课课通（C++）例3、蛇形方阵【问题描述】输入n，n≤100，输出n阶蛇形方阵。例如n=5时，输出如下：12671535814164913172210121821231119202425【问题分析】定义一个二维数组，模拟蛇形方阵填数的过程。具体程序参见教材520页。高等教育出版社信息学奥赛课课通（C++）实践巩固高等教育出版社信息学奥赛课课通（C++）