# 2016q3 Homework1 (clz)

## 開發環境

* OS:Lubuntu 16.04 LTS
* Memory: 8 GB
* CPU:
* Name:
* Intel(R) Core(TM) i5-4200H CPU @ 2.80GHz
* Cache:
* L1d Cache： 32K
* L1i Cache： 32K
* L2 Cache： 256K
* L3 Cache： 3072K

## clz簡介

目標：在由一連串有序的bit組成的排列中，找尋出現第一個1前含有的0之總數。

## 建立test case

為了先驗證以下幾種clz的演算法正確運作，因此先建立一個可測試所有32bit的程式。

思考過程：
我們必須先針對每個數字做測試，所以會有個基本的迴圈，從0x00000000到0xFFFFFFFF，但是要考量邊界避免溢值所以把迴圈設計成0x00000000到0xFFFFFFFE，0xFFFFFFFF另外判斷

for(uint32_t i=0; i<UINT_MAX; i++){	
}
/* test UINT_MAX */

而要如何知道每個i的clz是多少呢？，我想到[重新理解數值](https://hackmd.io/s/SkKZBXZT)的`x & (x - 1) == 0`，當clz值改變時，正好是二的次方，在將程式碼改成以下

for(uint32_t i=0,j=33; i<UINT_MAX; i++){
    if( i & (i-1) == 0){
        j--;
        printf("i:%u,j:%u\n",i,j);
    }
    /* test func(i)==j; if neq, break*/
}
if(i==UNIT_MAX){
    /* test func(UINT_MAX) == 0 */
}
else{
    /* error message*/
}

註：i=0時 i&(i-1)= 0x00000000 & 0xFFFFFFF(溢位) =0 所以j從33開始。

之後我們就可以像compute-pi的benchmark模式做測試了。

## 分析各個clz演算法

待續，來不及做QQ

### recursive version

### iteration version

### binary search technique

### byte-shift version

### Harley’s algorithm

## 參考資料