# 2016q3 Homework1 (clz) contributed by <`f5120125`> ###### tags: `sysprog` ## 開發環境 #### Ubuntu 14.04 LTS - CPU: Intel® Core™ i5 CPU 650 @ 3.20GHz × 4 - Mem: 8 GiB - Cache: L1d cache: 32 KB L1i cache: 32 KB L2 cache: 256 KB L3 cache: 4096 KB ## Counting Leading Zero - ### Iterative ```clike= uint8_t clz_iter( 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 ); } ``` - ### Recursive ```clike= uint8_t clz_recur( uint32_t x ){ return x ? clz_recur( x >> 1) - 1 : 32; } ``` - ### Binary Search ```clike= uint8_t clz_binary_search( 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 ```clike= uint8_t clz_byte_shift( 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; } ``` ## CLZ的應用 參考[[1]] - [ ] floating point 的實作 ## Reference [[1]] https://en.wikipedia.org/wiki/Find_first_set#Applications [ 1 ]:https://en.wikipedia.org/wiki/Find_first_set#Applications