DEV Community

codemee
codemee

Posted on • Updated on

Python 的位元運算

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

>>> bin(4)
'0b100'
>>> ~4
-5
>>>
Enter fullscreen mode Exit fullscreen mode

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

>>> bin(~5)
'-0b101'
>>>
Enter fullscreen mode Exit fullscreen mode

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

Python 的整數沒有止盡

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

0b0000000...0000100
Enter fullscreen mode Exit fullscreen mode

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

補上正負號位元
  |
  V
0b0 100
Enter fullscreen mode Exit fullscreen mode

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

這是正負號位元
  |
  v
0b1 011
Enter fullscreen mode Exit fullscreen mode

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

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

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

我們可以進一步測試:

>>> 4 & ~4
0
>>> 4 | ~4
-1
>>>
Enter fullscreen mode Exit fullscreen mode

這是因為:

幫 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
Enter fullscreen mode Exit fullscreen mode

用 2 的補數表示負的整數

還記得剛剛使用 bin() 內建函式顯示 2 進位結果時, 負數的奇怪表示法嗎?

>>> bin(-5)
'-0b101'
>>>
Enter fullscreen mode Exit fullscreen mode

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

>>> -0b101
-5
>>>
Enter fullscreen mode Exit fullscreen mode

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

>>> "{:b}".format(-5)
'-101'
>>> "{:#b}".format(-5)
'-0b101'
>>>
Enter fullscreen mode Exit fullscreen mode

可是若是要進行位元運算, 我們其實比較想知道實際上以 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
>>>
Enter fullscreen mode Exit fullscreen mode

要注意的是, 它提供的是整數絕對值佔用的位元數, 不含正負號位元, 所以實際佔用的位元數要多加 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'
Enter fullscreen mode Exit fullscreen mode

撰寫以 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'
>>>
Enter fullscreen mode Exit fullscreen mode

我們特別改用格式化字串為正數也加上正負號位元, 以便能清楚區別正負數。我們用 ~(-9) 來驗證結果到底正不正確:

 正負號位元
    |
    v
 ~0b1 0111
 ---------
  0b0 1000  -> 8
Enter fullscreen mode Exit fullscreen mode

實際用程式試看看:

>>> bin2(~(-9))
'0b01000'
>>> ~(-9)
8
>>>
Enter fullscreen mode Exit fullscreen mode

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

小結

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

Top comments (0)