clz

contributed by <Sisker1111>

tags: 進階電腦系統理論與實作

CLZ實作:

int clz(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);
}

CTZ實作:

CTZ 可以通過把 x 的每個 Bits 反轉，在實施 CLZ.

/// reverse
uint32_t reverse(uint32_t x){
    uint32_t n = x;
    n = ((n & 0xffff0000) >> 16) | ((n & 0x0000ffff) << 16);
    n = ((n & 0xff00ff00) >>  8) | ((n & 0x00ff00ff) <<  8);
    n = ((n & 0xf0f0f0f0) >>  4) | ((n & 0x0f0f0f0f) <<  4);
    n = ((n & 0xcccccccc) >>  2) | ((n & 0x33333333) <<  2);
    n = ((n & 0xaaaaaaaa) >>  1) | ((n & 0x55555555) <<  1);
    return n;
}
/// CTZ
int ctz(uint32_t x) {
    x = reverse(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);
}

或者使用以下方式:

uint32_t ctz(uint32_t x) {
    if(x==0) return 0;
    int n=0;
    if(!(x&0x0000FFFF)) { n+=16; x>>=16;}
    if(!(x&0x000000FF)) { n+=8; x>>=8;}
    if(!(x&0x0000000F)) { n+=4; x>>=4;}
    if(!(x&0x00000003)) { n+=2; x>>=2;}
    if(!(x&0x00000001)) { n+=1; x>>=1;}
    return n;
}