夏令营提高班hash与位运算

1、Hash与位运算山东师大附中陈键飞位运算对二进制数的一些操作优化时间常数优化代码长度核心思想将一个二进制串(集合)用一个数表示集合1,2,3,5 (10111)2位运算符and(&)or(|)xor()not()and的应用清零 eg. A and (00011)2取位 eg. A and (00100)2=0?求交集 AB=A and BMod ： A Mod 2n = A and (2n-1)满足交换律、结合律or的应用清零 eg. A or (00011)2求并集 AB=A or B满足交换律、结合律xor的应用把某些位反转 eg. A xor (01110)2求补集CuA=A xor

2、U哈希函数满足交换律、结合律，xor是自己的逆运算A xor B=B xor AA xor (B xor C)=A xor B xor CA xor B xor A=Bshl的应用乘2k ：A shl k青蛙过河：readln(m,n);writeln(m+1)shl n);shr的应用Div 2k ：A shr kmid:=(lb+rb)shr 1;if (leftmid) then search(t shl 1+1,mid+1,rb);小例题缩短代码：集合a是不是集合b的子集？function a( a,b : array1.30of boolean):boolean;var i:long

3、int;beginfor i:=1 to 30 do if ai and not bi then exit(false);exit(true);end;a and b = a例题判断一个01串中有没有两个1相邻？function b( a:array1.30of boolean):boolean;var i:longint;beginfor i:=1 to 29 do if ai and ai+1 then exit(true);exit(false);end;如果是判断是不是有两个0相邻呢?a and (a shr 1) 0 a or (a shr 1) 0 do begininc( pop

4、count , x and 1) ;x := x shr 1 ;end ;end ;O(log x)例题function popcount2( x : longint ) : longint ;begin x := ( x and $55555555 ) + ( (x1) and $55555555 ) ; x := ( x and $33333333 ) + ( (x2) and $33333333 ) ; x := ( x and $0F0F0F0F ) + ( (x4) and $0F0F0F0F ) ; x := ( x and $00FF00FF ) + ( (x8) and $00

5、FF00FF ) ; x := ( x and $0000FFFF ) + ( (x16) and $0000FFFF ) ; exit( x ) ;end ;例题状态压缩的动态规划A包含于B：A and B = AHash状态对一个事物的一个完整的描述比如说集训班有三个人，其中李其乐是神牛，李其刚是神犇，羊驼是李振那么(李其乐=神牛，李其刚=神犇，羊驼=李振)就是一个状态Hash再比如说，昨天所有同学的考试成绩，也是一个状态如果有N个同学，这个状态的大小就是O(N)HashHash函数与Hash表Hash函数：一个状态到一个正整数的映射F(Status)Hash表：将Hash函数按值的大小索

6、引HashHash的应用是多种多样的应用方法上：仅Hash函数，仅Hash表，两者都用应用领域上：广搜的判重，字符串的索引仅用Hash函数在下载时经常用到的MD5：将一个文件映射到一个Hash函数，通过比较MD5校验码判断文件的完整性。仅用Hash函数一个信息学竞赛中的应用实例：Rabin-Karp算法Hash表利用Hash函数值的特殊性，实现高效的插入、删除、查找。典型的空间换时间Hash表若Hash表大小是L，共S个状态插入复杂度O(1),删除和查找O(S/L)对比二叉查找树插入，删除和查找O(log n)Hash表的应用POI2000，Promotion值域缩小版Hash函数和Hash表的综合应用广搜的判重：先将状态映射成Hash函数，再用Hash表插入，查找。广搜+Hash已经成为一种套路，两者是密不可分的Hash函数和Hash表的综合应用字符串的索引生物基元问题：给定字符串S和基元串A1An，求最大的k，使S1.k由基元串组成Hash函数和Hash表的综合应用Fi=Or(Fj) (当且仅当j=i且Sj+1.i是一个基元串)Hash优化决策时间：判断Sj+1.i是不是基元串O(1)一个应用给定n