Bit Twiddling Hacks 解析 (一)

Bit Twiddling Hacks 解析 (一)

兩個整數是否同號

原文：Detect if two integers have opposite signs


res = (x ^ y) < 0;

因為負數從 MSB 開始會出現連續的 1; 而正數從 MSB 開始出現連續的 0。所以把兩個數 XOR 起來，如果也是一排 1 就表示兩者異號; 如果是一排 0 就表示兩者同號。如果改成 (x ^ y) >> 31 或是 (x ^ y) >> 63 就可以變成不用比較的版本。

整數絕對值

原文：Compute the integer absolute value (abs) without branching

方法一


mask = (x >> 31);
abs = (x + mask) ^ mask;

假定是 2 補數，那取絕對值其實是在做：

\[ abs(x) = \begin{cases} x & \text{if } x \geq 0 \newline (\sim x) + 1 & \text{if } x < 0 \end{cases} \]

假定 \(x > 0\)。因二補數系統恆有：

\[ (-x)_2 =\ \sim (x)_2 + 1 \]

所以在二的補數下，要找到某個負數的相反數就是逆推：先扣掉 1，再反轉所有位元。再來，那個 ~x (反轉全部位元) 可以用「XOR 0xFFFFFFFF 」來做，也就是可以用 (x ^ 0xFFFFFFFF) 代替。

然後就可以知道這個作法的原理：

如果 x >= 0，產生的 mask 是0x00000000，做 XOR 之後根本不會變，做完的結果再扣掉 mask 也不會變
反之，如果 x < 0，產生的 mask 就會是 0xFFFFFFFF，也就是二補數的 -1。上面的作法剛好就是把 x 扣掉 1 之後再反轉所有位元。

把 31 依照位元寬度不同進行對應調整就可以推廣到更寬的為元。

方法二 (patented)


mask = (x >> 31);
abs = (x ^ mask) - mask;

如果看得快的話，會發現當 \(x < 0\) 時，上面這坨東西直接變成 \(x\) 在二補數中的反元素; 而 \(x \geq 0\) 時則維持原狀。

當 \(x \geq 0\) 時顯然會對，而問題就是當x < 0 時，上面的結果會不會給出 \(-x\) ，也就是 \(x\) 的加法反元素，對應的二補數表示法？這時回到 2 補數系統中，「x, y 互為反元素 iff x + y = 0x00000000」。也就是 2 的反元素就是可以使：

\[ \mathtt{\bar x + x = 0x00000000} \]

的那個 \(\bar x\)。

回到上面的程式。當 x < 0 時，有：

\[ \mathtt{abs = (\sim x) + 1} \]

然後就驗證看看這傢伙是不是滿足反元素的定義：

\[ \mathtt{abs + x = (\sim x) + x + 1} \]

因為 ~x + x 是 0xFFFFFFFF，再加上 1 之後就變成 0x00000000，所以結果就是 0x00000000，因此就證明 abs 確實是 x 的反元素。由此可知在 x < 0 時，這個結果就是 -x。

交換兩個數

原文：Swapping values with XOR



x ^= y;
y ^= x;
x ^= y;

經典的做法。利用 XOR 的性質，\((x \oplus y)\) 再去 XOR \(x\) 或 \(y\) 其中一個時，會自動得到另外一個。如果利用 new_x 表示做完之後的 x，new_y 表示做完之後的 y ，上述的程式碼運作原理大致上如下：

new_x = x ^ (x ^ y) = y;
new_y = y ^ (x ^ y) = x;

看清楚這種：


x ^ (x ^ y)

形式的東西。後面很多利用到類似的想法去構造。比如說：













// cond 為真時交換 2 數
new_x = x ^ ((x ^ y) & -cond);
new_y = y ^ ((x ^ y) & -cond);

// 找最大最小值。上面 cond 用 (x < y) 帶入得到
max = x ^ ((x ^ y) & -(x < y));
min = y ^ ((x ^ y) & -(x < y));

// 依照 mask 合併 x 跟 y 的位元
r = x ^ ((x ^ y) & mask); 

// 依照 mask 把位元設成 cond。上面 y 用 -cond 帶入得到
x = x ^ ((x ^ -cond) & mask);

看條件交換兩個數

上面這個看似簡單的東西，可以做一點變形，達到「若滿足某某某條件，就將兩者交換; 否則維持原狀」的效果。也就是像下面這樣的程式碼：

if (cond) {
    new_1 = y;
    new_2 = x;
} else {
    new_1 = x;
    new_2 = y;
}

可以用下面這個東西取代：


new_1 = y ^ ((x ^ y) & -cond);
new_2 = x ^ ((x ^ y) & -cond);

當 cond == 1 的時候，-cond 會是 -1 (也就是 0xFFFFFFFF)，所以就會交換; 反之，-cond 會是 0x00000000，結果就是維持原樣。

找最大/最小值

原文：Compute the minimum (min) or maximum (max) of two integers without branching

方法一 (視條件交換兩數)

這個作法可以由上面的「有條件的交換兩個數」啟發，使用 (x < y) 作為上面的 cond，就做完了。他的程式本來是：

new_1 = y ^ ((x ^ y) & -cond);
new_2 = x ^ ((x ^ y) & -cond);

把 cond 變成 x < y，得到：

new_1 = x ^ ((x ^ y) & -(x < y));
new_2 = y ^ ((x ^ y) & -(x < y));

可以驗證看看：當 x < y 這個條件為真時，結果會是：

new_1 = x ^ (x ^ y);    /* = y */
new_2 = y ^ (x ^ y);    /* = x */

而不成立時，結果會是：

new_1 = x;
new_2 = y;

把 new_1 名字改成 max、new_2 名字改成 min 就做完了。


max = x ^ ((x ^ y) & -(x < y));
min = y ^ ((x ^ y) & -(x < y));

方法二 (僅限相減不會溢位時)



diff = (x - y)
max = x - ((diff) & (diff >> 31));
min = y + ((diff) & (diff >> 31));

數學上的概念是：「幫比較小的數補上兩者之間的差距，就得到比較大的那個」。把兩個數中比較小的加上 \(|x - y|\)，把比較大的扣掉 \(|x - y|\)，就可以自動調整出比較大跟比較小的數了。

所以，假定 x < y，而且 (x - y) 不會溢位，那照上面的作法，「比較小的(這邊是 x)加上兩個之間的差距就是比較大的」：

\[ \max \{x, y\} = x + |x - y| = x + (-\underbrace{(x - y)}_{\text{diff}}) = y \]

而類似地，最小值就是「比較大的減掉兩個之間的差距」，也就是：

\[ \min \{x, y\} = y - |x - y| = y -(- (x - y)) = x \]

看條件合併位元

原文：Merge bits from two values according to a mask

問題：給定一個 mask，以及兩組整數 x 跟 y。如果 mask 的第 i 位元是 1，那結果的第 i 位元就要跟 x 一樣; 反之，如果第 i 位元是 0，那結果的第 i 位元要跟 y 一樣。






unsigned int x;    // value to merge in non-masked bits
unsigned int y;    // value to merge in masked bits
unsigned int mask; // 1 where bits from b should be selected; 0 where from a.
unsigned int r;    // result of (a & ~mask) | (b & mask) goes here

r = x ^ ((x ^ y) & mask);

這個形式跟上面「有條件的交換」很類似，原理也幾乎一樣。用同樣的想法，逐位元思考就會得到了：

如果 mask 的第 i 位元是位元是 1，那結果的第 i 位元會跟 x ^ (x ^ y) 的第 i 位元，也就是 b 的第 i 位元;
反之，若 mask 的第 i 位元是 0，結果的第 i 位元就會跟 x ^ 0 的第 i 位元一樣，也就是 x 的第 i 位元。

看條件設定或清除位元

原文：Conditionally set or clear bits without branching

問題：不用 branch 做到 x = cond ? (x | mask) : (x & ~mask)。也就是說：當 cond 為真時，照著 mask 設定位元; 反之，照著 mask 清除位元。cond 只會是 1 或是 0。


x = x ^ ((x ^ -cond) & mask);

思考方式可以用上面的「依照條件合併位元」來做，把 y 用 -cond 帶入就會得到答案。或是先遮住 mask，看一下這個形式的東西：

x ^ (x ^ -cond)

這個東西明顯就是 -cond。接著再把 mask 的部分放回去：

x ^ ((x ^ -cond) & mask)

這就很明顯可以理解這段程式的意思了：當 mask 的某位元為 1 時，把 x 的那個位元設成跟 cond 的那個位元一樣; 反之，就是維持原樣。

或是另外一個步驟比較多，但是直覺的解法：


x = (x & ~mask) | (-cond & mask);

這其實完全就是直接翻譯問題的要求。

清掉最低位元的 1


res = (x & (x - 1));

原理大概像這樣：

( x )  = ...100000...000
(x-1)  = ...011111...111
------------------------ (AND)
x&(x-1)= ...000000...000

最低位元的 1 及比它更低的位元會形成 100...000 的樣式。
扣掉 1 的時候，因為最低位的 1 被借位的關係，因此計算結果後，原先最低位的 1 以下的低位元必定會出現 011...111 這樣形式的位元。
而比原先最低位元的 1 更高的那些位元因為最低位的 1 已經被借位借走的關係，並不會在減 1 時受到影響，所以維持不變。
因此，再把兩個 XOR 起來，把相異的位元通通變成 0。

取出最低位的 1


res = (v) & (-v);

原理像是這個樣子：觀察 -x 在二補數其實就是 ~x + 1：

 ( x  )  =     ...     100000...000
 ( ~x )  =  (和原來相反) 011111...111
 (~x+1)  =  (和原來相反) 100000...000    = ( -x )

因此：

 ( x  )  =     ...     100000...000
 ( -x )  =  (和原來相反) 100000...000
------------------------------------(AND)
x&(~x+1) = ...000000...100000...000

正數是不是 2 的某次方

原文：Determining if an integer is a power of 2

這個問題是：一個數是不是剛好是 \(2^n\) 這種形式。


res = (x & (x - 1)); // res==0 if x is power of 2

這個概念也很簡單：

某個數為 2 的冪次時，整個數中僅有 1 個位元會是 1，其餘均為 0
把最低位的 1 消去之後，發現是 0x00000000 ，就表示他是 2 的冪次。

聽起來很 OK ，但問題是如果這個數字是 0x00000000，那麼結果會出錯，會是 0xFFFFFFFF。所以需要的話可以把這個狀況也考慮進去：


res = x && !(x & (x - 1));

看條件變號

原文：Conditionally negate a value without branching

問題：在不使用 branch 的狀況下，做到 res = cond ? x : (-x)。其中 cond 必定是
1 或 0。

第一個解法就是上面絕對值的那個「0 會產生的錯誤」：


r = x * (cond ^ (cond - 1));

當 cond 是 0 的時候，cond ^ (cond - 1) 會生出 0xFFFFFFFF，也就是 -1，乘上去之後就會變號。反之，若 cond 是 1，那麼就是在做 x * (1 ^ 0)，也就是回到 x。

不過動用乘法畢竟有點貴，所以另外一個做法是用 XOR：


r = (x ^ -cond) + cond;

cond 為 1 的時候，-cond 會是 0xFFFFFFFF，所以實際上就是在做 r = (~x) + 1，也就是取二補數的加法反元素
cond 為 0 的時候，就是在做 (x ^ 0) - 0，所以一切不變。

Sign Extension

方法一：用算的

原文：Sign extending from a variable bit-width

問題是對一個 b 位元的數做 sign extension。







unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
int m = 1U << (b - 1); // mask can be pre-computed if b is fixed

x = x & ((1U << b) - 1);  // (Skip this if bits in x above position b are already zero.)
r = (x ^ m) - m;

這個做法原理是：把最低的 b 位元取出來，然後如果最左邊的位元 1 的話 (也就是要生出一排 1)，那麼 (m ^ x) - m 會做像下面這種事：

000...001  (b-1 bits)   (x)
000...001  00.....00    (m)
-------------------------------------(XOR)
000...000  (b-1 bits)   (m ^ x)
000...001  00.....00    (m)
-------------------------------------(-)
111...111  (b-1 bits)   ((m ^ x) - m)

而如果最左邊的位元是 0 的話，m ^ x 會讓他多 m，於是 (m ^ x) - m 又會再扣回去：

000...000  (b-1 bits)   (x)
000...001  00.....00    (m)
-------------------------------------(XOR)
000...001  (b-1 bits)   (m ^ x)
000...001  00.....00    (m)
-------------------------------------(-)
000...000  (b-1 bits)   ((m ^ x) - m)

方法二：除法計算

原文：Sign extending from a variable bit-width in 3 operations






















unsigned b; // number of bits representing the number in x
int x;      // sign extend this b-bit number to r
int r;      // resulting sign-extended number
#define M(B) (1U << (32 - B))
static int const multipliers[] = 
{
  0,     M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
  M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
  M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
  M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
  M(32)
}; // (add more if using more than 64 bits)
static int const divisors[] = 
{
  1,    ~M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
  M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
  M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
  M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
  M(32)
}; // (add more for 64 bits)
#undef M
r = (x * multipliers[b]) / divisors[b];

最核心的思想是假定心中想的是個 b 位元的整數，那麼做：

m = 32 - b;
res = (x << m) >> m;

在有號數使用算術位移的狀況下，就會得到 sign extension 的結果。不過因為上面這個做法未定義行為，所以要動點手腳避開未定義行為。

我在納悶這個做法會不會踩到 UB。比如 x = 0x2，b = 2 時：
\[\mathtt{x \cdot M(2)} = \mathtt{2 \cdot 2^{30}} > 2^{31}-1 \quad \text{(overflow ?)}\]
(然後發現真的會)(見下方 UBsan 的測試)

在 godbolt 用 gcc 5.5 加上 -O0 -fsanitize=undefined 選項編譯以下程式(godbolt 連結) ：



























#include <stdio.h>
int main()
{
    unsigned b = 2; // number of bits representing the number in x
    int x = 2;      // sign extend this b-bit number to r
    int r;      // resulting sign-extended number
#define M(B) (1U << (32 - B))
    static int const multipliers[] =
    {
      0,     M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
      M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
      M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
      M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
      M(32)
    }; // (add more if using more than 64 bits)
    static int const divisors[] =
    {
      1,    ~M(1),  M(2),  M(3),  M(4),  M(5),  M(6),  M(7),
      M(8),  M(9),  M(10), M(11), M(12), M(13), M(14), M(15),
      M(16), M(17), M(18), M(19), M(20), M(21), M(22), M(23),
      M(24), M(25), M(26), M(27), M(28), M(29), M(30), M(31),
      M(32)
    }; // (add more for 64 bits)
#undef M
    r = (x * multipliers[b]) / divisors[b];
    printf("%x\n", r);
}

會顯示是未定義行為：

Compiler returned: 0
Program returned: 0
example.cpp:25:12: runtime error: signed integer overflow: 1073741824 * 2 cannot be represented in type 'int'
fffffffe

另外，用 gcc 6.1 開始就會編譯不過。錯誤訊息出在 multipliers 陣列中：

<source>: In function 'int main()':
<source>:15:5: error: narrowing conversion of '2147483648u' from 'unsigned int' to 'int' inside { } [-Wnarrowing]
     }; // (add more if using more than 64 bits)
     ^

在 b 位元的表示法中，如果 x 最高位是 0 的狀況下，其實是在做： \(x \cdot 2^{(32 - b)} / 2^{(32 - b)}\)，所以就是原地不動。

另外一個狀況，假設在 b 位元的表示法中， x 最高位是 1，並假定它代表的數值在 b 位元中所代表的數值是 \(-n\)，其中 \(n > 0\) 。由乘法跟位元的觀察可知，乘上 multipliers[b] 之後~~這樣 int 溢位是未定義行為吧！但總之先假定它溢位行為就是 wrap around~~，得到的位元所表示的數值會是 \(-n \times 2^{32 - b}\)，然後再除掉 \(2^{32 - b}\)，就會得到 32 位元的 \(-n\)。

特例是只有 b = 1 的時候，因為這時 1 << 31 ~~這也會未定義行為吧！~~ 會是負數，而不像前面那樣是個正數，所以計算結果會多一個負號。他的解法是在 b = 1 改成 ~M(1)，這樣 b = 1 且 x = 1 時，在使用二補數的時候，正在計算的數值就會變成 \(-2^{31} / (2^{31} - 1) = -1\) 也就是 \(\mathtt{0xFFFFFFFF}\)。

然後如前面的測試，在 C 語言中會有溢位或未定義行為的問題。