# 2017q3 Homework1 (clz)
contributed by < `lukechin` >
作業要求: https://hackmd.io/s/Hyl9-PrjW
## clz的應用案例
* 測試兩數是否相等
設兩數為 $x$ 與 $y$，
在 32-bit 無符號數值範圍可由 $clz(x−y)$` >> `$5$，得知
因為當 $x$ 與 $y$ 相等時，$clz(x-y)$ 為 $32$，在右邏輯位移 $5$ 後，得 $1$；
$x$ 與 $y$ 不相等 $clz(x-y)$ 則不為 $32$，位移後，得 $0$。
```
is_equal(unsigned int x, unsigned int y){
return clz(x-y)>>5;
}
```
* [Binary GCD](https://en.wikipedia.org/wiki/Binary_GCD_algorithm)
binary gcd 的精神就是當兩數為偶數時，必有一 $2$ 因子。
$$gcd(x, y) = 2·gcd(\frac{x}{2}, \frac{y}{2})$$
且一數為奇數另一數為偶數，則無 $2$ 因子。
$$gcd(x, y) = gcd(x, \frac{y}{2})$$
於是我們可以改良為：
$$ even\_factor = min(ctz(x), ctz(y))$$
$$gcd(x, y) = even\_factor·gcd((x\gg even\_factor), (y\gg even\_factor))$$
其中符號 $\gg$ 是 right shift。
剩下的過程就直接採用 Euclidean algorithm 的作法即可。
## 簡介clz
Count Leading Zeros (clz) 或名 Number of Leading Zeros (nlz) 為計算 2 進位數從 MSB 往右數遇到的第一個 $1$ 之前所有 $0$ 的數量， e.g. clz(`0001010100011011`) = $3$。
## 實做方式
### 利用 binary search
binary search 是一種分而治之的方式，是將問題分成兩個部份，
然後將最接近解的部份令為下一個待解的子問題，
子問題又能分成兩個部份，其中一個部份又能變為子問題，直到找到解。
#### iterative
```clike=
int clz(uint32_t x) { // l := left, r := right
uint32_t n = 32, c = 16, l, r = x;
do {
l = r >> c;
if (l) { n -= c; r = l; }
c >>= 1;
} while (c);
return (n - r);
}
```
假設一個數字 ```00001010100011011100001010100101```
```x = 00001010100011011100001010100101```, $c = 16$, $n = 32$
```...._______________^________________```
```x = 00000000000000000000101010001101```, $c = 8$, $n = 16$
```...._______________^_______^________```
```x = 00000000000000000000000000001010```, $c = 4$, $n = 8$
```...._______________^_______^___^____```
```x = 00000000000000000000000000001010```, $c = 2$, $n = 8$
```...._______________^_______^___^_^__```
```x = 00000000000000000000000000000010```, $c = 1$, $n = 6$
```...._______________^_______^___^_^^_```
```x = 00000000000000000000000000000001```, $c = 0$, $n = 5$
$r = 1$, 最後```return (n - r);``` i.e. clz = 4.
### bit mask
作業中稱這個方法為 binary search 怪怪的，因為其他兩份 code 也是 binary search，決定將檔案都改成 bit mask
```clike=
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;
}
```
利用 bit mask 的概念去判定第一個 $1$ 出現在哪邊。
#### byte shift
```clike
int clz(uint32_t x) {
if (x == 0) return 32;
int n = 1;
if ((x >> 16) == 0) { n += 16; x <<= 16; }
if ((x >> 24) == 0) { n += 8; x <<= 8; }
if ((x >> 28) == 0) { n += 4; x <<= 4; }
if ((x >> 30) == 0) { n += 2; x <<= 2; }
n = n - (x >> 31);
return n;
}
```
只有 if 判斷跟 bit mask 寫法不同，但邏輯上是一樣的。
### Hash Table
#### De Bruijn sequence
TODO: 解釋 De Bruijn sequence
```Clike=
const int tab32[32] = {
0 , 1 , 28, 2 , 29, 14, 24, 3,
30, 22, 20, 15, 25, 17, 4 , 8,
31, 27, 13, 23, 21, 19, 16, 7,
26, 12, 18, 6 , 11, 5 , 10, 9
};
int clz(uint32_t value) {
value |= value >> 1;
value |= value >> 2;
value |= value >> 4;
value |= value >> 8;
value |= value >> 16;
return tab32[((uint32_t)((value - (value >> 1))*0x077CB531U)) >> 27];
}
```
先將 value 變為除了第一個 $1$ ，其餘的 bit 都設為 $0$
接著用```0x077CB531U```這個 De Bruijn sequence 乘上 value，在將 table 映射到的值回傳。
#### Harley's algorithm
```clike=
uint8_t clz(uint32_t x)
{
static uint8_t const Table[] = {
0xFF, 0, 0xFF, 15, 0xFF, 1, 28, 0xFF,
16, 0xFF, 0xFF, 0xFF, 2, 21, 29, 0xFF,
0xFF, 0xFF, 19, 17, 10, 0xFF, 12, 0xFF,
0xFF, 3, 0xFF, 6, 0xFF, 22, 30, 0xFF,
14, 0xFF, 27, 0xFF, 0xFF, 0xFF, 20, 0xFF,
18, 9, 11, 0xFF, 5, 0xFF, 0xFF, 13,
26, 0xFF, 0xFF, 8, 0xFF, 4, 0xFF, 25,
0xFF, 7, 24, 0xFF, 23, 0xFF, 31, 0xFF,
};
/* Propagate leftmost 1-bit to the right */
x = x | (x >> 1);
x = x | (x >> 2);
x = x | (x >> 4);
x = x | (x >> 8);
x = x | (x >> 16);
/* x = x * 0x6EB14F9 */
x = (x << 3) - x; /* Multiply by 7. */
x = (x << 8) - x; /* Multiply by 255. */
x = (x << 8) - x; /* Again. */
x = (x << 8) - x; /* Again. */
return 31 - Table[x >> 26];
}
```
先將輸入 `x`， MSB 至第一位 `1` 以後的位全變為 `1`， e.g. `00100100 -> 00111111`
再將 `x` 乘上 `0x6EB14F9`，接著位移至剩下 $5$ 位，查表並用 $31$ 減去。
`0x6EB14F9` 能產出的值為 $0$ ~ $63$ 之間 $32$ 種互不相同的數字，並且 `0xFF` 並沒有特別的意義。
## 程式執行
* 輸入 `make run`
* 畫圖 `make plot`，數值範圍從 67100000 到 67116384
從圖片中可以發現一開始效能比較是
**bit mask >= byte > iteration > harley > recursive**
可以發現 recursive 的版本所需時間跳動範圍大的多，試著縮小數值範圍來觀察
根據劉亮谷學長的開發紀錄，會造成上下跳動的原因應該是因為它特別設計的演算法的關係，能讓特定數值速度加速
Sign in with Wallet
Connect another wallet