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

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

uint8_t clz_recur( uint32_t x ){
    return x ? clz_recur( x >> 1) - 1 : 32;
}

• Binary Search

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

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