###### tags: `Python`
# Python 的位元運算
如果你嘗試過 Python 的[位元運算](https://docs.python.org/3/library/stdtypes.html?highlight=bit_length#bitwise-operations-on-integer-types), 可能會感到有點困惑, 比如說：
```python
>>> bin(4)
'0b100'
>>> ~4
-5
>>>
```
咦, 4 的 2 進位表示是 0b100, 那 `~` (not) 運算不就應該是 0b011, 是 3 嗎？既然結果怪怪的, 那我們看一下 ~5 的 2 進位表示好了：
```python
>>> bin(~5)
'-0b101'
>>>
```
不看還好, 一看更怪了, 這個表示法怎麼跟我想像的不一樣？
## Python 的整數沒有止盡
其實是這樣的, Python 的整數沒有限制, 端看你電腦的記憶體有多大, 因此雖然 Python 的整數是[採用 2 的補數](https://docs.python.org/3/reference/datamodel.html#index-10)來表示, 但是要想像左邊有無限多個正負號位元, 以剛剛的 4 為例, 你要想像它是：
```
0b0000000...0000100
```
不過實際上要進行位元運算, 我們只要[在左側多擺一個正負號位元](https://docs.python.org/3/library/stdtypes.html?highlight=bit_length#bitwise-operations-on-integer-types)即可, 所以 4 要表示成：
```
補上正負號位元
|
V
0b0 100
```
把它當成是一個 4 位元的有號整數, 再進行 `~` 運算, 就會是：
```
這是正負號位元
|
v
0b1 011
```
由於是以 [2 的補數](https://zh.wikipedia.org/wiki/%E4%BA%8C%E8%A3%9C%E6%95%B8)表示, 而且正負號位元是 1, 表示是負數, 所以只要減 1 後再做一次反向運算, 就可以得到該數的絕對值了：
```
這是正負號位元
|
v
0b1 011 以 2 的補數表示的負數
- 1 減 1
--------
~0b1 010 反向
--------
0b0 101 得到 5, 所以原負數是 -5
```
這個負數的絕對值是 5, 所以原來的負數就是 -5, 因此得到 ~4 的結果是 -5 沒錯。
我們可以進一步測試：
```python
>>> 4 & ~4
0
>>> 4 | ~4
-1
>>>
```
這是因為：
```
幫 4 (0b100) 補上的正負號位元
|
______|______
| |
v v
0b0 100 0b0 100 4
& 0b1 011 | 0b1 011 ~4 (-5)
--------- ---------
0b0 000 0b1 111 以 2 的補數表示的負數
- 1 減 1
---------
~ 0b1 110 反向
---------
0b0 001 原負數是 -1
```
## 用 2 的補數表示負的整數
還記得剛剛使用 [`bin()`](https://docs.python.org/3/library/functions.html#bin) 內建函式顯示 2 進位結果時, 負數的奇怪表示法嗎？
```python
>>> bin(-5)
'-0b101'
>>>
```
它並不是顯示實際上以 2 的補數表示的結果, 而是以 Python 中書寫 2 進位整數的格式顯示, 也就是開頭加上正負號, 0b 之後是以 2 進位表示該整數的絕對值, 例如：
```python
>>> -0b101
-5
>>>
```
使用格式化字串的 'b' 轉換規格也可以得到一樣的結果：
```python
>>> "{:b}".format(-5)
'-101'
>>> "{:#b}".format(-5)
'-0b101'
>>>
```
可是若是要進行位元運算, 我們其實比較想知道實際上以 2 的補數表示的結果。要做到這件事, 我們可以利用剛剛所學, 只要使用一個和要顯示的負數佔相同位元數, 但所有位元都是 1 的正整數和該負數先進行 `&` 運算, 由於會在左側補上正負號位元, `&` 運算後就可以得到一個保留原來負數個別位元的正整數, 再用 `bin()` 即可顯示實際以 2 進位表示的結果了。以 -5 為例, 剛剛描述的過程就是：
1. 取得 -5 佔用的位元數：
```
-5 -> 0b1011 佔 4 個位元
```
2. 使用 4 個位元但所有位元都是 1 的正整數, 也就是 0b1111 和 -5 進行 & 運算, 這會在 0b1111 左側多加一個正負號位元並填上 0 變成 5 個位元的正整數；而 -5 因為是負數, 原來的正負號位元是 1, 所以同一位置多加的正負號位元也要填 1 才會維持是負數：
```
多加一個正負號位元
|
V
0b0 1111 相同位元數但全是 1 的正整數
& 0b1 1011 -5 (左側捕的正負號位元要填 1)
----------
0b0 1011 變成 +11
```
3. 再用 `bin()` 顯示 2 進位表示：
```python
>>> 0b1111 & -5
11
>>> bin(0b1111 & -5)
'0b1011'
>>>
```
注意 `bin()` 顯示的是 Python 書寫 2 進位整數的格式, 所以不會顯示左側代表正負號位元的 0。
## 取得整數佔用的位元數
如果想要將上述過程寫成一個函式, 就必須先知道佔用的位元數, 還好整數物件就有 [`bit_length()`](https://docs.python.org/3/library/stdtypes.html?highlight=bit_length#int.bit_length) 可以提供這項資訊, 例如：
```python
>>> (4).bit_length()
3
>>> (-5).bit_length()
3
>>>
```
要注意的是, 它提供的是整數絕對值佔用的位元數, 不含正負號位元, 所以實際佔用的位元數要多加 1 位。因此, 若是要得到相同位元數, 但每一個位元都是 1 的正整數, 可以這樣計算：
```python
>>> (1 << ((4).bit_length() + 1)) - 1
15
>>> bin((1 << ((4).bit_length() + 1)) - 1)
'0b1111'
>>> (1 << ((-5).bit_length() + 1)) - 1
15
>>> bin((1 << ((-5).bit_length() + 1)) - 1)
'0b1111'
```
## 撰寫以 2 的補數表示整數的函式
有了以上的基礎, 可以 2 的補數正確顯示整數的函式就可以寫成：
```python
>>> def bin2(x):
... bits = x.bit_length() + 1 # 計算位元數
... n = (1 << bits) - 1 # 相同位元數全為 1 的數
... x2 = n & x # & 運算
... if x < 0:
... return f"{x2:#{bits+2}b}" # 2 進位表示
... else:
... return f"{x2:#0{bits+2}b}" # 正數補上正負號位元
>>>
>>> bin2(5)
'0b0101'
>>> bin2(-5)
'0b1011'
>>> bin2(-9)
'0b10111'
>>>
```
我們特別改用格式化字串為正數也加上正負號位元, 以便能清楚區別正負數。我們用 `~(-9)` 來驗證結果到底正不正確：
```
正負號位元
|
v
~0b1 0111
---------
0b0 1000 -> 8
```
實際用程式試看看：
```python
>>> bin2(~(-9))
'0b01000'
>>> ~(-9)
8
>>>
```
表示 `bin2()` 函式的結果是正確的。
## 小結
很多時候我們不會注意到小細節, 但是一旦遇到奇怪的結果時, 往往會被弄得暈頭轉向, 希望本文能夠讓大家更清楚 Python 的整數以及位元運算, 同時我們也設計了一個簡單的函式, 可以顯示負數實際的 2 進位表示內容, 希望可以對大家有幫助。
Sign in with Wallet
Connect another wallet