# Python的位元運算
首先要聲明三點
1. 如果只是要考APCS，使用Python其實**不太需要位元運算**
2. 如果要轉C++的必須要學，原因我不多說
3. 位元運算在更高階的比賽**一定要會**

所謂位元運算，就是對二進制作運算，我們可以從當中得到一些有趣的特性
## AND(&)
在位元運算的and跟一般運算很相似，但是它是針對每一個二進位的數字做and運算
比如我有兩個二進位數字，只要兩個都為 1 就是 1
1111
0101
我們要同時看上跟下的數字，比如第一行，上為 1 下為 0 ，那 1 and 0 就是 0
後面以此類推，最後得到答案就是0101，用十進位表示就是 5

b = 15 # 1111
c = 5  # 0101 用成四位是因為比較好觀察
# b & c  0101 == 答案 == 5
print(b & c) # 0101

## OR(|)
or跟前面的and一樣，都是用相同方式，但是**只要有一個為 1** 答案就是 1

b = 15 # 1111
c = 5  # 0101 用成四位是因為比較好觀察
# b | c  1111 == 答案 == 15
print(b | c) # 1111

## XOR(^)
這個比較少見，或者根本沒見過，其實它就是**只能有一個為 1**
比如說 1 xor 1 就是 0 ，因為有兩個 1 ， 0 跟 0 也是一樣

b = 15 # 1111
c = 5  # 0101 用成四位是因為比較好觀察
# b ^ c  1010 == 答案 == 10
print(b ^ c) # 1010

## not(~)
這個比較難理解，有興趣的可以去查二補數
比如15 (二進位1111)，我們可以看成 01111，然後再做not運算
not運算就跟一般的not一樣， 1 變成 0 ， 0 變成 1
那麼01111 -> 10000 (-16)

c = 15  # 01111 用成五位
# ~c      10000 == 答案 == -16
print(~c) # 10000

## 左移(<<)
這個比較有意思，就是把二進式從右邊多補n個0
比如15(1111)，多加一個0會變成30(11110)
在正整數的時候相當於 × 2^n^

c = 15  # 1111 
# c<<1      11110 == 答案 == 30
print(c<<1) # 11110

## 右移(<<)
這個跟剛剛一樣，但是是把二進式從右邊移除n個數
比如15(1111)，移除一個數會變成7(111)
在正整數的python=時候相當於 // 2^n^

c = 15  # 1111 
# c>>1      111 == 答案 == 7
print(c>>1) # 111

## 實用的性質
介紹完剛剛的運算方式，我們可以得到幾個比較有用的性質
### 判斷奇數偶數
用and運算可以快速判斷，只要跟 1 做and位元運算
那麼只要看最右邊的數字是 1 還是 0 就知道奇數偶數
### A變成-A
用not運算可以快速轉換正負，只要~A+1就會等於-A
### A × 2 或 A // 2
在二分搜的時候常常用到，用左右移就可以達成

a >>= 1 # // 2
a <<= 1 # × 2 

### A B 對調數字
在python當中用 a,b = b,a 就好
如果是C++等比較不方便的語言，通常都是用多一個變數tmp去協助
但是用xor運算能夠省去tmp的運用

a = a^b
b = a^b
a = a^b

如果把它換成二進制就不難理解了
比如下面這個例子
1111 a
0101 b
先做一次 xor 運算
1010 a
0101 b
再做一次 xor 運算
1010 a
1111 b
會發現此時b已經變成a了
最後再做一次位元運算
0101 a
1111 b
a b 就對調了，如果想要徹底理解的話，我有在下面證明，不想看的可以自動忽略
證明 :
首先要知道，xor有五個性質
1. A xor B == B xor A (交換律)
2. A xor B xor C == A xor (B xor C) (結合律)
3. A xor A == 0
4. if A xor B == C -> A xor C == B
5. A xor 0 == A

那麼之前對調的例子就知道
t = a ^ b
b = t ^ b == a ^ b ^ b == a ^ ( b ^ b ) == a ^ 0 == a
a = t ^ b == a ^ b ^ a == ( a ^ a ) ^ b == 0 ^ b == b
所以可以對調

## 練習題
[a621. 1. Powers of Two](https://zerojudge.tw/ShowProblem?problemid=a621)
二進位的運用也就是位元運算的運用

___
本篇到此結束~