位运算及其对程序的优化_(免费阅读).ppt

程序中所有的数据在计算机内存中都是以二进制的形式储存的。位运算，本质上就是直接对整数在内存中的二进制位进行运算，同时，数的各个二进制位互不影响。由于位运算直接对内存数据进行操作，不需要转换成十进制，因此处理速度非常快，在信息学竞赛中往往可以优化理论时间复杂度的系数。另外，位运算还有很多特殊的技巧，能够帮助我们简化代码、美化程序等等。本文就结合自己的学习和应用经验，介绍一些位运算及其对程序的优化方法。 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。 由上面的介绍，我们不难发现这些位运算的基本用途： and主要是用来取出某一个二进制位 or主要是用来强行给二进制的某一位赋值 xor运算通常用来取反 not操作就是直接把内存中的0和1全部取反 not and , shl ,shr or,xor 比如以下几个运算，你能很快报出结果吗？ not 1 or 1 ＝ not 1 and 1 ＝ 1 and 1 shl 1 ＝ not 1 or 0 shl 1 xor 0 and 1 = －1 0 2 －2 例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 and0.22s 0.14s 100000000 1.26s 0.52s 1000000000 12.00s 4.23s 运算要求 用位运算实现 实际应用 把右数第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））。 功能 用位运算实现 集合的并、交、差 A or B A and B A and not B 添加/删除某一个元素 A or 1 shl (k-1) ; A and not(1 shl (k-1)) 判断某一元素是否存在 A and (1 shl (k-1)) 是否为0。 为0就是不存在 从A集合中删去B集合 （B集合为A集合的子集） A xor B 例2. 尼克在一家养猪场工作，这家养猪场共有M间锁起来的猪舍，由于猪舍的钥匙都给了客户，所以尼克没有办法打开这些猪舍，客户们从早上开始一个接一个来购买生猪，他们到达后首先用手中的钥匙打开他所能打开的全部猪舍，然后从中选取他要买的生猪，尼克可以在此期间将打开的猪舍中的猪调整到其它开着的猪舍中，每个猪舍能存放的猪的数量是没有任何限制的。买完猪后客户会将他打开的猪舍关上。 好在尼克事先知道每位客户手中有哪些钥匙，要买多少猪，以及客户到来的先后次序。请你写一个程序，帮助尼克求出最多能卖出多少头生猪。 猪舍 客户 s t 这里用整数来表示猪舍的有无情况，这样最大可以有1000个二进制位，于是还要