---
# System prepended metadata

title: 研讀 Bit Twiddling Hacks
tags: [' bitwise operation', c]

---

---
tags: c, bitwise operation
---

# 研讀 Bit Twiddling Hacks
contributed by < `hsuedw` >

## [Compute the sign of an integer](https://graphics.stanford.edu/~seander/bithacks.html#CopyIntegerSign)

有兩個型別為 `int` 的變數 `v` 與 `sign` 。想要偵測 `v` 是否小於 `0` 。

### 若 `v` 小於 `0` ，則 `sign` 被指派為 `-1` 。否則， `sign` 被指派為 `0` 。

* 第一種實作方法
  :::spoiler {state=open} detect_sign_1.c
  ```c=
  int main()
  {
      int v = -7, sign;
      sign = -(v < 0);

      v = 9;
      sign = -(v < 0);

      return 0;
  }
  ```
  :::
  若 `v` 的值小於 `0` ，則運算式 `v < 0` 的值為 `1` 。結果就是 `-1` 被指派給 `sign` 。
  若 `v` 的值大於 `0` ，則運算式 `v < 0` 的值為 `0` 。結果就是 `0` 被指派給 `sign` 。
  
  接下來，觀察 `detect_sign_1.c` 的 x86 組合語言
  ```assembly=
  0000000000001129 <main>:
  1129:       f3 0f 1e fa             endbr64
  112d:       55                      push   %rbp
  112e:       48 89 e5                mov    %rsp,%rbp
  1131:       c7 45 f8 f9 ff ff ff    movl   $0xfffffff9,-0x8(%rbp)
  1138:       8b 45 f8                mov    -0x8(%rbp),%eax
  113b:       c1 e8 1f                shr    $0x1f,%eax
  113e:       0f b6 c0                movzbl %al,%eax
  1141:       f7 d8                   neg    %eax
  1143:       89 45 fc                mov    %eax,-0x4(%rbp)
  1146:       c7 45 f8 09 00 00 00    movl   $0x9,-0x8(%rbp)
  114d:       8b 45 f8                mov    -0x8(%rbp),%eax
  1150:       c1 e8 1f                shr    $0x1f,%eax
  1153:       0f b6 c0                movzbl %al,%eax
  1156:       f7 d8                   neg    %eax
  1158:       89 45 fc                mov    %eax,-0x4(%rbp)
  115b:       b8 00 00 00 00          mov    $0x0,%eax
  1160:       5d                      pop    %rbp
  1161:       c3                      retq
  1162:       66 2e 0f 1f 84 00 00    nopw   %cs:0x0(%rax,%rax,1)
  1169:       00 00 00
  116c:       0f 1f 40 00             nopl   0x0(%rax)
  ```
  組合語言的第 5 行到第 10 行對應到 C 語言的第 3 行到第 4 行。
  從這段組合語言得到了啟發，我們可以把程式碼以下列想法改寫
  1. 假設每個 byte 有 8 個 bit，且一個 `int` 型別的 object 在記憶體中佔用 4 個 byte。
  2. 由於現今電腦對有號整數大多採用二補數 (two's complement) 編碼。所以，若變數 `v` 內的數值小於 `0` ，則其二補數編碼的 most significant bit 必為 `1` (如組合語言第 5 行的 `$0xfffffff9`)。反之，為 `0` (如組合語言第 11 行的 `$0x9`)。
  3. 對變數 `v` 內的數值做 31 個 bit 的邏輯右移。若變數 `v` 內的數值小於 `0` ，則做完邏輯右移後，變數 `v` 內的數值變為 `1` 。否則，為 `0` 。
  4. ==在 C 語言規範中，對小於 0 的有號整數做右移 (bitwise right shift) 是 implementation-defined。==
     > C99 Standard, 6.5.7 Bitwise shift operators
     > The result of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a nonnegative value, the value of the result is the integral part of the quotient of E1 / 2E2. ==If E1 has a signed type and a negative value, the resulting value is implementation-defined.==
     
     對小於 0 的有號數而言， `>>` 運算子是邏輯右移，還是算術右移？==因為使用 GCC 編譯程式碼。所以，對有號整數而言， `>>` 運算子是算術右移==。
     > [Re: right shift of signed type](https://gcc.gnu.org/legacy-ml/gcc/2000-04/msg00152.html)
     > An arithmetic left shift is equivalent to a logical left shift
     > (as far as GCC is concerned).
     >
     > For right shifts, if the type is signed, then we use an arithmetic shift;
     > if the type is unsigned then we use a logical.

  我不知道原作者是否觀察了組合語言後，得到了第二種實作方法的靈感。
* 第二種實作方法
  :::spoiler {state=open} detect_sign_2.c
  ```c
  #define CHAR_BIT  (8)
  int main()
  {
      int v = -7;
      int sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

      v = 9;
      sign = -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

      return 0;
  }
  ```
  :::
  事實上，我們可以不需要大費周章地把變數 `v` 轉為 `unsigned int` ，做完邏輯右移後，再轉回 `int` ，然後再加上負號。
  我們可以利用下面幾個技巧簡化程式碼。
  1. ==用 GCC 編譯的程式碼中，對有號整數而言 `>>` 運算子的行為是算術右移==。也就是在右移的時候，把 most significant bit 填入左邊空出來的 bit。
  2. 在二補數編碼中， most significant bit 為 sign bit 。對正整數而言， sign bit 為 `0` 。對負整數而言， sign bit 為 `1` 。
  所以，==在使用 GCC 的前提下==，可以把 `detect_sign_2.c` 的程式碼簡化如下。
  :::spoiler {state=open} detect_sign_3.c
  ```c
  #define CHAR_BIT  (8)
  int main()
  {
      int v = -7;
      int sign = v >> (sizeof(int) * CHAR_BIT - 1);

      v = 9;
      sign = v >> (sizeof(int) * CHAR_BIT - 1);

      return 0;
  }
  ```
  :::
  也就是直接對變數 `v` 內的數值 (`int` 型別的數值為有號整數) 做算術右移 31 個 bit 。
  若變數 `v` 內的數值小於 0 ，算術右移 31 個 bit 後，變數 `v` 內的數值為 `0xffffffff` ，這就是 `-1` 的二補數二進位編碼。
  若變數 `v` 內的數值大於或等於 0 ，算術右移 31 個 bit 後，變數 `v` 內的數值為 `0x00000000` ，這就是 `0` 的二補數二進位編碼。
  > 延伸閱讀:
  > * Computer Systems: A Programmer’s Perspective, 3rd ed, Ch 2 Representing and Manipulating Information
  > * [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)

  要注意的是， ==`detect_sign_3.c` 不具 portability== 。因為對有號整數做 bitwise right shift 的行為取決於 compiler 的實做，不是 C 語言的規範。

### 若 `v` 小於 `0` ，則 `sign` 被指派為 `-1` 。否則， `sign` 被指派為 `1` 。

:::spoiler {state=open} detect_sign_4.c
```c
#define CHAR_BIT  (8)
int main()
{
    int v = -7;
    int sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));

    v = 9;
    sign = +1 | (v >> (sizeof(int) * CHAR_BIT - 1));

    return 0;
}
```
:::
延續 `detect_sign_3.c` 的實作，對 `(v >> (sizeof(int) * CHAR_BIT - 1))` 做 bitwise or ，可以實現當 `v` 小於 `0` ，則 `sign` 被指派為 `-1` 。否則， `sign` 被指派為 `1`。
如先前所述，這種寫法不具 portability。

### 若 `v` 小於 `0` ，則 `sign` 被指派為 `-1` 。若 `v` 等於 `0` ，`sign` 被指派為 `0` 。若 `v` 大於 `0` ，`sign` 被指派為 `1` 。

:::spoiler {state=open} detect_sign_5.c
```c
#define CHAR_BIT  (8)
int main()
{
    int v = -7;
    int sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

    v = 9;
    sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

    v = 0;
    sign = (v != 0) | -(int)((unsigned int)((int)v) >> (sizeof(int) * CHAR_BIT - 1));

    return 0;
}
```
:::

:::spoiler {state=open} detect_sign_6.c
```c
#define CHAR_BIT  (8)
int main()
{
    int v = -7;
    int sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1));

    v = 9;
    sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1));

    v = 0;
    sign = (v != 0) | (v >> (sizeof(int) * CHAR_BIT - 1));

    return 0;
}
```
:::
`detect_sign_5.c` 雖然比較繁瑣，但具 protibility 。 `detect_sign_6.c` 則相反。
原作者還提供第三種實作方式。
:::spoiler {state=open} detect_sign_7.c
```c
int main()
{
    int v = -7;
    int sign = (v > 0) - (v < 0);

    v = 9;
    sign = (v > 0) - (v < 0);

    v = 0;
    sign = (v > 0) - (v < 0);

    return 0;
}
```
:::

### 若 `v` 為非 `0` ，則 `sign` 被指派為 `1` 。否則， `sign` 被指派為 `0` 。

:::spoiler {state=open} detect_sign_8.c
```c
#define CHAR_BIT (8)
int main()
{
    int v = -7;
    int sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1));

    v = 9;
    sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1));

    v = 0;
    sign = 1 ^ ((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1));

    return 0;
}
```
:::
由先前的討論可得知，
* 若變數 `v` 的數值小於 `0` ，則 `((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1))` 運算式的計算結果為 `0x00000001` 。再與 `1` 做 `^` (bitwise xor) ，最後結果為 `0x00000000` 。
* 若變數 `v` 的數值為非 `0` ，則 `((unsigned int)v >> (sizeof(int) * CHAR_BIT - 1))` 運算式的計算結果為 `0x00000000` 。再與 `1` 做 `^` (bitwise xor) ，最後結果為 `0x00000001` 。

## [Detect if two integers have opposite signs](https://graphics.stanford.edu/~seander/bithacks.html#DetectOppositeSigns)

```c
#include <stdbool.h>
int main()
{
    int x = 0, y = 0;
    bool f = ((x ^ y) < 0);

    x = 1, y = 2;
    f = ((x ^ y) < 0);

    x = -1, y = -2;
    f = ((x ^ y) < 0);

    x = 1, y = -2;
    f = ((x ^ y) < 0);

    return 0;
}
```
由於現今電腦對有號整數大多採用二補數 (two's complement) 編碼。所以，在有號整數的二進位表示法中，其 most significant bit 為 sign bit。這裡借用 Computer Systems: A Programmer's Perspective 第三版，第二章中對二補數編碼的定義來說明
> Computer Systems: A Programmer's Perspective, 2.2.3 Two's-Complement Encodings
> PRINCIPLE: Definition of two's-complement encoding
> For vector $\vec{x} = [x_{w-1}, x_{w-2}, \cdots, x_{0}]$
> $$
> B2T_{w}(\vec{x}) \dot{=} -x_{w-1}2^{w-1} + \sum\limits_{i=0}^{w-2} x_{i}2^{i} \tag{2.3}
> $$

由公式 (2.3) 可以得知對小於 0 的有號整數而言，其二進位表示法中的 most signifcant bit 必為 `1`。否則，為 `0` 。
* 若兩有號整數 (`x` 與 `y`)，一為負整數，另一為非負整數，則此兩有號整數的 most significant bit 必分別為 `1` 與 `0` 。 `x ^ y` 運算結果的 most siginificant bit 必為 `1` 。所以， `x ^ y` 運算結果必為負整數。
* 若兩有號整數 (`x` 與 `y`)，同時大於等於 0 或同時小於 0 ，則此兩有號整數的 most significant bit 必同時分別為 `0` 或 `1` 。 `x ^ y` 運算結果的 most siginificant bit 必為 `0` 。所以， `x ^ y` 運算結果必為非負整數。

## [Compute the minimum (min) or maximum (max) of two integers without branching](https://graphics.stanford.edu/~seander/bithacks.html#IntegerMinOrMax)

### 找最小值

#### 第一種方法

:::spoiler {state=open} min1.c
```c=
int my_min(int x, int y)
{
    return y ^ ((x ^ y) & -(x < y));
}

int main()
{
    int r = my_min(3, 5);
    r = my_min(9, 2);
    r = my_min(8, 8);

    return 0;
}
```
:::
整支程式的重點當然就是第 3 行中 `y ^ ((x ^ y) & -(x < y))` 這個運算式。把這個運算式拆解成幾個部分來看。
* `-(x < y)` 這個運算式扮演條件判斷的的角色。
  * 如果 `x < y` 成立，則整個 `-(x < y)` 的結果是 `-1` 。由於電腦採用二補數表示有號整數，所以 `-1` 的二進位表示法為 `0xffffffff` (假設 `int` 型別 object 佔用 4 個 byte)。所以可以對整個運算式 `y ^ ((x ^ y) & -(x < y))` 做出下列改寫:
    `y ^ ((x ^ y) & -(x < y))`
    $\Rightarrow$ `y ^ ((x ^ y) & 0xffffffff)`
    $\Rightarrow$ `y ^ (x ^ y)`
    $\Rightarrow$ `x`
  * 如果 `x < y` 不成立 (也就是 `x` 大於 `y` )，則整個 `-(x < y)` 的結果是 `0` 。 `0` 的二進位表示法為 `0` 所以可以對整個運算式 `y ^ ((x ^ y) & -(x < y))` 做出下列改寫:
    `y ^ ((x ^ y) & -(x < y))`
    $\Rightarrow$ `y ^ ((x ^ y) & 0)`
    $\Rightarrow$ `y ^ 0`
    $\Rightarrow$ `y`

#### 第二種方法

:::spoiler {state=open} min2.c
```c=
#include <limits.h>

int my_min(int x, int y)
{
    return y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
}

int main()
{
    int r = my_min(3, 5);
    r = my_min(9, 2);
    r = my_min(8, 8);
    r = my_min(INT_MIN, INT_MIN);
    r = my_min(INT_MAX, INT_MAX);
    r = my_min(INT_MAX, INT_MIN);
    r = my_min(INT_MIN, INT_MAX);

    return 0;
}
```
:::

假設 `int` 型別的 object 在記憶體中佔用 4 個 byte ，每個 byte 有 8 個 bit。所以 `(x - y) >> (sizeof(int) * CHAR_BIT - 1)` 運算式會對 `(x - y)` 做 31 個 bit 的 bitwise right shift 31。
在==使用 GCC 編譯程式碼==的前提下。運算子 `>>` 對負整數而言是算術右移，對非負整數而言是邏輯右移。
1. 如果 `x - y` 為負整數 (也就是 `x` 小於 `y` ) ，則運算式 `(x - y) >> (sizeof(int) * CHAR_BIT - 1)` 的結果就是 `0xffffffff` 。那麼，我們可以對整個 `y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))` 運算式做下列改寫:
   `y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))`
   $\Rightarrow$ `y + ((x - y) & ((x - y) >> 31))`
   $\Rightarrow$ `y + ((x - y) & 0xffffffff)`
   $\Rightarrow$ `y + (x - y)`
   $\Rightarrow$ `x`
2. 如果 `x - y` 為正整數 (也就是 `x` 大於 `y` ) ，則運算式 `(x - y) >> (sizeof(int) * CHAR_BIT - 1)` 的結果就是 `0` 。那麼，我們可以對整個 `y + ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)))` 運算式做下列改寫:
   $\Rightarrow$ `y + ((x - y) & ((x - y) >> 31))`
   $\Rightarrow$ `y + ((x - y) & 0)`
   $\Rightarrow$ `y + 0`
   $\Rightarrow$ `y`
然而第二種方法在第 15 行與第 16 行無法計算出正確答案。這兩行計算出來的答案都是 `INT_MAX` 而不是我們所期待的 `INT_MIN` 。這是 overflow 所造成的問題。所以==第二種方法的使用前提是 `x - y` 不能發生 overflow== 。

### 找最大值

#### 第一種方法

```c=
int my_max(int x, int y)
{
    return x ^ ((x ^ y) & -(x < y));
}

int main()
{
    int r = my_max(3, 5);
    r = my_max(9, 2);
    r = my_max(8, 8);

    return 0;
}
```
* 運作原理 `min1.c` 相似。
* 其實，第 3 行中的運算式也可以寫成這樣 `y ^ ((x ^ y) & -(y < x))` 。

#### 第二種方法

```c=
#include <limits.h>

int my_max(int x, int y)
{
    return x - ((x - y) & ((x - y) >> (sizeof(int) * CHAR_BIT - 1)));
}

int main()
{
    int r = my_max(3, 5);
    r = my_max(9, 2);
    r = my_max(8, 8);
    r = my_max(INT_MIN, INT_MIN);
    r = my_max(INT_MAX, INT_MAX);
    r = my_max(INT_MAX, INT_MIN);
    r = my_max(INT_MIN, INT_MAX);

    return 0;
}
```
* 運作原理 `min2.c` 相似。
* 然而第二種方法在第 15 行與第 16 行無法計算出正確答案。這兩行計算出來的答案都是 `INT_MIN` 而不是我們所期待的 `INT_MAX` 。這是 overflow 所造成的問題。所以==第二種方法的使用前提是 `x - y` 不能發生 overflow== 。

## [Determining if an integer is a power of 2](https://graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2)

```c
#include <stdbool.h>

bool is_power_of_2(unsigned int v)
{
    return v && !(v & (v - 1));
}

int main()
{
    bool f = is_power_of_2(100);
    f = is_power_of_2(1024);
    f = is_power_of_2(0);

    return 0;
}
```
* 若變數 `v` 的值是 2 的冪 (power of 2)，則它的二進位編碼中必定只有一個 bit 為 `1` 。假設變數 `v` 的數值為 `1024` ，它的二進位編碼為 10000000000$_{2}$ ，則運算式 `v - 1` 的結果為 01111111111$_{2}$ 。所以，運算式 `v & (v - 1)` 的結果就是 10000000000$_{2}$ & 01111111111$_{2}$ = 0 。
* 所以，==只要變數 `v` 的值是 2 的冪 ，運算式 `v & (v - 1)` 的結果就是 0== 。
* 有一個例外狀況需要處理。當變數 `v` 的值為 `0` 時， `v & (v - 1)` 的結果是 0 。但是， 0 並不是 2 的冪。所以把運算式改寫為 `v && !(v & (v - 1))` 。這樣就可以擋掉這個例外狀況。

## Sign extending

### [Sign extending from a constant bit-width](https://graphics.stanford.edu/~seander/bithacks.html#FixedSignExtend)

假設有一個以二補數表示的有號數 `x` ，其二進位表示法由 b 個 bit 表示。然後，我們想要把 `x` 轉換成由 `int` 型別 (一般為 32 個 bit)的 object 表示。則左邊多出來的 bit 皆填 sign bit 。
```c
#define BIT_WIDTH (5)
int main()
{
    int x; // convert this from using BIT_WIDTH bits to a full int
    int r; // resulting sign extended number goes here
    struct {
        signed int x:BIT_WIDTH;
    } s;

    x = -3;
    r = s.x = x;

    x = 5;
    r = s.x = x;

    return 0;
}
```

```
(gdb) l
1
2       #define BIT_WIDTH (5)
3       int main()
4       {
5           int x; // convert this from using BIT_WIDTH bits to a full int
6           int r; // resulting sign extended number goes here
7           struct {
8               signed int x:BIT_WIDTH;
9           } s;
10
(gdb)
11          x = -3;
12          r = s.x = x;
13
14          x = 5;
15          r = s.x = x;
16
17          return 0;
18      }
(gdb) b 11
Breakpoint 1 at 0x1131: file test.c, line 11.
(gdb) r
Starting program: /home/edward/workspace/linux-2022/gdb/test

Breakpoint 1, main () at test.c:11
11          x = -3;
(gdb) n
12          r = s.x = x;
(gdb) x/4bx &r
0x7fffffffe2dc: 0x00    0x00    0x00    0x00
(gdb) n
14          x = 5;
(gdb) x/4bx &r
0x7fffffffe2dc: 0xfd    0xff    0xff    0xff
(gdb) n
15          r = s.x = x;
(gdb) n
17          return 0;
(gdb) x/4bx &r
0x7fffffffe2dc: 0x05    0x00    0x00    0x00
(gdb)
```

### [Sign extending from a variable bit-width](https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtendj)

有時候我們想要把以 b 個 bit 表示的有號整數用更多 bit 表示，但我們又事先不知道 b 的確切數字。也就是說， `b` 是個變數。
```c=
int main()
{
    unsigned b = 5; // number of bits representing the number in x
    int x = -3;     // sign extend this b-bit number to r
    int r;          // resulting sign-extended number
    int const 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;

    x = 3;
    x = x & ((1U << b) - 1);
    r = (x ^ m) - m;

    return 0;
}
```
以上面這個程式為例。變數 `b` (無號正整數)的數值為 `5` 。也就是用 5 個 bit 表示有號數。
第 6 行的變數 `m` 的值為 `0x00000010` 。
第 8 行。運算式 `(1U << b)` 的結果為 `0x00000020` 。接著，運算式 `(1U << b) - 1` 的結果為 `0x0000001f` 。 所以，整個運算式 `x & ((1U << b) - 1)` 的結果為 `0x0000001d` 。並把這個值指派給變數 `x` 。
* 也就是說，運算式 `(1U << b) - 1` 造出了一個 mask 。這個 mask 保留了變數 `x` 的 bit 0 ~ 4 ，其餘的 bit 全都清為 0 。
第 9 行。運算式 `x ^ m` 的結果為 `0x0000000d` 。所以，整個運算式 `(x ^ m) - m` 的結果為負整數 `0xfffffffd` ，並把這個值指派給變數 `r`。
* 也就是說，運算式 `x ^ m` 檢測變數 `x` 中的 sign bit (就是本範例中的 bit 4 )。
* 在這個範例中，以 5 個 bit 表示有號整數。所以有號整數的範圍為 -16 ~ 15 。
* 如果這 5 個 bit 表示一個負整數，則 sign bit (即 bit 4 ) 為 `1` 。那麼，運算式 `x ^ m` 相當於加 16 。則運算式 `(x ^ m) - m` 則是再減掉 `-16` ，就會回到原本的負整數。
* 如果這 5 個 bit 表示一個非負整數，則 sign bit (即 bit 4 ) 為 `0` 。那麼，運算式 `x ^ m` 相當於減 16 。則運算式 `(x ^ m) - m` 則是再減掉 `-16` ，就會回到原本的非負整數。

### [Sign extending from a variable bit-width in 3 operations](https://graphics.stanford.edu/~seander/bithacks.html#VariableSignExtendRisky)

```c=
#include <stdio.h>
#include <limits.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 << ((sizeof(x) * CHAR_BIT) - B)) // CHAR_BIT=bits/byte
    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("%d\n", r);

    return 0;
}
```
假設 1 個 byte 有 8 個 bit 。 `int` 與 `unsigned int` 都是佔用 4 個 byte 的記憶體空間。而我們要表示的有號整數佔用 b 個 bit 。
這個作法的核心想法就是 `(x << B) >> B` 。其中， `B = 32 - b` 。
在沒有發生 overflow 的前提下，運算式 `(x << B) >> B` 的結果與 `x` 所表示的數值相同。

#### 什麼時候會發生 overflow ?

如程式中的第 6~7 行所示，當變數 `b` 與 `x` 的數值皆為 `2` 時， $2 << 30 = 2 \times 2^{30} = 2^{31} > 2^{31} - 1$ 。會超過 `int` 型別所能表示的最大值 ($2^{31} - 1$)，所以會發生 overflow。
把上面的程式編譯後，並執行。可得下列結果。
```
$ gcc test.c -fsanitize=undefined -o test
$ ./test
test.c:27:12: runtime error: signed integer overflow: 2 * 1073741824 cannot be represented in type 'int'
-2
```
原本預期程式會輸出 `2` 。但是因為 overflow ，得到的結果卻是 `-2` 。
由這個範例中的討論可以知道，只要 $log_{2}x + (32 - b) \ge 31$ 就會發生 overflow 。

在程式碼中，第 20 行的 `~M(1)` 跟 `multipliers` 與 `divisors` 這兩個陣列的其他元素看起來不大一樣。如果只用 1 個 bit 表示有號整數，那麼可以表示的數值範圍為 -1 ~ 0 。也就是當變數 `b` 與 `x` 皆為 `1` 時， $log_{2}x + (32 - b) = 31 \ge 31$ 。會發生 overflow 。無法套用 `(x << B) >> B` 這個想法。
```c
#include <stdio.h>
#include <limits.h>

int main()
{
    unsigned b = 1; // number of bits representing the number in x
    int x = 1;      // sign extend this b-bit number to r
    int r;      // resulting sign-extended number
    #define M(B) (1U << ((sizeof(x) * CHAR_BIT) - B)) // CHAR_BIT=bits/byte
    int multiplier = M(b), divisor = M(b);

    r = (x * multiplier) / divisor;
    printf("%d\n", r);

    return 0;
}
```
編譯並執行後，可得下列結果。原本預期程式會輸出 `-1` 。但是因為 overflow ，得到的結果卻是 `1` 。
```
$ gcc test.c -fsanitize=undefined -o test
$ ./test
1
```
將 `divisor = M(b)` 改為 `divisor = ~M(b)` 。因為 `1 * M(1)` $\Rightarrow$ `1 << 31` $\Rightarrow$ `-2147483648` ，又 `~M(1)` $\Rightarrow$ `2147483647` 。所以 `-2147483648 / 2147483647` $\Rightarrow$ `-1` 。
```c
#include <stdio.h>
#include <limits.h>

int main()
{
    unsigned b = 1; // number of bits representing the number in x
    int x = 1;      // sign extend this b-bit number to r
    int r;      // resulting sign-extended number
    #define M(B) (1U << ((sizeof(x) * CHAR_BIT) - B)) // CHAR_BIT=bits/byte
    int multiplier = M(b), divisor = ~M(b);

    r = (x * multiplier) / divisor;
    printf("%d\n", r);

    return 0;
}
```
編譯並執行後，就可以得到預期的結果。
```
$ gcc test.c -fsanitize=undefined -o test
$ ./test
-1
```

## [Conditionally set or clear bits without branching](https://graphics.stanford.edu/~seander/bithacks.html#ConditionalSetOrClearBitsWithoutBranching)

不用 C 語言的 `if ... else ...` 語句 (即 without branch 或 branchless ) 做到下面這支程式的效果。也就是當變數 `f` 為 `1` 時，會按照變數 `m` 的 set bits 設定變數 `w`  中相對應的位元 。否則 (即變數 `f` 為 `0` ) ，會按照變數 `m` 的 set bits 清除變數 `w`  中相對應的位元 。變數 `f` 的值只會是 `0` 或 `1` 。
```c
#include <stdbool.h>

int main()
{
    bool f;          // conditional flag
    unsigned int m; // the bit mask
    unsigned int w; // the word to modify

    if (f)
        w |= m;
    else
        w &= ~m;

    return 0;
}
```

### 方法一:

```c
#include <stdbool.h>

int main()
{
    bool f = 1;          // conditional flag
    unsigned int m = 0xabcdef12; // the bit mask
    unsigned int w = 0x12345678; // the word to modify

    w ^= (-f ^ w) & m;  // w = w ^ ((-f ^ w) & m);

    return 0;
}
```
藉由觀察組合語言可以推得運算式 `w ^= (-f ^ w) & m` 等價於運算式 `w = w ^ ((-f ^ w) & m)` 。
```
$ gcc test.c -O0 -g -o test
$ objdump  -d test | less

0000000000001129 <main>:
    1129:       f3 0f 1e fa             endbr64
    112d:       55                      push   %rbp
    112e:       48 89 e5                mov    %rsp,%rbp
    1131:       c7 45 f4 01 00 00 00    movl   $0x1,-0xc(%rbp)
    1138:       c7 45 f8 12 ef cd ab    movl   $0xabcdef12,-0x8(%rbp)
    113f:       c7 45 fc 78 56 34 12    movl   $0x12345678,-0x4(%rbp)
    1146:       8b 45 f4                mov    -0xc(%rbp),%eax
    1149:       f7 d8                   neg    %eax
    114b:       33 45 fc                xor    -0x4(%rbp),%eax
    114e:       23 45 f8                and    -0x8(%rbp),%eax
    1151:       31 45 fc                xor    %eax,-0x4(%rbp)
    1154:       b8 00 00 00 00          mov    $0x0,%eax
    1159:       5d                      pop    %rbp
    115a:       c3                      retq
    115b:       0f 1f 44 00 00          nopl   0x0(%rax,%rax,1)
```

* 假設 1 個 byte 有 8 個 bit 。 1 個 `unsigned int` 佔用 4 個 byte 。
* $A \oplus B = (A \cdot \lnot B) + (\lnot A \cdot B)$

#### 變數 `f` 的數值為 `1`

`w ^ ((-f ^ w) & m)`
$\Rightarrow$ `w ^ ((-1 ^ w) & m)`
$\Rightarrow$ `w ^ ((0xffffffff ^ w) & m)`
$\Rightarrow$ `w ^ (w & m)`
$\Rightarrow$ `(w & ~(w & m)) | (~w & (w & m))`
$\Rightarrow$ `(w & (~w | ~m)) | (~w & (w & m))`
$\Rightarrow$ `((w & ~w) | ( w & ~m)) | ((~w & w) & m)`
$\Rightarrow$ `0 | ( w & ~m) | 0 & m`
$\Rightarrow$ `( w & ~m) | 0`
$\Rightarrow$ `w & ~m`
|  w  |  m  |  ~m  | w & m | w ^ (w & m) | w & ~m |
| --- | --- | ---- | ----- | ----------- | ------ |
|  0  |  0  |  1   |   0   |      0      |   0    |
|  0  |  1  |  0   |   0   |      0      |   0    |
|  1  |  0  |  1   |   0   |      1      |   1    |
|  1  |  1  |  0   |   1   |      0      |   0    |

#### 變數 `f` 的數值為 `0`

`w ^ ((-f ^ w) & m)`
$\Rightarrow$ `w ^ ((0 ^ w) & m)`
$\Rightarrow$ `w ^ (~w & m)`
$\Rightarrow$ `(w & ~(~w & m)) | (~w & (~w & m))`
$\Rightarrow$ `(w & (w | ~m)) | ((~w & ~w) & m)`
$\Rightarrow$ `w | (~w & m)`
$\Rightarrow$ `(w | ~w) & (w | m)`
$\Rightarrow$ `1 & (w | m)`
$\Rightarrow$ `w | m`
|  w  |  m  |  ~w  |  ~m  | w \| ~m | w & (w \| ~m) | ~w & m | w ^ (~w & m) | w \| m |
| --- | --- | ---- | ---- | ------- | ------------- | ------ | ------------ | ------ |
|  0  |  0  |  1   |  1   |    1    |       0       |    0   |       0      |    0   |
|  0  |  1  |  1   |  0   |    0    |       0       |    1   |       1      |    1   |
|  1  |  0  |  0   |  1   |    1    |       1       |    0   |       1      |    1   |
|  1  |  1  |  0   |  0   |    1    |       1       |    0   |       1      |    1   |

### 方法二:

```c
#include <stdbool.h>

int main()
{
    bool f;          // conditional flag
    unsigned int m; // the bit mask
    unsigned int w; // the word to modify

    w = (w & ~m) | (-f & m);

    return 0;
}
```

#### 變數 `f` 的數值為 `1`

`(w & ~m) | (-f & m)`
$\Rightarrow$ `(w & ~m) | (-1 & m)`
$\Rightarrow$ `(w & ~m) | (0xffffffff & m)`
$\Rightarrow$ `(w & ~m) | m`
$\Rightarrow$ `(w | m) & (~m | m)`
$\Rightarrow$ `(w | m) & 1`
$\Rightarrow$ `w | m`

#### 變數 `f` 的數值為 `0`

`(w & ~m) | (-f & m)`
$\Rightarrow$ `(w & ~m) | (0 & m)`
$\Rightarrow$ `(w & ~m) | 0`
$\Rightarrow$ `w & ~m`

## [Conditionally negate a value without branching](https://graphics.stanford.edu/~seander/bithacks.html#ConditionalNegate)

### 方法一

在不使用分支的情況下，當 flag ( `fNegate` ) 的值為 `false` 時，取負數。

```c
#include <stdbool.h>

int main()
{
    bool fDontNegate = 0;  // Flag indicating we should not negate v.
    int v = 1234;          // Input value to negate if fDontNegate is false.
    int r = 5678;          // result = fDontNegate ? v : -v;

    r = (fDontNegate ^ (fDontNegate - 1)) * v;
    return 0;
}
```

假設 `int` 佔用 4 個 byte ，每個 byte 有 8 個 bit 。

#### 當 fDontNegate 的值為 `0` 時

`r = (0 ^ (0 - 1)) * v;`
$\Rightarrow$ `r = (0 ^ (-1)) * v;`
$\Rightarrow$ `r = (0x00000000 ^ 0xffffffff) * v;`
$\Rightarrow$ `r = (0xffffffff) * v;`
$\Rightarrow$ `r = (-1) * v;`
$\Rightarrow$ `r = -v;`

用 `gdb` 追蹤程式碼。看完下面組合語言程式碼的追蹤，可以得知上面的數學推導與電腦機器指令的執行過程是一致的。
對照一下上面的 C 語言程式碼，可以得知 `r = (fDontNegate ^ (fDontNegate - 1)) * v;` 這個 statement 對應到下面組合語言的第 14 ~ 18 行。
```assemble=
$ gcc test.c -O0 -g -o test
$ gdb -q test
Reading symbols from test...
(gdb) disass main
Dump of assembler code for function main:
   0x0000000000001129 <+0>:     endbr64
   0x000000000000112d <+4>:     push   %rbp
   0x000000000000112e <+5>:     mov    %rsp,%rbp
   0x0000000000001131 <+8>:     movb   $0x0,-0x9(%rbp)
   0x0000000000001135 <+12>:    movl   $0x4d2,-0x8(%rbp)
   0x000000000000113c <+19>:    movl   $0x162e,-0x4(%rbp)
   0x0000000000001143 <+26>:    movzbl -0x9(%rbp),%eax
   0x0000000000001147 <+30>:    movzbl -0x9(%rbp),%edx
   0x000000000000114b <+34>:    sub    $0x1,%edx
   0x000000000000114e <+37>:    xor    %eax,%edx
   0x0000000000001150 <+39>:    mov    -0x8(%rbp),%eax
   0x0000000000001153 <+42>:    imul   %edx,%eax
   0x0000000000001156 <+45>:    mov    %eax,-0x4(%rbp)
   0x0000000000001159 <+48>:    mov    $0x0,%eax
   0x000000000000115e <+53>:    pop    %rbp
   0x000000000000115f <+54>:    retq
End of assembler dump.
```
下面是用 `gdb` 追蹤組合語言的部分過程。
* 當執行完第 14 行 (`sub    $0x1,%edx`) 後， CPU 暫存器 rdx 的內容由 `0` 轉為 `0xffffffff` 。
  ```gdb
  (gdb) info register rdx
  rdx            0x0                 0
  (gdb) ni
  9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
  (gdb) info register rdx
  rdx            0xffffffff          4294967295
  ```
* 當執行完第 15 行 (`xor    %eax,%edx`) 後， CPU 暫存器 rdx 的內容維持 `0xffffffff`。
  ```gdb
  (gdb) info register rax
  rax            0x0                 0
  (gdb) ni
  9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
  (gdb) info register rdx
  rdx            0xffffffff          4294967295
  ```gdb
* 當執行完第 16 行 (mov    -0x8(%rbp),%eax) 與第 17 行 (`imul   %edx,%eax`) 後， CPU 暫存器 rax 的內容變為 `0xfffffb2e` ，也就是 $-1234_{10}$ 。
  ```gdb
  (gdb) info register rax
  rax            0x0                 0
  (gdb) ni
  0x0000555555555153      9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
  (gdb) info register rax
  rax            0x4d2               1234
  (gdb) ni
  0x0000555555555156      9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
  (gdb) info register rax
  rax            0xfffffb2e          4294966062
  ```
* 當執行完第 18 行 (mov    %eax,-0x4(%rbp)) 後， 將計算結果 ($-1234_{10}$) 由 CPU 暫存器複製到記憶體位址 0x7fffffffe2cc (就是變數 `r`)中 。
  因為 Intel CPU 架構採 little endian (least significant byte 放在低位址)，所以正確的資料為 0xfffffb2e ，也就是 $-1234_{10}$ 。
  ```gdb
  (gdb) info register rbp
  rbp            0x7fffffffe2d0      0x7fffffffe2d0
  (gdb) x/4bx 0x7fffffffe2cc
  0x7fffffffe2cc: 0x2e    0x16    0x00    0x00
  (gdb) ni
  10          return 0;
  (gdb) x/4bx 0x7fffffffe2cc
  0x7fffffffe2cc: 0x2e    0xfb    0xff    0xff
  (gdb)
  ```

#### 當 fDontNegate 的值為 `1` 時

`r = (1 ^ (1 - 1)) * v;`
$\Rightarrow$ `r = (1 ^ (0)) * v;`
$\Rightarrow$ `r = (0x00000001 ^ (0x00000000)) * v;`
$\Rightarrow$ `r = (0x00000001) * v;`
$\Rightarrow$ `r = 1 * v;`
$\Rightarrow$ `r = v;`

把 C code 中，變數 `fDontNegate` 的初值改為 `1` 。
下面是用 gdb 追蹤組合語言的部分過程。

```assemble=
$ gcc test.c -O0 -g -o test
$ gdb -q test
Reading symbols from test...
(gdb) disass main
Dump of assembler code for function main:
   0x0000000000001129 <+0>:     endbr64
   0x000000000000112d <+4>:     push   %rbp
   0x000000000000112e <+5>:     mov    %rsp,%rbp
   0x0000000000001131 <+8>:     movb   $0x1,-0x9(%rbp)
   0x0000000000001135 <+12>:    movl   $0x4d2,-0x8(%rbp)
   0x000000000000113c <+19>:    movl   $0x162e,-0x4(%rbp)
   0x0000000000001143 <+26>:    movzbl -0x9(%rbp),%eax
   0x0000000000001147 <+30>:    movzbl -0x9(%rbp),%edx
   0x000000000000114b <+34>:    sub    $0x1,%edx
   0x000000000000114e <+37>:    xor    %eax,%edx
   0x0000000000001150 <+39>:    mov    -0x8(%rbp),%eax
   0x0000000000001153 <+42>:    imul   %edx,%eax
   0x0000000000001156 <+45>:    mov    %eax,-0x4(%rbp)
   0x0000000000001159 <+48>:    mov    $0x0,%eax
   0x000000000000115e <+53>:    pop    %rbp
   0x000000000000115f <+54>:    retq
End of assembler dump.
```

一樣把注意力集中在第 14 ~ 18 行。
在程式執行到第 14 行時，變數 `fDontNegate` ， `v` 與 `r` 的初值會被分別寫到 `0x7fffffffe2d7` (1 byte) ， `0x7fffffffe2d8` (4 bytes) 與 `0x7fffffffe2dc` (4 bytes) 這三個記憶體位址。要注意的是， Intel CPU 採用 little endian 對記憶體讀寫資料。
```gdb
(gdb) info register rbp
rbp            0x7fffffffe2e0      0x7fffffffe2e0
(gdb) x/4xb 0x7fffffffe2d7
0x7fffffffe2d7: 0x01    0x00    0x00    0x00
(gdb) x/4xb 0x7fffffffe2d8
0x7fffffffe2d8: 0xd2    0x04    0x00    0x00
(gdb) x/4xb 0x7fffffffe2dc
0x7fffffffe2dc: 0x2e    0x16    0x00    0x00
```
接著執行組合語言第 14 行 (`sub    $0x1,%edx`)。因為在第 13 行已經把變數 `fDontNegate` (記憶體位址 `0x7fffffffe2d7` ) 的值複製給了 CPU 暫存器 `rdx` ，所執行完第 14 行後，暫存器 `rdx` 的值為 `0` 。
```gdb
(gdb) info register rdx
rdx            0x1                 1
(gdb) ni
9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
(gdb) info register rdx
rdx            0x0                 0
```
當執行完第 15 行 (xor %eax,%edx) 後， CPU 暫存器 rdx 的內容變為 `1`。因為暫存器 eax 在第 12 行已被設定為變數 `fDontNegate` 的值，也就是 `1` 。
```gdb
(gdb) ni
9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
(gdb) info register rdx
rdx            0x1                 1
```
當執行完第 16 行 ( `mov -0x8(%rbp),%eax` ) 與第 17 行 ( `imul %edx,%eax` ) 後， CPU 暫存器 rax 的內容變為 `0x4d2` ，也就是 `1234` 。
```gdb
(gdb) info register rax
rax            0x1                 1
(gdb) ni
9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
(gdb) ni
0x0000555555555153      9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
(gdb) info register rax
rax            0x4d2               1234
```
當執行完第 18 行 ( `mov %eax,-0x4(%rbp)` ) 後， 將計算結果 ( $1234_{10}$ ) 由 CPU 暫存器複製到記憶體位址 `0x7fffffffe2dc` (就是變數 r)中 。
```gdb
(gdb) x/4dx 0x7fffffffe2dc 
0x7fffffffe2dc : 0x2e    0x16    0x00    0x00
(gdb) ni
0x0000555555555156      9           r = (fDontNegate ^ (fDontNegate - 1)) * v;
(gdb) ni
10          return 0;
(gdb) x/4dx 0x7fffffffe2dc 
0x7fffffffe2dc: 0xd2    0x04    0x00    0x00
```

### 方法二

在不使用分支的情況下，當 flag ( `fNegate` ) 的值為 `true` 時，取負數。

```c
#include <stdbool.h>

// If you need to negate only when a flag is true, then use this:
int main()
{
    bool fNegate = 1;  // Flag indicating if we should negate v.
    int v = 1234;      // Input value to negate if fNegate is true.
    int r = 5678;      // result = fNegate ? -v : v;

    r = (v ^ -fNegate) + fNegate;
    return 0;
}
```

假設 `int` 佔用 4 個 byte ，每個 byte 有 8 個 bit 。

#### 當 fDontNegate 的值為 `1` 時

`r = (v ^ -fNegate) + fNegate;`
$\Rightarrow$ `r = (v ^ -1) + 1;`
$\Rightarrow$ `r = (v ^ 0xffffffff) + 1;`
$\Rightarrow$ `r = ~v + 1;`
$\Rightarrow$ `r = -v;`

接著用 GDB 追蹤程式碼。
```gdb=
$ gcc test.c -O0 -g -o test
$ gdb -q test
Reading symbols from test...
(gdb) disass main
Dump of assembler code for function main:
   0x0000000000001129 <+0>:     endbr64
   0x000000000000112d <+4>:     push   %rbp
   0x000000000000112e <+5>:     mov    %rsp,%rbp
   0x0000000000001131 <+8>:     movb   $0x1,-0x9(%rbp)
   0x0000000000001135 <+12>:    movl   $0x4d2,-0x8(%rbp)
   0x000000000000113c <+19>:    movl   $0x162e,-0x4(%rbp)
   0x0000000000001143 <+26>:    movzbl -0x9(%rbp),%eax
   0x0000000000001147 <+30>:    neg    %eax
   0x0000000000001149 <+32>:    xor    -0x8(%rbp),%eax
   0x000000000000114c <+35>:    mov    %eax,%edx
   0x000000000000114e <+37>:    movzbl -0x9(%rbp),%eax
   0x0000000000001152 <+41>:    add    %edx,%eax
   0x0000000000001154 <+43>:    mov    %eax,-0x4(%rbp)
   0x0000000000001157 <+46>:    mov    $0x0,%eax
   0x000000000000115c <+51>:    pop    %rbp
   0x000000000000115d <+52>:    retq
End of assembler dump.
```
對照 C code 之後，可以很容易地理解到，組合語言中的第 9 到 11 行就是將變數 `fNegate` 、 `v` 以及 `r` 分別初始化為 `1` 、 `1234` 以及 `5678` 。所以，這三個變數的記憶體位址分別為 `0x7fffffffe247` (`-0x9(%rbp)`) 、 `0x7fffffffe248` (`-0x8(%rbp)`) 以及 `0x7fffffffe24c` (`-0x4(%rbp)`)。
```gdb
(gdb) info register rbp
rbp            0x7fffffffe250      0x7fffffffe250
(gdb) x/1xb 0x7fffffffe247
0x7fffffffe247: 0x01
(gdb) x/4xb 0x7fffffffe248
0x7fffffffe248: 0xd2    0x04    0x00    0x00
(gdb) x/4xb 0x7fffffffe24c
0x7fffffffe24c: 0x2e    0x16    0x00    0x00
```
組合語言第 12 與 13 行將變數 `fNegate` 的值 (也就是記憶體位址 `0x7fffffffe247` 中的值) 複製到暫存器 `eax` 中。然後再對暫存器 `eax` 取負值。
```gdb
(gdb) info register rax
rax            0x555555555129      93824992235817
(gdb) ni
0x0000555555555147      10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x1                 1
(gdb) ni
10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0xffffffff          4294967295
```
組合語言第 14 行將變數 `v` 的值 ( `0x04d2` ) 與 `0xffffffff` 也就是 ( `-1` ) 進行 xor 運算。得到的結果為 `~v` ( `0xfb2d` ) 。
```gdb
(gdb) ni
0x000055555555514c      10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0xfffffb2d          4294966061
```
組合語言第 15 到 17 行將 `0xfb2d` 複製到暫存器 edx ，將變數 `fNegate` 的值 (`1`) 複製到暫存器 eax ，將暫存器 edx 中的值與暫存器 eax 中的值相加 ( `0xfb2d + 1` ) 後的和存入暫存器 eax 中。
```gdb
(gdb) info register rdx
rdx            0x7fffffffe358      140737488347992
(gdb) ni
10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rdx
rdx            0xfffffb2d          4294966061
(gdb) info register rax
rax            0xfffffb2d          4294966061
(gdb) ni
10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x1                 1
(gdb) ni
0x0000555555555154      10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0xfffffb2e          4294966062
```
最後，組合語言第 18 行，將最後的結果 `0xfb2e` ( `-1234` ) 複製到變數 `r` 中。
```gdb
(gdb) x/4bx 0x7fffffffe24c
0x7fffffffe24c: 0x2e    0x16    0x00    0x00
(gdb) ni
11          return 0;
(gdb) x/4bx 0x7fffffffe24c
0x7fffffffe24c: 0x2e    0xfb    0xff    0xff
```

#### 當 fDontNegate 的值為 `0` 時

`r = (v ^ -fNegate) + fNegate;`
$\Rightarrow$ `r = (v ^ 0) + 0;`
$\Rightarrow$ `r = v + 0;`
$\Rightarrow$ `r = v;`

在 C code 中，將變數 `fNegate` 的初值改為 `0` 。
接著用 GDB 追蹤程式碼。
```gdb=
$ gcc test.c -O0 -g -o test
$ gdb -q test
Reading symbols from test...
(gdb) disass main
Dump of assembler code for function main:
   0x0000000000001129 <+0>:     endbr64
   0x000000000000112d <+4>:     push   %rbp
   0x000000000000112e <+5>:     mov    %rsp,%rbp
   0x0000000000001131 <+8>:     movb   $0x0,-0x9(%rbp)
   0x0000000000001135 <+12>:    movl   $0x4d2,-0x8(%rbp)
   0x000000000000113c <+19>:    movl   $0x162e,-0x4(%rbp)
   0x0000000000001143 <+26>:    movzbl -0x9(%rbp),%eax
   0x0000000000001147 <+30>:    neg    %eax
   0x0000000000001149 <+32>:    xor    -0x8(%rbp),%eax
   0x000000000000114c <+35>:    mov    %eax,%edx
   0x000000000000114e <+37>:    movzbl -0x9(%rbp),%eax
   0x0000000000001152 <+41>:    add    %edx,%eax
   0x0000000000001154 <+43>:    mov    %eax,-0x4(%rbp)
   0x0000000000001157 <+46>:    mov    $0x0,%eax
   0x000000000000115c <+51>:    pop    %rbp
   0x000000000000115d <+52>:    retq
End of assembler dump.
```
和上一節一樣，組合語言中的第 9 到 11 行就是將變數 `fNegate` 、 `v` 以及 `r` 分別初始化為 `0` 、 `1234` 以及 `5678` 。所以，這三個變數的記憶體位址分別為 `0x7fffffffe247` (`-0x9(%rbp)`) 、 `0x7fffffffe248` (`-0x8(%rbp)`) 以及 `0x7fffffffe24c` (`-0x4(%rbp)`)。
```gdb
(gdb) x/1xb 0x7fffffffe247
0x7fffffffe247: 0x00
(gdb) x/4xb 0x7fffffffe248
0x7fffffffe248: 0xd2    0x04    0x00    0x00
(gdb) x/4xb 0x7fffffffe24c
0x7fffffffe24c: 0x2e    0x16    0x00    0x00
```
組合語言第 12 與 13 行將變數 fNegate 的值 (也就是記憶體位址 0x7fffffffe247 中的值) 複製到暫存器 eax 中。然後再對暫存器 eax 取負值。
```gdb
(gdb) info register rax
rax            0x555555555129      93824992235817
(gdb) ni
0x0000555555555147      10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x0                 0
(gdb) ni
10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x0                 0
```
組合語言第 14 行將變數 v 的值 ( `0x04d2` ) 與 `0` 進行 xor 運算。得到的結果為 ~v ( `0x04d2` ) 。
```gdb
(gdb) ni
0x000055555555514c      10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x4d2               1234
```
組合語言第 15 到 17 行將 `0x04d2` 複製到暫存器 edx ，將變數 `fNegate` 的值 ( `0` ) 複製到暫存器 eax ，將暫存器 edx 中的值與暫存器 eax 中的值相加 ( `0x04d2 + 0` ) 後的和存入暫存器 eax 中。
```gdb
(gdb) info register rdx
rdx            0x7fffffffe358      140737488347992
(gdb) ni
10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rdx
rdx            0x4d2               1234
(gdb) info register rax
rax            0x4d2               1234
(gdb) ni
10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x0                 0
(gdb) ni
0x0000555555555154      10          r = (v ^ -fNegate) + fNegate;
(gdb) info register rax
rax            0x4d2               1234
```
最後，組合語言第 18 行，將最後的結果 `0xfb2e` ( `-1234` ) 複製到變數 `r` 中。
```gdb
(gdb) x/4bx 0x7fffffffe24c
0x7fffffffe24c: 0x2e    0x16    0x00    0x00
(gdb) ni
11          return 0;
(gdb) x/4bx 0x7fffffffe24c
0x7fffffffe24c: 0xd2    0x04    0x00    0x00
```

## [Merge bits from two values according to a mask](https://graphics.stanford.edu/~seander/bithacks.html#MaskedMerge)

```c
int main()
{
    unsigned int a;    // value to merge in non-masked bits
    unsigned int b;    // 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 = a ^ ((a ^ b) & mask);

    return 0;
}
```
這段程式碼中定義了 4 個 `unsigned int` 變數 `a` 、 `b` 、 `mask` 與 `r` 。若變數 `mask` 的 bit i 為 `1` 則變數 `r` 的 bit i 會與變數 `b` 的 bit i 相同。若變數 `mask` 的 bit i 為 `0` 則變數 `r` 的 bit i 會與變數 `a` 的 bit i 相同。

以下標 $_{i}$ 表示某個變數的 bit i 。

### 當 $mask_{i}$ 為 `1` 時

$r_{i} = a_{i} \oplus ((a_{i} \oplus b_{i}) \land mask_{i})$
$\Rightarrow r_{i} = a_{i} \oplus ((a_{i} \oplus b_{i}) \land 1)$
$\Rightarrow r_{i} = a_{i} \oplus (a_{i} \oplus b_{i})$
$\Rightarrow r_{i} = b_{i}$
所以，當變數 `mask` 的 bit i 為 `1` 則變數 `r` 的 bit i 會與變數 `b` 的 bit i 相同。

### 當 $mask_{i}$ 為 `0` 時

$r_{i} = a_{i} \oplus ((a_{i} \oplus b_{i}) \land mask_{i})$
$\Rightarrow r_{i} = a_{i} \oplus ((a_{i} \oplus b_{i}) \land 0)$
$\Rightarrow r_{i} = a_{i} \oplus 0$
$\Rightarrow r_{i} = a_{i}$
所以，當變數 `mask` 的 bit i 為 `0` 則變數 `r` 的 bit i 會與變數 `a` 的 bit i 相同。

## Counting bits set

### [Counting bits set (naive way)](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive)

```c
int main()
{
    unsigned int v; // count the number of bits set in v
    unsigned int c; // c accumulates the total bits set in v

    for (c = 0; v; v >>= 1)
        c += v & 1;

    return 0;
}
```
這支程式應該不需要多做解釋。

### [Counting bits set by lookup table](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetTable)

#### 方法一

```c
int main()
{
    static const unsigned char BitsSetTable256[256] =
    {
    #define B2(n) n,     n+1,     n+1,     n+2
    #define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
    #define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
        B6(0), B6(1), B6(1), B6(2)
    };

    unsigned int v; // count the number of bits set in 32-bit value v
    unsigned int c; // c is the total bits set in v

    // Option 1:
    c = BitsSetTable256[v & 0xff] +
        BitsSetTable256[(v >> 8) & 0xff] +
        BitsSetTable256[(v >> 16) & 0xff] +
        BitsSetTable256[v >> 24];

    return 0;
}
```

#### 方法二

```c
int main()
{
    static const unsigned char BitsSetTable256[256] =
    {
    #define B2(n) n,     n+1,     n+1,     n+2
    #define B4(n) B2(n), B2(n+1), B2(n+1), B2(n+2)
    #define B6(n) B4(n), B4(n+1), B4(n+1), B4(n+2)
        B6(0), B6(1), B6(1), B6(2)
    };

    unsigned int v; // count the number of bits set in 32-bit value v
    unsigned int c; // c is the total bits set in v

    // Option 2:
    unsigned char * p = (unsigned char *) &v;
    c = BitsSetTable256[p[0]] +
        BitsSetTable256[p[1]] +
        BitsSetTable256[p[2]] +
        BitsSetTable256[p[3]];

    return 0;
}
```

#### 另一種產生 table 的方法

```c
// To initially generate the table algorithmically:
BitsSetTable256[0] = 0;
for (int i = 0; i < 256; i++)
{
  BitsSetTable256[i] = (i & 1) + BitsSetTable256[i / 2];
}
```


### [Counting bits set, Brian Kernighan's way](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetKernighan)



### [Counting bits set in 14, 24, or 32-bit words using 64-bit instructions](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSet64)



### [Counting bits set, in parallel](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel)



### [Count bits set (rank) from the most-significant bit upto a given position](https://graphics.stanford.edu/~seander/bithacks.html#CountBitsFromMSBToPos)



### [Select the bit position (from the most-significant bit) with the given count (rank)](https://graphics.stanford.edu/~seander/bithacks.html#SelectPosFromMSBRank)



## [Swapping values with XOR](https://graphics.stanford.edu/~seander/bithacks.html#SwappingValuesXOR)

```c=
int main()
{
    int x = 12, y = 77;
    x = x ^ y;
    y = x ^ y;
    x = x ^ y;

    return 0;
}
```
或者可以跟原作者一樣定義 macro 。
```c
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))
```
接下來研究如何用 bitwise xor 運算子 (`^`) 交換兩個型別為 `int` 的變數的值。
|  x  |  y  |  x ^ y |
| --- | --- | ------ |
|  0  |  0  |    0   |
|  0  |  1  |    1   |
|  1  |  0  |    1   |
|  1  |  1  |    0   |
   
由 xor 的真值表可以看出==運算式 `x ^ x` 的結果是 0== 。
所以，第 5 行可以改寫如下:
```c=5
y = (12 ^ 77) ^ 77;
```
所以，當第 5 行執行完畢後，變數 `y` 的值就是變數 `x` 一開始的值，也就是 `12` 。
接著看第 6 行。這時，變數 `x` 停留在第 4 行執行結束後的狀態，也就是 `x ^ y`。且此時變數 `y` 的值已經是變數 `x` 原本一開始的數值。所以可以把第 6 行改寫如下:
```c=6
x = (12 ^ 77) ^ 12;
```
所以，第 6 行執行完畢後，變數 `x` 的數值就會是變數 `y` 原本一開始的數值，也就是 `77` 。

### 有條件交換兩個變數的數值

```c=
#include <stdio.h>
int main()
{
    int x = 12, y = 77, cond = 0, t;
    t = x ^ y;
    y = y ^ (t & -cond);
    x = x ^ (t & -cond);

    return 0;
}
```
* 假設整數型別 ( `int` ) 變數在記憶體中佔用 4 個 byte ，且每個 byte 有 8 個 bit 。
* 若變數 `cond` 的數值為 `0` ，則運算式 `t & -cond` 的結果就是 `0` ，導致第 6 行與第 7 行可寫如下。
  ```c=6
  y = 77 ^ 0;
  x = 12 ^ 0;
  ```
* 若變數 `cond` 的數值為 `1` ，則運算式 `-cond` 的結果就是 `-1` 。而 `-1` 的二補數編碼就是 `0xffffffff` 。那麼，運算式 `t & 0xffffffff` 的結果還是變數 `t` 的數值。所以，第 6 行與第 7 行可寫如下。
  ```c=6
  y = 77 ^(12 ^ 77)
  x = 12 ^(12 ^ 77)
  ```
  所以，當變數 `cond` 為 `0` 時，變數 `x` 與 `y` 的數值維持不變。當變數 `cond` 為 `1` 時，變數 `x` 與 `y` 的數值互換。
* NOTE:
  這部分的內容參考 [看條件交換兩個數](https://hackmd.io/@0xff07/ORAORAORAORA#%E7%9C%8B%E6%A2%9D%E4%BB%B6%E4%BA%A4%E6%8F%9B%E5%85%A9%E5%80%8B%E6%95%B8) 的敘述。


## 參考資料
* [Bit Twiddling Hacks](https://graphics.stanford.edu/~seander/bithacks.html)
* [Bit Twiddling Hacks 解析 (一)](https://hackmd.io/@0xff07/ORAORAORAORA)
* [Bit Twiddling Hacks 解析 (二)](https://hackmd.io/@0xff07/MUDAMUDAMUDA)
* [Bit Twiddling Hacks 解析 (三)](https://hackmd.io/@0xff07/WRYYYYYYYYYY)
* Computer Systems: A Programmer's Perspective, Third Edition
* [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)
* [CS107 Guide to x86-64 - Stanford University](https://web.stanford.edu/class/archive/cs/cs107/cs107.1222/guide/x86-64.html)