10/23 preTraining
位元運算是對二進位的 0 和 1 做一些處理,然後會出現一些性質和用途。
二進位理所當然就只有 true(1) 跟 false(0),以下是位元運算示範操作
AND運算: OR運算:
0 & 0 0 0 | 0 0
0 & 1 0 0 | 1 1
1 & 0 0 1 | 0 1
1 & 1 1 1 | 1 1
XOR運算(⊕): NOT運算:
0 ^ 0 0 !0 1
0 ^ 1 1
1 ^ 0 1 !1 0
1 ^ 1 0
因為 XOR 太多常用性質,所以特別拿出來講。
先來幾個基本原則(bitwise xor 的符號一樣用 ⊕):
C++程式裡使用"<<"與">>"來表示,表示為位元左移(右移)一格
左移時最左邊會補上 0
而右移時最右邊位元會被移除
9=1001 9<<1 = 10010 = 18 15=1111 15>>1 = 111 = 7 常見用法 (x>>1) 快速除2 以及 (x<<1) 和 (x<<1)|1 左子節點和右子節點
C++程式裡使用 "~" 來表示,補數運算為逐位元取反
顛倒一個變數的每個位元的 0 和 1
~0=-1 ~1=-2 常見用法(位元優化dp 總有一天會遇到) 15 & ~(1 << 1) = 13 //將第2個bit設為0 8 |(1 << 2) = 12 //將第3個bit設為1
if (status)
while (status)
for ( ; status ; )
以上的 status 都是非 0 就是 true,也就是裡面都是布林值
所以可以常常看到這種寫法
if(array[x]){ //若array[x]的值非零即會進入"True" cout<<"True"; } else{ //只有再array[x]==0的時候才會進入這邊 cout<<"False"; } while(x){ //當x不是0的時候就不會跳出迴圈 x--; cout<<x<<endl; }
規律性質
例題: [CPE例題]
詢問 x~y 中所有的數字轉換成二進制後有幾個 1
而當你把位元攤開來之後
0 : 0 0 0 0
1 : 0 0 0 1
2 : 0 0 1 0
3 : 0 0 1 1
4 : 0 1 0 0
5 : 0 1 0 1
6 : 0 1 1 0
7 : 0 1 1 1
8 : 1 0 0 0
每個bit拆開來即可發現規律
1 最低的'1'位元
x & -x
根據二的補數,-x 為 ~x + 1。因此在這先將 -x 拆開為 ~x + 1 來討論。
x 中最低位的位元 1 經過 not 運算後,將在 ~x 中變為最低位的位元 0。
因此對 ~x 加上 1 後,最低位的位元 0 重新變為位元 1,且其後的位元都將被設定為 0。
2 檢查冪次
是否為二的冪次
(x & -x) == x
由於若你為二的冪次,則該數字只會有一個位元(也是最高位元)
練習 1 –- XOR 練習
x^=y^=x^=y
請問 x,y 各為多少?(用 x 跟 y 表示)
拆開來看即為
x = x ^ y; y = y ^ x; x = x ^ y;
答案為 x 為 y ,y 為 x (相等於 swap ( x , y ))
練習 2 –- 優先級的練習
cout<<(15>>1+2);
cout<< ( 15 >> 1 + 2 );
ans : 1
大多數的位元運算子的運算優先級都比較低,
因此此題的計算過程為 1 + 2 = 3 , 15(1111) >> 3 = 1.
所以你不確定優先級的時候最好都要加括號
練習 3 –- 常用的技巧
if(x & 1) return 1; else return 0;
return (x & 1);
if(x&1) return 1;//(奇數) else return 0;//(偶數)
判斷 x 的奇偶性 也是常見用法 (比較快)
由於一個數字的位元組成都是 2 的冪次方
因此 \(2^n\) 只有在 n==1 的時候會影響到數字的奇偶性,
故只需要判斷最後一個位元
原本我們在計算 \(x^y\) 的時候呢,有一個最直觀且簡短的寫法,就是跑一個時間複雜度為 \(O(y)\) 的迴圈
int ans=1; for(int i=1;i<=y;i++){ ans*=x; } cout<<ans<<"\n";
但是如果今天 \(y\) 太大的時候,就會需要優化這個程式,需要讓他更快速的解決這個問題,於是就衍生出了快速冪的這個算法。
先把 y 換成二進位
以 \(2^{13}\) 為例
\(13\)
\(= 1101\)
\(= 1\cdot 2^3 + 1\cdot 2^2 + 0\cdot 2^1 + 1\cdot 2^0\)
\(= 8 + 4 + 1\)
\(\to 2^{13} = 2^8 * 2^4 * 2^1\)
因此,我們只要求出 \(2^8, 2^4, 2^1\) 就好
也就是只需要求出每個目標的二的冪次在做相加,也就是 \(\log N\) 次
一樣以 \(2^{13}\) 為例
\(1101\) 就從最右邊的 bit 開始
判斷最右邊的 bit 是不是 \(1\) 如果是 \(1\) 則把答案乘上去
接著每次把 \(x\) 平方
接著把整個右移一個,變成 \(110\)
因此一樣變成判斷最右邊的 bit 即可
\(再右移\to 11\)
\(再右移\to 1\)
一直做到 y 右移到 0 為止
x | y | 原本答案 | 計算後答案 |
---|---|---|---|
\(2^1\) | 1101 | \(2^0\) | \(2^1\) |
\(2^2\) | 110 | \(2^1\) | \(2^1\) |
\(2^4\) | 11 | \(2^1\) | \(2^5\) |
\(2^8\) | 1 | \(2^5\) | \(2^{13}\) |
long long mypow(long long x,long long y){ long long ans = 1; while(y){ if( y&1 ) ans = ans * x; x = x * x; //每次把自己平方 y >>= 1; //每次右移一格 } return ans; }
如果數字太大的話,很有可能會超過 long long 的範圍
因此許多題目會要我們把結果 mod 一個數字
const ll MOD = 1e9 + 7; long long mypow(long long x,long long y){ long long ans = 1; while(y){ if( y&1 ) ans = (ans * x) % MOD; x = (x * x) % MOD; //每次把自己平方 y >>= 1; //每次右移一格 } return ans; }
為什麼我們在實作的過程中可以邊 mod 邊乘?
在 \((A \times B) \% m\) 的情況下
\(A = (C_1 \times m) + R_1\), \(B = (C_2 \times m) + R_2\)
\((A \times B) \% m = ((C_1 \times m) \times (C_2 \times m)) +((C_1 \times m) \times R_2) +((C_2 \times m) \times R_1)\)
\(+ (R_1 \times R_2) \% m\)
我們可以發現上方的一行皆可以被 \(m\) 整除,因此我們得到這樣的結論
\((A \times B) \% m = ((A \% m) \times (B \% m)) \% m\)
換成 2 進位,只需要計算 \(\log y\) 次
當要計算 \(x^y\) ,\(y\) 到 \(10^{18}\) 的時候
\(\log 10^{18} = 60\)
只需做 60 次就可以算出 \(x 的 10^{18}\) 次方