位运算及其对程序的优化.ppt

该【位运算及其对程序的优化 】是由【ielbcztwz24384】上传分享，文档一共【25】页，该文档可以免费在线阅读，需要了解更多关于【位运算及其对程序的优化 】的内容，可以使用淘豆网的站内搜索功能，选择自己适合的文档，以下文字是截取该文章内的部分文字，如需要获得完整电子版，请下载此文档到您的设备，方便您编辑和打印。位运算及其对程序的优化
——常州市第一中学 戴涵俊
序言
程序中所有的数据在计算机内存中都是以二进制的形式储存的。位运算，本质上就是直接对整数在内存中的二进制位进行运算，同时，数的各个二进制位互不影响。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。另外，位运算还有很多特殊的技巧，能够帮助我们简化代码、美化程序等等。本文就结合自己的学习和应用经验，介绍一些位运算及其对程序的优化方法。
01
正文
02
位运算的基本操作
03
位运算的实用技巧
04
位运算对一些数据结构的优化
05
位运算对一些算法的优化
一、位运算的基本操作
X
Y
X and Y
X or Y
X xor Y
not X
0
0
0
0
0
1
0
1
0
1
1
1
1
0
0
1
1
0
1
1
1
1
0
0
位运算主要有and ，or，xor，not，shl，shr我们不妨通过一下的真值表来了解它们的运算法则——
Shl：左移，就是把二进制数整体向左移动x个位，
右边x位补成0
Shr：右移，就是把二进制数整体向右移动x个位，
原来高位的x个变成0，相当于div 2。

01
由上面的介绍，我们不难发现这些位运算的基本用途：
02
and主要是用来取出某一个二进制位
03
or主要是用来强行给二进制的某一位赋值
04
xor运算通常用来取反
05
not操作就是直接把内存中的0和1全部取反
not > and , shl ,shr > or,xor
比如以下几个运算，你能很快报出结果吗？
not 1 or 1 ＝
not 1 and 1 ＝
and 1 shl 1 ＝
not 1 or 0 shl 1 xor 0 and 1 =
1
1
2
3
6
5
4
2
2
0


例1、一个文件中有9亿个不重复的9位整数，现在要求对这个文件进行排序（当然时间可以不止1秒，但要求出可行解，即在可以接受的时间和空间范围内）。
4出现了
14没有出现
二、位运算的实用技巧

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);
times
mod
and
10000000


100000000


1000000000



运算要求
用位运算实现
实际应用
把右数第k位强行赋为1
x or (1 shl (k-1))
通过这些操作，我们可以用01表示某个状态并且方便地改变这一状态，在哈希表、状态DP、一些搜索记录状态中很实用
把右数第k位强行赋为0
x and not(1 shl (k-1))
右数第k位取反
x xor (1 shl (k-1))
去掉右起第一个1的左边
x and (x xor (x-1))
树状数组中用到的低位技术
求x和y的平均值下取整
x and y+(x xor y) shr 1
避免x+y超界但结果不超界的情况
求x的相反数（x基类型为有符整型）
not x＋1
更好地理解not以及数在计算机中的存储方式
交换变量x和变量y的值
x:=x xor y; y:=x xor y;
x:=x xor y;
省去交换变量时候需要的临时变量
用位运算取绝对值（以32位整数为例）
x xor (not (x shr 31) + 1) + x shr 31

循环队列比较方便的实现可以用一个头指针head，一个尾指针tail，每次取出来的是head mod base。这里不妨把base设置为2的整数次幂－1，然后用and来取模。

低位技术（Lowbit） L[i]：= i and （i xor （i-1））。
三、位运算对一些数据结构的优化