# 2016q3 Homework1(clz)
contributed by <`shelly4132`>

### Reviewed by `0140454`

* 應該善用 [.gitignore](https://git-scm.com/docs/gitignore) 來排除編譯出來的可執行檔案。
* [commit "add recursive version"](https://github.com/shelly4132/clz-tests/commit/09406e975c89d4cfad75e2e96c2d87bcbb882bec) 中包含多種實作方式，與 commit message 有些不符合。
* 未修正並實作 Harley 演算法。
* 未提出 clz 可應用之處。
* 未提及驗證正確性的結果。
* 可善用圖表來呈現各方式的效能，並進一步分析。

## 開發環境
* 作業系統：Ubuntu 16.04 LTS
* CPU：Intel(R) Core(TM) i5-4200U CPU @ 1.60GHz
* Cache：
* L1d cache: 32K
* L1i cache: 32K
* L2 cache: 256K
* L3 cache: 3072K

## 目標
閱讀 [重新理解數值](/s/SkKZBXZT) 裡頭關於 count leading zero ([clz](https://en.wikipedia.org/wiki/Find_first_set#CLZ)) 的描述，設計實驗，比較 32-bit 數值對以下實做的效能差異：
* recursive version
* iteration version
* binary search technique
* byte-shift version
* Harley's algorithm

## builtin_clz()
* Returns the number of leading 0-bits in x, starting at the most significant bit position.
If x is 0, the result is undefined.

int __builtin_clz (unsigned int x)

利用GCC提供的```__builtin_clz (unsigned int x)```去檢查[重新理解數值](/s/SkKZBXZT)裡，iteration、binary search、byte shift 算出來的結果。

for(uint32_t i=1; i<UINT_MAX; i++){
#if defined(ITERATIVE)
	assert(iterative_clz(i) == __builtin_clz(i));
#endif
#if defined(BINARY)
	assert(binary_clz(i) == __builtin_clz(i));
#endif
#if defined(BYTE)
	assert(byte_clz(i) == __builtin_clz(i));
#endif
}
	printf("Done!\n");

* assert() 裡面放的判斷式，如果「不成立的話」，程式便不會繼續執行下去。

## Recursive
參照老師給的範例去改的，其實算法都大同小異。

int recursive_clz(uint32_t x, int shift)
{
	if(x == 0)
		return 32;
	if(!shift) 
		return 0;

	uint16_t upper = (x >> shift); 
	uint16_t lower = (x & (0xFFFF >> (16 - shift)));
	return upper ? recursive_clz(upper,shift>>1) : shift + recursive_clz(lower,shift>>1);
}

用之前教的time指令去看每一種算法的時間，可以發現recursive的版本比其他版本的時間要高出許，這可能是因為recursive的版本多了很多function call的成本。

time ./check_iterative
Done!
86.34user 0.05system 1:26.39elapsed 100%CPU (0avgtext+0avgdata 1304maxresident)k
0inputs+0outputs (0major+64minor)pagefaults 0swaps
time ./check_binary
Done!
28.20user 0.00system 0:28.20elapsed 100%CPU (0avgtext+0avgdata 1168maxresident)k
0inputs+0outputs (0major+61minor)pagefaults 0swaps
time ./check_byte
Done!
30.46user 0.02system 0:30.49elapsed 99%CPU (0avgtext+0avgdata 1168maxresident)k
0inputs+0outputs (0major+61minor)pagefaults 0swaps
time ./check_recursive
Done!
180.16user 0.27system 3:00.43elapsed 100%CPU (0avgtext+0avgdata 1256maxresident)k
0inputs+0outputs (0major+61minor)pagefaults 0swaps

## 參考
* [重新理解數值](https://hackmd.io/s/SkKZBXZT)
* [VVN](https://hackmd.io/CwMwzADCDGBGCsBaWF4UcApgDnd+mAjIoZgEwDswAJmSBGdBEA==?view)