# 2017q1 Homework1 (clz) contributed by <`Hong`> ###### tags: `sysprog2017` `clz` `time` `gnuplot` `king1224` ## 開發環境 ``` OS: 16.04.1 Ubuntu 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-4200H CPU @ 2.80GHz 製程： 3 CPU MHz： 2913.305 CPU max MHz: 3400.0000 CPU min MHz: 800.0000 BogoMIPS: 5587.41 虛擬： VT-x L1d 快取： 32K L1i 快取： 32K L2 快取： 256K L3 快取： 3072K NUMA node0 CPU(s): 0-3 ``` ## clz clz 為 count leading zero 的縮寫，對於一個以二元表示的數，計算以二元表示時有多少個 0 在前面，例如在 32 bit 中以十進位表示的`32769`，以二進位表示時為`00000000000000001000000000000001`，最前面有16個連續的 0，因此計算此數的clz可得到 16。 ## 實驗 對於[劉亮谷的實驗紀錄](https://hackmd.io/s/BJBZn6Q6#)解釋個別實作的運作原理 以下介紹幾個計算 clz 的方法 ### iteration ```clike= unsigned 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); } ``` 將 32 bits 每次二分來檢查，第一次進入 do-while 迴圈時，y 會得到 x 的前 16 bits(要計算 clz 的數的前 16 bits 高位)，如果 y 有值，表示第 1~16 bits 不可能為 leading zero 的一部分，因此 n - c，減掉二分時不可能的那一半，且只需檢查第 17~32 bits，因此 x = y，若 y 為 0，leading zero 的最大可能值不變，因此 n 不改變，迴圈中 c 每次除以二，對剩下的一半再二分，到 c == 1 時，只檢查剩下 2 bits 的其中 1 bit，因此最後必須 return (n - x)，來檢查最後剩下的那一個 bit 是否為 0。 ### recursive ```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); } ``` 以 upper, lower 將每次要判斷的部份二分成兩個部份，最後兩行的 return 判斷高位的 bits 是否全為 0，若是則檢查剩下的低位，反之則檢查高位。 ### binary search ```clike= unsigned 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; } ``` 每次將要判斷的部份與中間值做比較，若較大則代表高位不全為 0，接著往高位的中間值比較前一半是否為 0，若較小則表示高位全為 0，將 n 加上特定數字並往低位比較還有多少 0。 ### byte-shift ```clike= unsigned 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; } ``` 每次將要判斷的分成兩部份，shift right 之後只剩高位，若高位為 0 則 leading zeros 需要增加，反之則直接往後檢查。 ### Harley's algorithm ```clike= unsigned clz(uint32_t x) { // CTZ table #ifdef CTZ 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, }; // CLZ table #else static uint8_t const Table[] ={ 32,31, 0,16, 0,30, 3, 0,15, 0, 0, 0,29,10, 2, 0, 0, 0,12,14,21, 0,19, 0, 0,28, 0,25, 0, 9, 1, 0, 17, 0, 4, 0, 0, 0,11, 0,13,22,20, 0,26, 0, 0,18, 5, 0, 0,23, 0,27, 0, 6,0,24, 7, 0, 8, 0, 0, 0 }; #endif /* 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)]; } ``` line27~line31： 將 x 第一個出現 1 的 bit 後面全部的 bits 都設為 1 line34~line37： 不知是如何經過這堆神奇的運算及神奇的表格就可以得到正確答案了 >閱讀 [0xff07 大神的共筆](https://hackmd.io/s/rkTYU0vKx#)得到很完整的解答 >[name=洪正皇][color=#e091df]