位元運算

二進制

要學習位元運算，必須要先學會二進制的數字表示法，
二進制與我們常用的十進制看起來非常不一樣，但核心概念是相同的。

• 二進制與十進制

  二進制與十進制的「進」代表的是進位，而前面的數字代表的是遇到多少要進位，
  十進制是遇到10就進位 看吧！變兩位數了 ，二進制則是遇到2就進位，
  所以其實也有八進制、十六進制等不同的進位方式。

• 數字的位數

  我們如果去觀察一個十進制數字，其實可以發現最右邊(個位數)其實代表的是

  ${10}^0$的數，往左一位(十位數)代表
  ${10}^1$的數，以此類推。

  二進制其實也是如此，但是把10都改成2，
  例如二進制的1001 代表的是

  $1\times 2^3+0\times 2^2+0\times 2^1+1\times 2^0=9$ 。

---

位元

大家應該都知道，電腦儲存資料的方法只有用0和1，而我們將一個儲存0或1的單位稱為位元Bit，又將8個位元合稱為一個位元組Byte。
如果去看資料型態的表格，你可以知道一個整數的記憶體空間是4 bytes，也就是4x8 = 32 bits
其中是用二進制儲存的，而有1 bit要被用來代表正負號，所以實際可以儲存的範圍是

$-2^{31}$~

$2^{31}-1$ 。

---

位元運算子

• NOT運算子 ~

  • 使用方法: ~n

  • 功能: 將一個數字內所有位元的1變成0，0變成1

    	$\cdots$	7	6	5	4	3	2	1	0	值
    n	0	1	0	0	1	1	1	1	0	158
    ~n	1	0	1	1	0	0	0	0	1	-159

• AND運算子 &

  	1	0
  1	1	0
  0	0	0

  • 使用方法: a & b

  • 功能: 將兩個數字內的位元位置對齊做AND邏輯運算(請見上表)

    	$\cdots$	7	6	5	4	3	2	1	0	值
    a	0	1	0	0	1	1	0	1	0	154
    b	0	0	0	1	1	1	0	0	1	57
    a & b	0	0	0	0	1	1	0	0	0	24

• OR運算子 |

  	1	0
  1	1	1
  0	1	0

  • 使用方法: a | b

  • 功能: 將兩個數字內的位元位置對齊做OR邏輯運算(請見上表)

    	$\cdots$	7	6	5	4	3	2	1	0	值
    a	0	1	0	0	1	1	0	1	0	154
    b	0	0	0	1	1	1	0	0	1	57
    a | b	0	1	0	1	1	1	0	1	1	187

• XOR運算子 ^

  	1	0
  1	0	1
  0	1	0

  • 使用方法: a ^ b

  • 功能: 將兩個數字內的位元位置對齊做XOR邏輯運算(請見上表)

    	$\cdots$	7	6	5	4	3	2	1	0	值
    a	0	1	0	0	1	1	0	1	0	154
    b	0	0	0	1	1	1	0	0	1	57
    a ^ b	0	1	0	1	0	0	0	1	1	163

• 右移運算子 >>

  • 使用方法: a >> b

  • 功能: 將數字a內的位元向右推移b格 (左邊正數補0，負數補1，右邊自動丟棄)

    	$\cdots$	7	6	5	4	3	2	1	0	值
    a	0	1	0	0	1	1	0	1	0	154
    a >> 2	0	0	0	1	0	0	1	1	0	38

• 左移運算子 <<

  • 使用方法: a << b

  • 功能: 將數字a內的位元向左推移b格 (右邊自動補0)

    	$\cdots$	7	6	5	4	3	2	1	0	值
    a	0	0	0	0	1	1	0	1	0	26
    a << 2	0	0	1	1	0	1	0	0	0	104

  其實右移運算子 >> 及左移運算子 << 做的事情非常簡單，分別是將數值除以2的i次方(整數除法)以及乘以2的i次方而已，可以思考看看為什麼。

• 應用

  • 判斷奇偶數:

    前面(三元運算子)有稍微帶到判斷奇偶數可以使用 n & 1，不過沒有解釋為什麼，
    現在講到位元運算子就有辦法解釋了，你可以自己先想想看:

    幾個重要的點:
    1的二進制是 00000001 、只要是奇數，最後一個位元必定是1 、AND運算子

    因為1除了

    $2^0$之外，其他都是0，所以AND的結果必定會是0。
    當我們對任何數n做 n & 1 時，只會有
    $2^0$項的區別，
    而且我們知道奇數最後一個位元一定是1、偶數最後一個位元一定是0，
    因此我們可以用n & 1來判斷一個數的奇偶性。

  • 2的i次方:

    我們知道了左移運算子其實就是將數值乘以2，所以只要簡單的用1 << i便可以達到2的i次方的目的。

  • 2147483647(?:

    要做出 2147483647 只要使用 ~(1 << 31) 就可以了，也不會很難理解。

  • 判斷兩數相等:

    a ^ b == 0

  • 兩數互換:

    兩數互換有一種最簡單的方式，是使用:

    ​​​​​​​​int temp = x;
    ​​​​​​​​x = y;
    ​​​​​​​​y = temp;
    

    但是還有一種不需要新變數的單行寫法 (XOR Swap Algorithm) :

    ​​​​​​​​x ^= y ^= x ^= y;
    

    這樣可能不太好理解，我們可以把它拆開來看:

    ​​​​​​​​x ^= y; // x = x ^ y
    ​​​​​​​​y ^= x; // y = y ^ x
    ​​​​​​​​x ^= y; // x = x ^ y
    

    引理:
    XOR 位元運算具有下列性質

    1. 交換律:
       $A\oplus B=B\oplus A$
    2. 結合律:
       $(A\oplus B)\oplus C=A\oplus (B\oplus C)$
    3. 單位元素:
       $A\oplus 0=A$
    4. 元素是自己的反元素:
       $A\oplus A=0$

    1. $X_1=X_0\oplus Y_0$
    2. $Y_1=Y_0\oplus X_1=Y_0\oplus X_0\oplus Y_0=X_0\oplus (Y_0\oplus Y_0)=X_0\oplus 0=X_0$
    3. $X_2=X_1\oplus Y_1=(X_0\oplus Y_0)\oplus X_0=(X_0\oplus X_0)\oplus Y_0=0\oplus Y_0=Y_0$