# Bit Twiddling Hacks 解析 (一)
下一篇：[Bits Twiddling Hacks 解析 (二)](https://hackmd.io/@0xff07/MUDAMUDAMUDA)
[TOC]
## 兩個整數是否同號
原文：[Detect if two integers have opposite signs](https://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns)
```c=
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](https://graphics.stanford.edu/~seander/bithacks.html#IntegerAbs)
### 方法一
```c=
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)` 代替。
然後就可以知道這個作法的原理：
1. 如果 `x >= 0`，產生的 `mask` 是`0x00000000`，做 XOR 之後根本不會變，做完的結果再扣掉 `mask` 也不會變
2. 反之，如果 `x < 0`，產生的 `mask` 就會是 `0xFFFFFFFF`，也就是二補數的 `-1`。上面的作法剛好就是把 `x` 扣掉 1 之後再反轉所有位元。
把 31 依照位元寬度不同進行對應調整就可以推廣到更寬的為元。
### 方法二 (patented)
```c=
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](https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR)
```c=
x ^= y;
y ^= x;
x ^= y;
```
經典的做法。利用 XOR 的性質，$(x \oplus y)$ 再去 XOR $x$ 或 $y$ 其中一個時，會自動得到另外一個。如果利用 `new_x` 表示做完之後的 `x`，`new_y` 表示做完之後的 `y` ，上述的程式碼運作原理大致上如下：
```c
new_x = x ^ (x ^ y) = y;
new_y = y ^ (x ^ y) = x;
```
:::info
看清楚這種：
```c=
x ^ (x ^ y)
```
形式的東西。後面很多利用到類似的想法去構造。比如說：
```c=
// 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);
```
:::
## 看條件交換兩個數
上面這個看似簡單的東西，可以做一點變形，達到「若滿足某某某條件，就將兩者交換; 否則維持原狀」的效果。也就是像下面這樣的程式碼：
```c
if (cond) {
new_1 = y;
new_2 = x;
} else {
new_1 = x;
new_2 = y;
}
```
可以用下面這個東西取代：
```c=
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](https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)
### 方法一 (視條件交換兩數)
這個作法可以由上面的「有條件的交換兩個數」啟發，使用 `(x < y)` 作為上面的 `cond`，就做完了。他的程式本來是：
```
new_1 = y ^ ((x ^ y) & -cond);
new_2 = x ^ ((x ^ y) & -cond);
```
把 `cond` 變成 `x < y`，得到：
```c
new_1 = x ^ ((x ^ y) & -(x < y));
new_2 = y ^ ((x ^ y) & -(x < y));
```
可以驗證看看：當 `x < y` 這個條件為真時，結果會是：
```c
new_1 = x ^ (x ^ y); /* = y */
new_2 = y ^ (x ^ y); /* = x */
```
而不成立時，結果會是：
```c
new_1 = x;
new_2 = y;
```
把 `new_1` 名字改成 `max`、`new_2` 名字改成 `min` 就做完了。
```c=
max = x ^ ((x ^ y) & -(x < y));
min = y ^ ((x ^ y) & -(x < y));
```
### 方法二 (僅限相減不會溢位時)
```c=
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](https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge)
問題：給定一個 `mask`，以及兩組整數 `x` 跟 `y`。如果 `mask` 的第 `i` 位元是 `1`，那結果的第 `i` 位元就要跟 `x` 一樣; 反之，如果第 `i` 位元是 `0`，那結果的第 `i` 位元要跟 `y` 一樣。
```c=
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);
```
這個形式跟上面「有條件的交換」很類似，原理也幾乎一樣。用同樣的想法，逐位元思考就會得到了：
1. 如果 `mask` 的第 `i` 位元是位元是 `1`，那結果的第 `i` 位元會跟 `x ^ (x ^ y)` 的第 `i` 位元，也就是 `b` 的第 `i` 位元;
2. 反之，若 `mask` 的第 `i` 位元是 `0`，結果的第 `i` 位元就會跟 `x ^ 0` 的第 `i` 位元一樣，也就是 `x` 的第 `i` 位元。
## 看條件設定或清除位元
原文：[Conditionally set or clear bits without branching](https://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching)
問題：不用 branch 做到 `x = cond ? (x | mask) : (x & ~mask)`。也就是說：當 `cond` 為真時，照著 `mask` 設定位元; 反之，照著 `mask` 清除位元。`cond` 只會是 `1` 或是 `0`。
```c=
x = x ^ ((x ^ -cond) & mask);
```
思考方式可以用上面的「依照條件合併位元」來做，把 `y` 用 `-cond` 帶入就會得到答案。或是先遮住 `mask`，看一下這個形式的東西：
```c
x ^ (x ^ -cond)
```
這個東西明顯就是 `-cond`。接著再把 `mask` 的部分放回去：
```c
x ^ ((x ^ -cond) & mask)
```
這就很明顯可以理解這段程式的意思了：當 `mask` 的某位元為 `1` 時，把 `x` 的那個位元設成跟 `cond` 的那個位元一樣; 反之，就是維持原樣。
或是另外一個步驟比較多，但是直覺的解法：
```c=
x = (x & ~mask) | (-cond & mask);
```
這其實完全就是直接翻譯問題的要求。
## 清掉最低位元的 1
```c=
res = (x & (x - 1));
```
原理大概像這樣：
```c
( x ) = ...100000...000
(x-1) = ...011111...111
------------------------ (AND)
x&(x-1)= ...000000...000
```
1. 最低位元的 1 及比它更低的位元會形成 `100...000` 的樣式。
2. 扣掉 1 的時候，因為==最低位的 1 被借位==的關係，因此計算結果後，原先最低位的 1 以下的低位元必定會出現 `011...111` 這樣形式的位元。
3. 而比原先最低位元的 1 ==更高的那些位元==因為最低位的 1 已經被借位借走的關係，==並不會在減 1 時受到影響==，所以維持不變。
4. 因此，再把兩個 XOR 起來，把相異的位元通通變成 0。
## 取出最低位的 1
```c=
res = (v) & (-v);
```
原理像是這個樣子：觀察 `-x` 在二補數其實就是 `~x + 1`：
```c
( x ) = ... 100000...000
( ~x ) = (和原來相反) 011111...111
(~x+1) = (和原來相反) 100000...000 = ( -x )
```
因此：
```c
( x ) = ... 100000...000
( -x ) = (和原來相反) 100000...000
------------------------------------(AND)
x&(~x+1) = ...000000...100000...000
```
## 正數是不是 2 的某次方
原文：[Determining if an integer is a power of 2](https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)
這個問題是：一個數是不是剛好是 $2^n$ 這種形式。
```c=
res = (x & (x - 1)); // res==0 if x is power of 2
```
這個概念也很簡單：
1. 某個數為 2 的冪次時，整個數中僅有 1 個位元會是 `1`，其餘均為 `0`
2. 把最低位的 `1` 消去之後，發現是 `0x00000000` ，就表示他是 2 的冪次。
聽起來很 OK ，但問題是如果這個數字是 `0x00000000`，那麼結果會出錯，會是 `0xFFFFFFFF`。所以需要的話可以把這個狀況也考慮進去：
```c=
res = x && !(x & (x - 1));
```
## 看條件變號
原文：[Conditionally negate a value without branching](https://graphics.stanford.edu/~seander/bithacks.html#ConditionalNegate)
問題：在不使用 branch 的狀況下，做到 `res = cond ? x : (-x)`。其中 `cond` 必定是
`1` 或 `0`。
第一個解法就是上面絕對值的那個「0 會產生的錯誤」：
```c=
r = x * (cond ^ (cond - 1));
```
當 `cond` 是 0 的時候，`cond ^ (cond - 1)` 會生出 `0xFFFFFFFF`，也就是 `-1`，乘上去之後就會變號。反之，若 `cond` 是 `1`，那麼就是在做 `x * (1 ^ 0)`，也就是回到 `x`。
不過動用乘法畢竟有點貴，所以另外一個做法是用 XOR：
```c=
r = (x ^ -cond) + cond;
```
1. `cond` 為 `1` 的時候，`-cond` 會是 `0xFFFFFFFF`，所以實際上就是在做 `r = (~x) + 1`，也就是取二補數的加法反元素
2. `cond` 為 `0` 的時候，就是在做 `(x ^ 0) - 0`，所以一切不變。
## Sign Extension
### 方法一：用算的
原文：[Sign extending from a variable bit-width](https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtend)
問題是對一個 `b` 位元的數做 sign extension。
```c=
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` 會做像下面這種事：
```c
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` 又會再扣回去：
```c
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](https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtendRisky)
```c=
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` 位元的整數，那麼做：
```c
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 的測試)
:::danger
在 godbolt 用 gcc 5.5 加上 `-O0 -fsanitize=undefined` 選項編譯以下程式([godbolt 連結](https://godbolt.org/z/Jcflti)) ：
```c=
#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);
}
```
會顯示是未定義行為：
```gcc
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 開始就會編譯不過](https://godbolt.org/z/l5221f) 。錯誤訊息出在 `multipliers` 陣列中：
```gcc
<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 語言中會有溢位或未定義行為的問題。
Sign in with Wallet
Connect another wallet