# 2016q3 Homework1 (clz) contributed by <`HaoTse`> --- ## 目標 - recursive version - iteration version - binary search technique - byte-shift version - Harley’s algorithm --- ## Check clz 首先撰寫確認計算出來的值正確的程式，先使用 [重新理解數值](https://hackmd.io/s/SkKZBXZT) 中提到的 `iteration version`, `binary search technique`, `byte-shift version` 來實作，並用 gcc 提供的 `int __builtin_clz (unsigned int x)` 作為正確輸出。 > 注意. `__builtin_clz (unsigned int x)` 不能傳入 0，否則會是 undefined。[name=鄭皓澤] ---- ### 結果輸出 - `$ make check` ```shell time ./test_iterator Very Good 100.55user 0.01system 1:40.58elapsed 99%CPU (0avgtext+0avgdata 1252maxresident)k 0inputs+0outputs (0major+60minor)pagefaults 0swaps time ./test_bin_search Very Good 34.66user 0.01system 0:34.68elapsed 99%CPU (0avgtext+0avgdata 1168maxresident)k 0inputs+0outputs (0major+61minor)pagefaults 0swaps time ./test_byte_shift Very Good 39.28user 0.05system 0:39.33elapsed 99%CPU (0avgtext+0avgdata 1256maxresident)k 0inputs+0outputs (0major+63minor)pagefaults 0swaps ``` 明顯看出 iterator 版本明顯慢很多。 > [time 指令](http://linux.vbird.org/linux_basic/0320bash/csh/no3-8-07.html)的輸出格式可參照連結。[name=鄭皓澤] --- ## Recursive 版本 加入以下程式碼 ```clike= int recursive_clz(uint32_t x, int offset) { //when input = 0 if(x == 0) return 32; if(offset == 0) return 0; uint16_t upper = (x >> offset); uint16_t lower = (x & (0xFFFF >> (16 - offset))); return upper ? recursive_clz(upper, offset >> 1) : offset + recursive_clz(lower, offset >> 1); } ``` ---- - `$ make check` 輸出 ```shell time ./test_iterator Very Good 101.70user 0.00system 1:41.71elapsed 99%CPU (0avgtext+0avgdata 1212maxresident)k 0inputs+0outputs (0major+63minor)pagefaults 0swaps time ./test_bin_search Very Good 35.92user 0.00system 0:35.93elapsed 99%CPU (0avgtext+0avgdata 1268maxresident)k 0inputs+0outputs (0major+61minor)pagefaults 0swaps time ./test_byte_shift Very Good 41.53user 0.09system 0:41.63elapsed 99%CPU (0avgtext+0avgdata 1252maxresident)k 0inputs+0outputs (0major+61minor)pagefaults 0swaps time ./test_recursive Very Good 207.42user 0.00system 3:27.43elapsed 99%CPU (0avgtext+0avgdata 1236maxresident)k 0inputs+0outputs (0major+63minor)pagefaults 0swaps ``` 發現 recursive 跑的非常久，接下來使用 gnuplot 畫圖方便做比較。 ---- - gnuplot 輸出 ![](https://i.imgur.com/Ixnz2z6.png) --- ###### tags: `HaoTse` `sysprog21` `clz`