Python 的位元運算

如果你嘗試過 Python 的位元運算, 可能會感到有點困惑, 比如說：

>>> bin(4)
'0b100'
>>> ~4
-5
>>>

咦, 4 的 2 進位表示是 0b100, 那 ~ (not) 運算不就應該是 0b011, 是 3 嗎？既然結果怪怪的, 那我們看一下 ~5 的 2 進位表示好了：

>>> bin(~5)
'-0b101'
>>>

不看還好, 一看更怪了, 這個表示法怎麼跟我想像的不一樣？

Python 的整數沒有止盡

其實是這樣的, Python 的整數沒有限制, 端看你電腦的記憶體有多大, 因此雖然 Python 的整數是採用 2 的補數來表示, 但是要想像左邊有無限多個正負號位元, 以剛剛的 4 為例, 你要想像它是：

0b0000000...0000100

不過實際上要進行位元運算, 我們只要在左側多擺一個正負號位元即可, 所以 4 要表示成：

補上正負號位元
  |
  V
0b0 100

把它當成是一個 4 位元的有號整數, 再進行 ~ 運算, 就會是：

這是正負號位元
  |
  v
0b1 011

由於是以 2 的補數表示, 而且正負號位元是 1, 表示是負數, 所以只要減 1 後再做一次反向運算, 就可以得到該數的絕對值了：

這是正負號位元
   |
   v
 0b1 011  以 2 的補數表示的負數
-      1  減 1 
--------
~0b1 010  反向
--------
 0b0 101  得到 5, 所以原負數是 -5

這個負數的絕對值是 5, 所以原來的負數就是 -5, 因此得到 ~4 的結果是 -5 沒錯。

我們可以進一步測試：

>>> 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() 內建函式顯示 2 進位結果時, 負數的奇怪表示法嗎？

>>> bin(-5)
'-0b101'
>>>

它並不是顯示實際上以 2 的補數表示的結果, 而是以 Python 中書寫 2 進位整數的格式顯示, 也就是開頭加上正負號, 0b 之後是以 2 進位表示該整數的絕對值, 例如：

>>> -0b101
-5
>>>

使用格式化字串的 'b' 轉換規格也可以得到一樣的結果：

>>> "{: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 進位表示：
   

   >>> 0b1111 & -5
   11
   >>> bin(0b1111 & -5)
   '0b1011'
   >>>
   

   注意 bin() 顯示的是 Python 書寫 2 進位整數的格式, 所以不會顯示左側代表正負號位元的 0。

取得整數佔用的位元數

如果想要將上述過程寫成一個函式, 就必須先知道佔用的位元數, 還好整數物件就有 bit_length() 可以提供這項資訊, 例如：

>>> (4).bit_length()
3
>>> (-5).bit_length()
3
>>>

要注意的是, 它提供的是整數絕對值佔用的位元數, 不含正負號位元, 所以實際佔用的位元數要多加 1 位。因此, 若是要得到相同位元數, 但每一個位元都是 1 的正整數, 可以這樣計算：

>>> (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 的補數正確顯示整數的函式就可以寫成：

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

實際用程式試看看：

>>> bin2(~(-9))
'0b01000'
>>> ~(-9)
8
>>>

表示 bin2() 函式的結果是正確的。

小結

很多時候我們不會注意到小細節, 但是一旦遇到奇怪的結果時, 往往會被弄得暈頭轉向, 希望本文能夠讓大家更清楚 Python 的整數以及位元運算, 同時我們也設計了一個簡單的函式, 可以顯示負數實際的 2 進位表示內容, 希望可以對大家有幫助。