狠狠撸

Binary number
? 19 10 = 10011 2
? 7 10 = 111 2

AND
? int a = 3 = 011 2
int b = 5 = 101 2
? a & b = 1 = 001 2
011
& 101
--------
= 001

OR
? int a = 3 = 011 2
int b = 5 = 101 2
? a | b = 7 = 111 2
011
| 101
--------
= 111

XOR (Exclusive OR)
? int a = 3 = 011 2
int b = 5 = 101 2
? a ^ b = 6 = 110 2
011
^ 101
--------
= 110

NOT
? 1變0，0變1
? 假設只有4個bit
? a = 3 = 0011 2
~a = 12 = 1100 2

Shift
? 正數 right-shift
a = 11 = 1011 2
a >> 2 = 2 = 0010 2
? 正數 left-shift
a = 11 = 1011 2
a << 2 = 2 = 1100 2

正負號
? 正：0 負：-1
int sign = a >> 31;
? 正：1 負：-1
int sign = 1 | ( a >> 31 );
? 正：1 零：0 負：-1
int sign = ( a != 0 ) | ( a >> 31 );

不同正負號
? 計算幾何判斷相交、凸包…
? 不同正負號：true 同正負號：false
bool diff = ( a ^ b ) >> 31 ;

是不是 2 的冪次
? 例子：8 ? ??? , 7 ? ??
? 正整數
bool result = ( a & ( a – 1 ) ) == 0 ;
? 考慮0
bool result = a && !( a & ( a – 1 ) ) ;

計算有幾個 bit 是 1
? 基礎方法
for( cnt = 0 ; a ; a >>= 1 ) cnt += a & 1 ;
? 查表
cnt = table256[ a & 0xff ] +
table256[ ( a >> 8 ) & 0xff ] +
table256[ ( a >> 16 ) & 0xff ] +
table256[ a >> 24 ];

往上取2的冪次
? 例子： 5 ? 8
? --a ;
a |= a >> 1 ;
a |= a >> 2 ;
a |= a >> 4 ;
a |= a >> 8 ;
a |= a >> 16 ;
++a ;

最右邊的 1
? 也叫 lowbit
? 例子： 010010 2 ? 000010 2
101000 2 ? 001000 2
? lowbit(x) = x & ( -x ) ;

集合
? 有一個由 0, 1, ? , ? ? 1 構成的集合 ?
? 我們可以用一個 ? bit的整數 ? ? 來表示 ?
? 第 ? 個 bit 為 1 代表 ? 在 ? 裡面（從右邊數）
? 例子：
? = 5
? = 0, 2, 3 ? ? ? = 01101 2
?′
= 1, 2, 4 ? ? ?′ = 10110 2

常用的集合
? ?1 = 0, 1, ? , ? ? 1
? ?1
= ( 1 << n ) – 1 ;
? ?2 = ?
? ?2
= 1 << i ;

Set operations
? 給你兩個集合，你可以做一些事
– 聯集 Union
– 交集 Intersection
– 對稱差 Symmetric Difference
– 判斷包含 Inclusion

聯集 Union
? 聯集其實就是在做 bitwise OR
? ? ?∪?′ = ? ? | ? ?′
? 例子：
? = 5
? = 0, 3, 4 ? ? ? = 11001 2
?′
= 0,1,4 ? ? ?′ = 10011 2
? ∪ ?′
= 0,1,3,4
? ? ?∪?′ = 11011 2

交集 Intersection
? 交集其實就是在做 bitwise AND
? ? ?∩?′ = ? ? & ? ?′

對稱差 Symmetric Difference
? 對稱差其實就是在做 bitwise XOR
? ? ?Δ?′ = ? ? ^ ? ?′

判斷包含 Inclusion
? 判斷包含可以看交集以後有沒有變
? ? ? ?′ ? = ? ∩ ?′ = ? ?
bool inc = ? ? & ? ?′ == ? ?;

枚舉子集
? 有時會需要枚舉子集合
? 例子：
? = 0, 1, 3
?, 0 , 1 , 3 , 0,1 , 0,3 , 1,3 , 0,1,3
0000, 0001, 0010, 1000,0011, 1001, 1010, 1011

枚舉子集 - simplified
? 先考慮比較簡單的版本
? 目標：枚舉 ? = 0, 1, ? , ? ? 1 的子集合
? 作法：就是 0 ~ 2 ?
? 1
– 0...000
– 0...001
– 0...010
– 0...011
– ...
– 1...111

枚舉子集 - original
? 目標：枚舉 ? 的子集合
? 有一些用不到的 bit 怎麼辦？那就不要考慮他們！
for ( int sub = sup ; ; sub = ( sub - 1 ) & sup ) {
// do something
if ( sub == 0 ) break ;
}

枚舉子集 2
? 有時需要枚舉大小為 ? 的子集合們
? 例子：
? = 0, 1, 3 , ? = 2
0,1 , 0,3 , 1,3
0011, 1001, 1010

枚舉子集 2 - simplified
? 先考慮 ? = 0, 1, ? , ? ? 1
? 例子：
int lower = ( 1 << k ) - 1, upper = 1 << n ;
for ( int comb = lower ; comb < upper ; ) {
// do something
comb = next_permu( comb ) ;
}

枚舉子集 2 - simplified
? 重點是找出下一個排列，自己畫個圖看看
int next_permu( int p ) {
int x = lowbit( p ), y = p + x ;
return y | ( ( p & ~y ) / x >> 1 ) ;
// or return y | ( ( p & ~y ) >> ( lg( x ) + 1 ) ) ;
}

狠狠撸

Bit Hack

More Related Content

Bit Hack