已發布·持續改進
Algorithm
位元運算把整數視為二進位位元，用 AND、OR、XOR 和位移來處理集合、旗標與位元遮罩 DP，既快速又簡潔。
位元運算把整數視為由 0 和 1 組成的序列，用 AND、OR、XOR、NOT 和位移來讀取、設定、清除或翻轉指定的位元。電腦以二進位儲存整數，並以二補數表示負數，因此這些運算通常只需一道 CPU 指令。像 x & -x（取最低位的 1）或 x & (x - 1)（清除這個位元）這樣的短運算式，往往能取代一整個迴圈。
位元運算之所以重要，是因為一個整數就能表示約 20 個元素的集合，因而可以列舉所有子集合，並把集合當作狀態進行位元遮罩 DP。程式競賽與技術面試常出現子集合列舉、XOR 性質與 popcount 題目；在實際系統中，檔案權限、功能旗標、子網路計算、雜湊表與點陣圖索引也都仰賴位元運算。不過各語言規則不同：Python 的整數沒有位數上限，JavaScript 會先轉成 32 位元並提供 >>>，Java 同樣有 >>>，而 C++ 中的遮罩最好使用無號型別。
建議先手動把數字轉換成二進位與二補數。接著熟悉單一位元的四種操作（設定、清除、翻轉、檢查），並讓遮罩從 0 走到 2^n - 1，印出所有子集合。之後再進入子遮罩列舉，以及工作分派、旅行推銷員問題等位元遮罩 DP，最後確認自己使用的語言的整數寬度與位移規則。
負數的二補數是把所有位元反轉後再加 1。左移相當於乘以 2，右移相當於除以 2，不同語言會區分算術右移與邏輯右移。
透過遮罩 1 << i，用 OR 設定、AND NOT 清除、XOR 翻轉第 i 個位元。x & -x 取出最低位的 1，x & (x - 1) 則把它清除。
n 個元素的子集合與 0 到 2^n - 1 的整數一一對應，聯集、交集與差集都只需一次位元運算。
可以反覆執行 x &= x - 1 或呼叫內建函式來計算 1 的個數。利用 a ^ a = 0，XOR 能找出落單的數，並求出漢明距離與格雷碼。
popcount 用 x &= x - 1 逐一清除最低位的 1，藉此計算 1 的個數。subsets 讓遮罩從 0 走到 2^n - 1，挑出第 i 個位元為 1 的元素，產生所有子集合。最後一行顯示 12 & -12 是最低位的 1 也就是 4，12 & 11 是清除該位元後的 8，x ^ x 則是 0。以 python bit_manipulation.py 執行。
bit_manipulation.py
def popcount(x: int) -> int:
count = 0
while x:
x &= x - 1 # clear the lowest set bit
count += 1
return count
def subsets(items):
n = len(items)
for mask in range(1 << n):
yield mask, [items[i] for i in range(n) if (mask >> i) & 1]
for mask, chosen in subsets(["a", "b", "c"]):
print(format(mask, "03b"), popcount(mask), chosen)
x = 12
print(x & -x, x & (x - 1), x ^ x) # 4 8 0
python bit_manipulation.py共六章，帶你從安裝一步步認識 位元運算 的核心概念。
在這裡提問、分享經驗，交流關於 位元運算 的看法。
還沒有討論。來發起第一則吧。
0 則留言
登入 · 登入後即可留言。
來留下第一則留言吧。