Python 的位元運算
Tags: python
Published: 2022-03-21 16:13:00

如果你嘗試過 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 進位表示內容, 希望可以對大家有幫助。