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 補數，那取絕對值其實是在做：

a b s (x) = {\begin{cases} x & if x \geq 0 \\ (\sim x) + 1 & 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 的反元素就是可以使：

\bar{x} + x = 0 x 00000000

的那個

\bar{x}

。

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

abs = (\sim x) + 1

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

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 + (- \underset{diff}{\underset{⏟}{(x - y)}}) = 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 時：

$x \cdot M (2) = 2 \cdot 2^{30} > 2^{31} - 1 (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

也就是

0 xFFFFFFFF

。

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

sss22213

2021/06/17 04:25:25

應該是X? (Edited)

0xff07

2021/06/17 15:07:55

沒錯！感謝您的修正！ (Edited)

Ethan Lee

2021/11/08 12:41:01

:::info 看清楚這種： ```c= x ^ (x ^ y) ``` 形式的東西。後面很多利用到類似的想法去構造。比如說： ```c= // cond 為真時交換 2 數

new_x還是x? (Edited)

2021/11/08 12:44:16

當cond=1時候，new_x還是x?

2021/11/08 13:30:31

cond 為 1 時，-cond 就會變成 (-1)，也就是 0xFFFFFFFF，所以 (x^y) & (-cond) 就會是 (x^y) 自己。因此最後 new_x 就會是 y^(x^y)，也就是恢復到 x 自己。 (Edited)

2021/11/09 00:16:00

ok,因為我以為你是想要new_x變成y (Edited)

2021/11/09 13:07:19

感謝您指出問題！已經修正🙇🏻 (Edited)

2021/11/26 10:52:01

~x` (反轉全部位元) 可以用「XOR `0xFFFFFFFF`

我一直搞不清楚這句話 ~x (反轉全部位元) 可以用「任何位元 XOR 0xFFFFFFFF 會變成和原來相反的位元配上程式碼和比對公式 (Edited)

2021/11/26 14:46:12

嗨！和 0xFFFFFFFF 做 XOR 可以反轉位元是能夠證明的。因為給定 x 的任意位元： 1. 如果這個位元是 0，那麼 (0^1) 會是 1 2. 如果原先的位元是 1。則 (1^1) 會變 0 因此，不論該位元是 0 或是 1，和 1 做 XOR 之後都會變成與原來相反的位元。維基百科的 Bitwise operation 介紹中的 XOR [1] 也有提到： The bitwise XOR may be used to invert selected bits in a register (also called toggle or flip). Any bit may be toggled by XORing it with 1. 裡面介紹到的其實也就是這個東西。 [1] https://en.wikipedia.org/wiki/Bitwise_operation#XOR

2021/11/26 11:00:33

然後abs這公式有出處嗎？當x<0時候，abs(x)=~(x-1)才對吧？我有理解錯誤嗎@@ 而且你這邊式子跟下面方法二解釋那邊，當 x < 0 時 abs = (~x)+1不一樣，我沒誤會的話兩個式子應該要一樣吧？ (Edited)

2021/11/26 15:11:16

這部分應該是想要寫 (~x) + 1。所以原先的 (~x) - 1 是錯的，應修正為 (~x) + 1。然而，您的 ~(x - 1) 也是對的，並且若已經知這個做法的話，用它直接看這個作法是比較顯然的。這邊的寫作脈絡是想先介紹 (~x) + 1 可以變號，然後導出 ~(x - 1) 這個作法。而之所以把一個二補數 x 做 (~x) + 1 會有變號的效果（不論 x 的正負）是因為：對於一個 32 位元的整數，有： (x) + (~x) = 0xFFFFFFFF 這時候可以觀察：如果左右再 +1 的話，就會有： (x) + (~x) + 1 = 0x00000000 兩者加起來是 0x00000000，這就表示 (~x) + 1 恰好是 (x) 的反元素（不論 x 是正是負）（然後可能還會需要 2 補數是加法群所以反元素唯一之類的東西）。所以就會有變號的效果。 (Edited)

2021/11/26 15:15:12

這個 (~x) + 1 可以變號，無論 x 的正負的現象（假定沒有超出正數的表達範圍的話），在康乃爾大學 CS 的介紹文章 Two's Complement [1] 中的 Conversion from Two's Complement 有提到： To see what this number is a negative of, we reverse the sign of this number. But how to do that? The class notes say (on 3.17) that to reverse the sign you simply invert the bits (0 goes to 1, and 1 to 0) and add one to the resulting number. (Edited)

2021/11/26 15:17:47

之所以沒有直接從 ~(x - 1)，而是由 (~x) + 1 開始的理由是因為：由 (~x) + 1 這個作法推到 ~(x - 1) 是明顯的，但是另外一個方向可能未必，而且由上述 (~x) + 1 的推導過程，x 不論正負都能適用。另外一方面 ~(x - 1) 這個作法就筆者當初學習的經驗來說，只介紹到「當 x 為負數時」這個作法可以逆推回變號前的數值。而 x 為正數時，這個作法是否仍然成立需要另外證明，我覺得很麻煩XD。 [1] https://www.cs.cornell.edu/~tomf/notes/cps104/twoscomp.html (Edited)

2021/11/30 07:14:24

ok, 我一開始被那個負號搞混了，運算式跟你的敘述不一樣可是很像，一開始看的時候產生一個邏輯衝突 (Edited)

Chang Hank

2024/04/18 09:27:20

因此，再把兩個 XOR 起來，把相異的位元通通變成 0。

應該是把兩個結果AND？可能不小心打錯了