位元運算 & 快速冪

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運算

因為 XOR 太多常用性質，所以特別拿出來講。
先來幾個基本原則（bitwise xor 的符號一樣用 ⊕）：

1. A ⊕ B = B ⊕ A，(A ⊕ B) ⊕ C = A ⊕ (B ⊕ C)，也就是運算順序不影響結果(有交換律和結合律)。
2. A ⊕ A = 0
3. 若 A ⊕ B = C，則 A ⊕ C = B
4. A ⊕ 0 = A

左移 右移 運算

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\)

原本我們在計算 \(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 為止

過程

程式碼

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 一個數字

加入 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與乘法的交換律

為什麼我們在實作的過程中可以邊 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}\) 次方