DEV Community

codemee
codemee

Posted on • Edited 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 進位表示內容, 希望可以對大家有幫助。

Reinvent your career. Join DEV.

It takes one minute and is worth it for your career.

Get started

Top comments (0)

Sentry image

See why 4M developers consider Sentry, “not bad.”

Fixing code doesn’t have to be the worst part of your day. Learn how Sentry can help.

Learn more

👋 Kindness is contagious

Explore a sea of insights with this enlightening post, highly esteemed within the nurturing DEV Community. Coders of all stripes are invited to participate and contribute to our shared knowledge.

Expressing gratitude with a simple "thank you" can make a big impact. Leave your thanks in the comments!

On DEV, exchanging ideas smooths our way and strengthens our community bonds. Found this useful? A quick note of thanks to the author can mean a lot.

Okay