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