位运算及其对程序的优化ppt.ppt
《位运算及其对程序的优化ppt.ppt》由会员分享,可在线阅读,更多相关《位运算及其对程序的优化ppt.ppt(25页珍藏版)》请在三一办公上搜索。
1、位运算及其对程序的优化,常州市第一中学 戴涵俊,序言,程序中所有的数据在计算机内存中都是以二进制的形式储存的。位运算,本质上就是直接对整数在内存中的二进制位进行运算,同时,数的各个二进制位互不影响。由于位运算直接对内存数据进行操作,不需要转换成十进制,因此处理速度非常快,在信息学竞赛中往往可以优化理论时间复杂度的系数。另外,位运算还有很多特殊的技巧,能够帮助我们简化代码、美化程序等等。本文就结合自己的学习和应用经验,介绍一些位运算及其对程序的优化方法。,正文,一、位运算的基本操作,二、位运算的实用技巧,三、位运算对一些数据结构的优化,四、位运算对一些算法的优化,一、位运算的基本操作,位运算主要
2、有and,or,xor,not,shl,shr我们不妨通过一下的真值表来了解它们的运算法则,Shl:左移,就是把二进制数整体向左移动x个位,右边x位补成0Shr:右移,就是把二进制数整体向右移动x个位,原来高位的x个变成0,相当于div 2。,1.位运算介绍,由上面的介绍,我们不难发现这些位运算的基本用途:,and主要是用来取出某一个二进制位,or主要是用来强行给二进制的某一位赋值,xor运算通常用来取反,not操作就是直接把内存中的0和1全部取反,2.位运算的优先级,not and,shl,shr or,xor,比如以下几个运算,你能很快报出结果吗?not 1 or 1 not 1 and
3、1 1 and 1 shl 1 not 1 or 0 shl 1 xor 0 and 1=,1,0,2,2,3.例题,例1、一个文件中有9亿个不重复的9位整数,现在要求对这个文件进行排序(当然时间可以不止1秒,但要求出可行解,即在可以接受的时间和空间范围内)。,001101100110001110,4出现了,14没有出现,二、位运算的实用技巧,1.对于mod运算的优化,mod版本:for i:=1 to time do x:=y mod base;and 版本:for i:=1 to time do x:=y and(1 shl 20-1);,2.位运算的一些技术,三、位运算对一些数据结构的优
4、化,1.循环队列,2.树状数组,循环队列比较方便的实现可以用一个头指针head,一个尾指针tail,每次取出来的是head mod base。这里不妨把base设置为2的整数次幂1,然后用and来取模。,低位技术(Lowbit)Li:=i and(i xor(i-1)。,3.集合,例题,例2.尼克在一家养猪场工作,这家养猪场共有M间锁起来的猪舍,由于猪舍的钥匙都给了客户,所以尼克没有办法打开这些猪舍,客户们从早上开始一个接一个来购买生猪,他们到达后首先用手中的钥匙打开他所能打开的全部猪舍,然后从中选取他要买的生猪,尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中,每个猪舍能存放的猪的数
5、量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。好在尼克事先知道每位客户手中有哪些钥匙,要买多少猪,以及客户到来的先后次序。请你写一个程序,帮助尼克求出最多能卖出多少头生猪。,猪舍,客户,s,t,这里用整数来表示猪舍的有无情况,这样最大可以有1000个二进制位,于是还要分段处理。不妨每段用一个64位的qword,把1000总共分成16段,对于每个猪舍编号k,先判断是哪一段的(用(k-1)div 64+1,可以写成shr 6加速),然后再在那一段进行赋值。于是,对于两段猪舍,看有无交集,只需要and一下,看是不是0就可以了。这样,我们把预处理的时间复杂度降到了O(100*100*16)。,
6、例3、某山贼集团在绿荫村拥有强大的势力,整个绿荫村由N个连通的小村落组成,并且保证对于每两个小村落有且仅有一条简单路径相连。小村落用阿拉伯数字编号为1,2,3,4,n,山贼集团的总部设在编号为1的小村落中。山贼集团除了老大坐镇总部以外,其他的P个部门希望在村落的其他地方建立分部。P个分部可以在同一个小村落中建设,也可以分别建设在不同的小村落中。每个分部到总部的路径称为这个部门的管辖范围,于是这P个分部的管辖范围可能重叠,或者完全相同。在不同的村落建设不同的分部需要花费不同的费用。每个部门可能对他的管辖范围内的小村落收取保护费,但是不同的分部如果对同一小村落同时收取保护费,他们之间可能发生矛盾,
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 运算 及其 程序 优化 ppt
链接地址:https://www.31ppt.com/p-5372482.html