# 2017q1 Homework1 (clz)
contributed by<`jack81306`>
###### tags:`jack81306`
## 開發環境
```
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
On-line CPU(s) list: 0-3
每核心執行緒數：2
每通訊端核心數：2
Socket(s): 1
NUMA 節點： 1
供應商識別號： GenuineIntel
CPU 家族： 6
型號： 60
Model name: Intel(R) Core(TM) i5-4210M CPU @ 2.60GHz
製程： 3
CPU MHz： 2463.049
CPU max MHz: 3200.0000
CPU min MHz: 800.0000
BogoMIPS: 5187.96
虛擬： VT-x
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
NUMA node0 CPU(s): 0-3
```
## 事前準備
* 閱讀以下資料
* [重新理解數值](https://hackmd.io/s/Hy-pTh8Fl)
* [劉亮谷學長的實驗紀錄](https://hackmd.io/s/BJBZn6Q6)
* [你所不知道的 C 語言：前置處理器應用篇](https://hackmd.io/s/S1maxCXMl)
## 運作原理
#### binary search technique
```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;
}
```
#### byte-shift version
```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;
}
```
* binary search technique 和 byte-shift version 的處理方式是相似的,這兩種方式都是每次檢查前面幾位的 bit 是否為 0 ,如果是的話就會將檢查出為 0 的個數加上去.
* 不同的地方在於, binary search technique 是直接檢查前面的位數是否為零,而 byte-shift version 則是將 bit 向右位移後檢查其是否為零來判斷結果.
#### iteration version
```clike=
int clz(uint32_t x) {
int n = 32, c = 16;
do {
uint32_t y = x >> c;
if (y) { n -= c; x = y; }
c >>= 1;
} while (c);
return (n - x);
}
```
* iteration version 和前面2個方法很相似,只是 iteration version 是藉由回圈來增減需要移動 bit ,並用減法來計算前面為零的個數,與前面兩個用加法判斷的不同.
#### Harley’s algorithm
```clike=
unsigned 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 Table[x >> 26];
}
```
* Harley’s algorithm 是使用雜湊法來判斷 leading zero 的個數, Table 代表的是 hash table .任意 int 輸入到 funtion 裡後,經由15到19行的處理,會變成除了 leading zero 以外的 bit 都變成 1 .因此,真正經由 hash function 運算的輸入只會有 32 種,而運算完的結果再藉由查表獲得 leading zero 的個數.
* 此方法的優點為運算時間為常數時間.
#### recursive version
```clike=
static const int mask[]={0,8,12,14};
static const int magic[]={2,1,0,0};
unsigned clz2(uint32_t x,int c)
{
if(!x && !c) return 32;
uint32_t upper = (x >> (16>>c));
uint32_t lower = (x & (0xFFFF>>mask[c]));
if(c==3) return upper?magic[upper]:2+magic[lower];
return upper?clz2(upper,c+1):(16>>(c)) + clz2(lower,c+1);
}
```
* 此方法似乎和 iteration version 原理相似,但是 lower 那裡有點看不太懂.
## 實驗測試
* 以下將有不同範圍的測試
* <big>100000 ~ 120000</big>
* <big>1000000~1020000</big>
* <big>10000000~10020000</big>
* <big>100000000~100020000</big>
* <big>1000000000~1000020000</big>
* 可以從以上各個範圍的測試觀察到說, recursive version 十分的不穩定,並有規律的跳動.
* harley 的運行結果十分平穩,不受範圍所影響.
* iteration 會隨著範圍數字的變大而增加時間.
* recursive version 是速度最慢且最不穩定的方法.
## 應用領域
* [密碼學中的編碼](https://books.google.com.tw/books?id=VaiYIZHduXQC&pg=PA50&lpg=PA50&dq=count+leading+zero++Cryptography&source=bl&ots=GWTEyF9DYM&sig=LN8klccBhw_PbmI2of8VHKSatj8&hl=zh-TW&sa=X&ved=0ahUKEwjw6eyf28nSAhUKgbwKHaqZCiUQ6AEIQTAF#v=onepage&q=count%20leading%20zero%20%20Cryptography&f=false)
* [unit counter](https://books.google.com.tw/books?id=EA4SBQAAQBAJ&pg=PA36&dq=count+leading+zero&hl=zh-TW&sa=X&redir_esc=y#v=onepage&q=count%20leading%20zero&f=false)
* [Digital Media Processing](https://books.google.com.tw/books?id=od1PLzHJbJYC&pg=PA266&dq=optimize+count+leading+zero&hl=zh-TW&sa=X&redir_esc=y#v=onepage&q=count%20leading&f=false)
Sign in with Wallet
Connect another wallet