---
tags: 你所不知道的 C 語言, 進階電腦系統理論與實作, NCKU Linux Kernel Internals, 作業系統
---
# 數值系統、Bitwise 操作、浮點數運算、定點數操作
contributed by <`RusselCK` >
###### tags: `RusselCK`
## [數值系統](https://hackmd.io/@sysprog/binary-representation)
* [解讀計算機編碼](https://hackmd.io/@sysprog/binary-representation)
#### 1. Bitwise XOR (`^`)
| bit a | bit b | bitwise `^` |
| ------ | ------ | ----------- |
|0 |0 |0 |
|1 |0 |1 |
|0 |1 |1 |
|1 |1 |0 |
注意看最後兩列，若要讓每個位元都是 `0` -> `1`, `1` -> `0` 的話，選用的 bitmask (可翻譯為「位元遮罩」，聽起來很文言，但很好理解，即想對某個數值做位元操作，才會得到預期的結果) 就該是 111...1 (在有效的位元空間中全部填入 `1`)，後者在二補數系統中，就是 `-1`。換言之，對 `-1` 做 XOR 操作可達到位元反轉。
`~x` (反轉全部位元) 可用「對 `0xFFFFFFFF` 做 XOR 操作，會變成和原來相反的位元」的特性來改寫，亦即可用 `(x ^ 0xFFFFFFFF)` 代替。
#### 2. 針對 32 位元整數實作絕對值:
```cpp
#include <stdint.h>
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x + mask) ^ mask;
}
```
該作法的原理：
1. 若 `x >= 0`，產生的 `mask` 是 `0x00000000`，做 XOR 之後根本不會變，做完的結果再扣掉 `mask` 也不會變;
2. 反之，若 `x < 0`，產生的 `mask` 就會是 `0xFFFFFFFF`，也就是二補數的 `-1`。上面的作法剛好就是把 `x` 扣掉 1 之後再反轉所有位元;
```cpp
int32_t abs(int32_t x) {
int32_t mask = (x >> 31);
return (x ^ mask) - mask;
}
```
當 $x \geq 0$ 時，`mask` 為 `0`，於是回傳值就是 `x`。那麼，當$x \lt 0$ 時，上面的結果會不會給出 $-x$ 呢？後者也就是 $x$ 的加法反元素、對應的二補數表示法。回想二補數系統「`x`, `y` 互為反元素的充要條件是 $x + y = 0x00000000$」，亦即某數和其反元素的關係:
$$
\mathtt{\bar x + x = 0x00000000}
$$
裡頭的 $\bar x$。
回到上面程式，當 `x < 0` 時，存有：
$$
\mathtt{abs(x) = (\sim x) + 1}
$$
驗證是否滿足反元素的定義：
$$
\mathtt{abs(x) + x = (\sim x) + x + 1}
$$
因為 `~x + x` 是 `0xFFFFFFFF`，再加上 `1` 即成為 `0x00000000`，因此結果是 `0x00000000`，從而證明 $abs(x)$ 確實是 $x$ 的反元素。由此可知在 $x < 0$ 時，程式碼的輸出即是 `-x`。
#### 3.給定兩個有號整數，找出其中較小的數值:
```cpp
int32_t min(int32_t a, int32_t b) {
int32_t diff = (a - b);
return b + (diff & (diff >> 31));
}
```
注意：這實作僅在 `INT32_MIN <= (a - b) <= INT32_MAX` 成立時，才會發揮作用。
再者考慮以下程式碼:
```cpp
int32_t a, b, c, x;
...
if (a > b)
x += c;
```
當 `INT32_MIN <= (b - a) <= INT32_MAX` 條件成立時，我們可改寫 `if (a > b) x += c;` 為以下程式碼:
```cpp
x += ((b - a) >> 31) & c;
```
儘管現代的中央處理器具備分支預測器 ([branch predictor](https://en.wikipedia.org/wiki/Branch_predictor))，在 `a` 和 `b` 之間變化難以預測時，上述的 branchless 手法可消弭因分支預測錯誤引發的效能損失。
#### 參考資料
* [Optimized abs function](https://www.strchr.com/optimized_abs_function)
* [Optimized ABS function in Assembly](https://helloacm.com/optimized-abs-function-in-assembly/)
* [How to get absolute value of a 32-bit signed integer as fast as possible?](https://community.arm.com/developer/ip-products/processors/f/cortex-m-forum/6636/how-to-get-absolute-value-of-a-32-bit-signed-integer-as-fast-as-possible)
* [Bit Twiddling Hacks](https://graphics.stanford.edu/~seander/bithacks.html) 解析: [(一)](https://hackmd.io/@0xff07/ORAORAORAORA), [(二)](https://hackmd.io/@0xff07/MUDAMUDAMUDA), [(三)](https://hackmd.io/@0xff07/WRYYYYYYYYYY)
* [理解矩陣](https://blog.csdn.net/myan/article/details/647511)
---
#### ASCII with Bitwise Operator
* 將字元轉成小寫: 免除使用分支
```cpp
('a' | ' ') // 得到 'a'
('A' | ' ') // 得到 'a'
```
* 將字元轉為大寫: 免除使用分支
```cpp
('a' & '_') // 得到 'A'
('A' & '_') // 得到 'A'
```
* 大小寫互轉: 避免使用分支
```cpp
('a' ^ ' ') // 得到 'A'
('A' ^ ' ') // 得到 'a'
```
#### 4. [XOR swap](https://en.wikipedia.org/wiki/XOR_swap_algorithm)
1. naive swap
```clike
void swap(int *a, int *b) {
int t = *a;
*a = *b;
*b = t;
}
```
:::warning
* 額外用到 `t`，不為 in-place，如何避免?
:::
2. 搬移差距 swap
```clike
void swap(int *a, int *b) {
*a = *a - *b; /* 兩數相差 */
*b = *a + *b; /* 相加得出 *b */
*a = *b - *a; /* 相減得出 *a */
}
```
:::danger
* 可能會造成 Overflow
:::
3. XOR swap
* 交換兩個記憶體空間內的數值，可完全不用額外的記憶體來實作
* 不只 `int` ，任何型態的數字都可用
```cpp
void xorSwap(int *x, int *y) {
*x ^= *y;
*y ^= *x;
*x ^= *y;
}
```
#### 5. 避免 overflow
* 比方說 `(x + y) / 2` 這樣的運算，有個致命問題在於 (x + y) 可能會導致 overflow (考慮到 x 和 y 都接近 [UINT32_MAX](https://msdn.microsoft.com/en-us/library/mt764276.aspx)，亦即 32-bit 表示範圍的上限之際)
* [Binary search 的演算法提出之後十年才被驗證](https://www.comp.nus.edu.sg/~sma5503/recitations/01-crct.pdf)
* 於是我們可以改寫為以下:
```cpp
(x & y) + ((x ^ y) >> 1)
```
* 用加法器來思考: `x & y` 是進位, `x ^ y` 是位元和, `/ 2` 是向右移一位
* 位元相加不進位的總和: `x ^ y`; 位元相加產生的進位值: `(x & y) << 1`
* `x + y = x ^ y + ( x & y ) << 1`
* 所以 (x + y) / 2
= `(x + y) >> 1`
= `(x ^ y + (x & y) << 1) >> 1`
= `(x & y) + ((x ^ y) >> 1)`
#### 6. [strlen](http://opensource.apple.com/source/Libc/Libc-583/arm/string/strlen.s) 偵測是否為 0 或者說是否為 NULL char ’\0’
* 我們先思考 strlen() 該怎麼實做，以下實作一個簡單的版本
```C
unsigned int strlen(const char *s) {
char *p = s;
while (*p != ’\0’) p++;
return (p - s);
}
```
這樣的版本有什麼問題？雖然看起來精簡，但是因為他一次只檢查 1byte，所以一旦字串很長，他就會處理很久。另外一個問題是，假設是在 32-bit 的 CPU 上，一次是處理 4-byte (32-bit) 大小的資訊，不覺得這樣很浪費嗎?
* C 語言程式的 DETECT NULL 巨集
```cpp
#if LONG_MAX == 2147483647L
#define DETECT(X) \
(((X) - 0x01010101) & ~(X) & 0x80808080)
#else
#if LONG_MAX == 9223372036854775807L
#define DETECT(X) \
(((X) - 0x0101010101010101) & ~(X) & 0x8080808080808080)
#else
#error long int is not a 32bit or 64bit type.
#endif
#endif
```
為了可以思考這樣的程式，我們由已知的計算方式來逆推原作者可能的思考流程，首先先將計算再簡化一點點，將他從 **(((X) - 0x01010101) & ~(X) & 0x80808080)** 變成
```
((X) - 0x01) & ~(X) & 0x80
```
還是看不懂，將以前學過的笛摩根定理套用上去，於是這個式子就變成了
```
~( ~(X - 0x01) | X ) & 0x80
```
再稍微調整一下順序
```
~( X | ~(X - 0x01) ) & 0x80
```
所以我們就可進行分析
* `X | ~(X - 0x01)` => 取得最低位元是否為 0 ，並將其他位元設為 1
* X = 0000 0011 => 1111 1111
* X = 0000 0010 => 1111 1110
* 想想 0x80 是什麼? 0x80 是 1000 0000 ，也就是 1-byte 的最高位元
上面這兩組組合起來，我們可以得到以下結果
* X = 0 => 1000 0000 => 0x80
* X = 1 => 0000 0000 => 0
* X = 2 => 0000 0000 => 0
* .......
* X = 255 => 0000 0000 => 0
於是我們知道，原來這樣的運算，如果一個 byte 是 0，那經由這個運算得到的結果會是 0x80，反之為 0。
再將這個想法擴展到 32-bit，是不是可以想到說在 32bit 的情況下，0 會得到 0x80808080 這樣的答案?我們只要判斷這個數值是不是存在，就可以找到 ’\0’ 在哪了！
#### 7. Count Leading Zero
當我們計算 log~2~ (以2為底的對數) 時, 其實只要算高位有幾個 0's bits. 再用 31 減掉即可。
> 舉例 in 8 bits:
$x$ =`00011111` 高位有3個bits
-> 最大的1出現在第(8-3=5)位
-> log~2~x 約等於 5
* 一般寫法
```cpp
int BITS = 31;
for (; i < 32; --BITS) {
if (N & 0x80000000) break;
N <<= 1;
}
```
* 類似 De Bruijn 演算法 (32-bit version)
```cpp
const int tab32[32] = {
0, 9, 1, 10, 13, 21, 2, 29,
11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7,
19, 27, 23, 6, 26, 5, 4, 31
};
int log2_32 (uint32_t value)
{
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[(uint32_t)(value*0x07C4ACDD) >> 27];
}
```
* gcc 提供 built-in Function:
* [int __builtin_clz (unsigned int x)](http://gcc.gnu.org/onlinedocs/gcc/Other-Builtins.html)
* Returns the number of leading 0-bits in x, starting at the most significant bit position.
* If x is 0, the result is undefined.
* 可用來實做 log2:
```cpp
#define LOG2(X) ((unsigned) \
(8 * sizeof (unsigned long long) -
__builtin_clzll((X)) - 1))
```
* 實做 clz
* binary search technique
```cpp
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 0;
if (x <= 0x0000FFFF) { n += 16; x <<= 16; }
if (x <= 0x00FFFFFF) { n += 8; x <<= 8; }
if (x <= 0x0FFFFFFF) { n += 4; x <<= 4; }
if (x <= 0x3FFFFFFF) { n += 2; x <<= 2; }
if (x <= 0x7FFFFFFF) { n += 1; x <<= 1; }
return n;
}
```
---
## ==[ Bitwise 操作](https://hackmd.io/@sysprog/c-bitwise)==
#### 1. Set a bit
:::info
where n is the bit number, and 0 is the least significant bit
:::
```cpp
unsigned char a |= (1 << n);
```
Example:
```
a 1 0 0 0 0 0 0 0
a |= (1 << 1) = 1 0 0 0 0 0 1 0
a |= (1 << 3) = 1 0 0 0 1 0 0 0
a |= (1 << 5) = 1 0 1 0 0 0 0 0
```
#### 2. Clear a bit:
```cpp
unsigned char b &= ~(1 << n);
```
- [ ] Example 1:
```
b 1 1 1 1 1 1 1 1
b &= ~(1 << 1) = 1 1 1 1 1 1 0 1
b &= ~(1 << 3) = 1 1 1 1 0 1 1 1
b &= ~(1 << 5) = 1 1 0 1 1 1 1 1
```
* `~` ：反向
* Test a bit:
```cpp
unsigned char e = d & (1 << n); //d has the byte value.
```
#### 3. Toggle a bit:
```cpp
unsigned char c ^= (1 << n);
```
Example:
```
c 1 0 0 1 1 0 1 1
c ^= (1 << 1) = 1 0 0 1 1 0 0 1
c ^= (1 << 3) = 1 0 0 1 0 0 1 1
c ^= (1 << 5) = 1 0 1 1 1 0 1 1
```
* The Magic of XOR
```
x ^ y == (~x & y) | (x & ~y)
```
#### 4. The right/left most byte
assuming 16 bit, 2-byte short integer:
```cpp
unsigned char right = val & 0xff; /* right most (least significant) byte */
unsigned char left = (val >> 8) & 0xff; /* left most (most significant) byte */
```
* 要不要考慮 Little endian or Big endian ?
#### 5. sign bit
assuming 16 bit, 2-byte short integer, two's complement:
```cpp
bool sign = val & 0x8000; // sign bit
```
---
#### bitwise 練習題
* [Bitwise Operators in C](http://www2.mta.ac.il/~hbinsky/c%20content/Bits.pdf)
* Uses of Bitwise Operations or Why to Study Bits
* [C Bitwise Operators Quiz](http://doc.callmematthi.eu/C_Bitwise_Operators.html)
* [線上測驗](https://pconrad.github.io/old_pconrad_cs16/topics/bitOps/) (附上解答)
* [Bitwise Practice](https://web.stanford.edu/class/archive/cs/cs107/cs107.1202/lab1/practice.html)
* [2018q1 考古題](https://hackmd.io/s/rJh9U4Guf) / [參考解答](https://hackmd.io/s/S1f0tSyTG)
* [2018q3 考古題](https://hackmd.io/s/S1a9-YO_Q) / [參考解答](https://hackmd.io/s/By5KCaZam)
* [2019q1 考古題1](https://hackmd.io/@sysprog/SyrZMGYr4) / [參考解答](https://hackmd.io/@chenishi/S1DHQ3KrE) / [延伸閱讀](https://medium.com/fcamels-notes/%E4%BD%BF%E7%94%A8%E4%BD%8D%E5%85%83%E8%A8%88%E7%AE%97%E5%8A%A0%E9%80%9F%E6%B1%82%E8%A7%A3-n-queen-d20442f34110)
* [2019q1 考古題2](https://hackmd.io/@sysprog/H1Pik8M8E) / [參考解答](https://hackmd.io/@1IzBzEXXRsmj6-nLXZ9opw/B1vrcKcu4)
* [2020q1 考古題](https://hackmd.io/@sysprog/linux2020-quiz3) / [參考解答](https://hackmd.io/@Hsuhaoxiang/2020q3)
---
## [浮點數運算與定點數操作](https://hackmd.io/@NwaynhhKTK6joWHmoUxc7Q/H1SVhbETQ)
#### 浮點數表示
#### 案例: 浮點數乘以二
* 推導：欲使給定的浮點數乘以 `2`，必須考慮到 3 種情況
1. Normalize 模式的話，必須將指數加一後放回。
2. Denormalize 模式的話，比較有趣，可以直接將原數左移一單位，
* Mantissa 的 overflow 會自動變成 exp 的 1，之後再將 sign bit 放回即可。
4. 遇到 NaN, INF，就直接 return
```clike
/* Return bit-level equivalent of expression 2 * uf
* for floating point uf
*/
unsigned float_twice (unsigned uf) {
unsigned uf_sgn = (uf >> 31) & 0x01; //擷取首位正負號
unsigned uf_exp = (uf >> 23) & 0xff; //擷取八位指數位
if (uf_exp == 0) { //檢查為 denormalized 模式
uf <<= 1; // 將數值左移一位也就是乘以二
uf += (uf_sgn << 31); //將 sign bit 放回原數
}
else if (uf_exp != 0xff) {
//檢查不是 INF or NaN （也就是剩下來的 Normalized 模式）
uf_exp += 1; //讓 exp + 1 來乘以二
/* 更新 uf */
uf &= 0x807fffff; //把 exp 的部分遮蔽掉
uf = uf + (uf_exp << 23); //把處理完的 exp 放回去
}
return uf;
}
```
* 數值範圍檢查
1. case NORMALIZE:
NORMALIZE 下能表示的數字為 ±(1.F) \* 2 ^ (E - 127)
其中 E 範圍在 1 ~ 254 之間
以最大值 E = 254 為例，經過 `float_twice` 之後 EXP 部份變成 254 + 1 = 255 也就是 infinity 或者是 NaN 的表示法
:::warning
理論上這邊結果不應該是 NaN 而應該是 infinity
不過要怎麼確認 mantissa 部份在這個時候會變成零
是不是要補個條件判斷或 mask
> [name=chenishi]
```clike
/* Return bit-level equivalent of expression 2 * uf
* for floating point uf
*/
unsigned float_twice(unsigned uf) {
unsigned uf_sgn = (uf >> 31) & 0x01;
unsigned uf_exp = (uf >> 23) & 0xff;
if (uf_exp == 0) {
uf <<= 1;
uf += (uf_sgn << 31);
}
else if (uf_exp != 0xff) {
uf_exp += 1;
/* 如果從 normalize 加到 denormalized */
if (uf_exp == 0xff) {
uf &= 0x80000000;// 歸零 mantissa
/* 正常從 normalize 到 normalize */
} else {
uf &= 0x807fffff;// 留下 mantissa
}
uf = uf + (uf_exp << 23);
}
return uf;
}
```
:::
2. case DENORMALIZE:
DENORMALIZE 下條件為 EXP 部份全部為零，如果 `float_twice` 前，mantissa 為 0b1......（也就是首位為 1）
> 舉 0-00000000-1111111111111111111111 為例（denormalize 情況下的最大數）
> E = 1 - Bias = -126
> M = 2^23 - 1 / 2^23
`float_twice` 之後
> 0-00000001-1111111111111111111110
> E = e - Bias = -126
> M = (2^23 - 1 / 2^23) * 2 (可以看成原本的 Mantissa 左移一位)
這正好符合 CS:APP 中關於 NORMALIZE/ DENORMALIZE 中 EXP 的解釋 (FLOAT 等級距的性質)
3. case NaN/ infinity:
直接回傳不影響
#### 案例: 浮點數的絕對值
* 我們知道，浮點數的正負號是由最前面的 MSB 控制的
* 所以想要取得絕對值，只要**把 $x$ 的 MSB 設為 0**。
```clike
#include<stdio.h>
#include<stdlib.h>
void absf(double *x) {
int a = 0x1;
char little_end = *((char *) &a);
*(((int *) x) + little_end) &= 0x7fffffff;
}
int main() {
double x = -1;
printf("%f \n", x);
absf(&x);
printf("%f \n", x);
}
```
> double : 8 bytes
> int : 4 bytes
> char : 1 bytes
* `a` : `0x00 00 00 01`
* 當此機器為 Little Endian 時，`char little_end`會變為`0x1`，
* 而 Big Endian 時，`char little_end` 會得到`0x0`。
* 用意:
* 在 Big Endian 之下，將 `*x & 0x7fffffff` 即為所求
* 在 Little Endian 之下，將 `*(x+1) & 0x7fffffff` 才是所求
```graphviz
digraph{
address[shape = record label = "{*x}|{*(x+1)}"]
}
```
#### Big / Small Endian
* 現今 little endian 架構在筆電，桌機上盛行
* big endian 也被稱作 Network Byte Order
* [Big Endian 與他們的現狀](https://hackmd.io/s/BJRaOrGCX)
#### [C 語言強制轉型 (Casting)](https://)
#### 要怎麼知道電腦是 Little/Big - endian ?
雖然現在主流的系統絕大多數都是 little-endian，不過還是有辦法偵測 endian
如果是在 Linux 系統，可以使用 shell script 判斷
```bash
echo -n I | od -to2 | head -n1 | cut -f2 -d" " | cut -c6
```
如果是 little endian 則應該會回傳 1，如果是 big endian 則應該會回傳 0
#### 什麼是定點數？
定點數與浮點數的差別最大在於「十進制中小數點位置是否固定」
像我們一般用的 int 整數就是「定點數」的一種，其小數點固定在最右方
這樣的表示方法用在小數上，代表我們只能夠表示固定大小的小數位
舉例來說，假設我們定點數小數點固定放在右三到右四之間，那麼
> 10 / 3 = 3.333
如果是左五到左四之間
> 10 / 3 = 3.3333
也就是說，隨著我們設計小數點位置不同，定點數能表示的範圍以及數值精度都會受到影響
Sign in with Wallet
Connect another wallet