[心得] Bitwise parallel

[FRAXIS (喔喔)]

這是之前準備面試問題的筆記，跟大家分享。

主要是在討論用bitwise parallel的技巧去解一些問題，下面這些問題

可以用類似的技巧去解，或許也可以用類似的技巧解更多問題。當然這

些解法不是問題的唯一解法，也不一定是最快速的解法，像是用查表法

這些問題都可以得到解答。我只是覺得這群問題都可以用類似的方法解

決很有趣而已。

如果有人知道其他問題也可以用類似的技巧解，請告訴我，我會很感激的。


假設給定一個32bit無號整數，如果以byte為單位切成四份，求這四份的數字總合。

範例 0x09ABCDEF -> 0x09 + 0xAB + 0xCD + 0xEF

直覺的方法就是

x & 0xFF + (x&0xFF00 >> 8) + (x&0xFF0000 >> 16) + (x&0xFF000000 >> 24)

第二種是第一種的變形，可以少一個加法運算和shift運算

x = x & 0x00FF00FF + (x & 0xFF00FF00 >> 8)
x = ((x & 0xFFFF0000) >> 16) + x & 0x0000FFFF

原理就是把原本的第一個和第三個加法同時間一起做而已，相當於把32bit

的加法器，當成兩個8bit加法器來用。


用Parallel的技巧可以讓速度加快，理論上有很多運算需要O(n)次

的運算才能完成（此地的n為整數的bit數）。不過實際上如果整數

的bit數固定，而且CPU可以支援位元運算的話，許多動作只要O(lgn)

的時間就可以完成了。

像是可以用來計算parity上面
（parity就是把32個bit xor起來，原本需要31次的xor）

x ^= x >> 16;
x ^= x >> 8;
x ^= x >> 4;
x ^= x >> 2;
x = (x ^ (x >> 1)) & 1;

同樣的技巧，也可以用來做把整數中的bit反轉的動作
（簡單的實作需要16次的交換）

x = ((x >> 1) & 0x55555555) | ((x & 0x55555555) << 1);
x = ((x >> 2) & 0x33333333) | ((x & 0x33333333) << 2);
x = ((x >> 4) & 0x0F0F0F0F) | ((x & 0x0F0F0F0F) << 4);
x = ((x >> 8) & 0x00FF00FF) | ((x & 0x00FF00FF) << 8);
x = ( x >> 16             ) | ( x               << 16);

最廣為人知的是做bit counting，計算整數中有幾個位元為1。
（暴力法需要判斷32次）

x = ((x >> 1) & 0x55555555) + (x & 0x55555555);
x = ((x >> 2) & 0x33333333) + (x & 0x33333333);
x = ((x >> 4) & 0x0F0F0F0F) + (x & 0x0F0F0F0F);
x = ((x >> 8) & 0x00FF00FF) + (x & 0x00FF00FF);
x = ((x >> 16) & 0x0000FFFF) + (x & 0x0000FFFF);

一個比較少人知道的是做bit shuffle，假設32個bit是
b1 b2 b3 .... b32，做shuffle是要把位元轉成
b1 b17 b2 b18 ... b16 b32
就好像撲克牌的完美洗牌一樣

x = (x & 0xFF0000FF) | ((x & 0x00FF0000) >> 8) | ((x & 0x0000FF00) << 8);
x = (x & 0xF00FF00F) | ((x & 0x0F000F00) >> 4) | ((x & 0x00F000F0) << 4);
x = (x & 0xC3C3C3C3) | ((x & 0x30303030) >> 2) | ((x & 0x0C0C0C0C) << 2);
x = (x & 0x99999999) | ((x & 0x44444444) >> 1) | ((x & 0x22222222) << 1);

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 140.119.162.51
推 smallworld:你確定可以變成logN? 有參考文獻嗎
推 ledia:hacker's delight
推 adrianshum:蠻有趣的技巧耶~ :D  (筆記中...)
→ FRAXIS:回一樓 bitwise parallel是實作上的技巧
→ FRAXIS:所以用這技巧去打破理論的限制是不會被計算理論學者接受的.
→ FRAXIS:當計算模型仔細到用bit來分析 這技巧就不適用了..