HackMD
2017q1 Homework1 (clz)
contributed by <zmke>
開發環境
OS: Ubuntu 16.04 LTS
Architecture: x86_64
CPU 作業模式： 32-bit, 64-bit
Byte Order: Little Endian
CPU(s): 4
Model name: Intel® Core™ i5-4200H CPU @ 2.80GHz
L1d 快取： 32K
L1i 快取： 32K
L2 快取： 256K
L3 快取： 3072K
Count Leading Zero
- 計算從 MSB 開始往下到第一個 1 有幾個 0
recursive version
static const int mask[]= {0,8,12,14};
static const int magic[]= {2,1,0,0};
unsigned clz2(uint32_t x,int c)
{
if (!x && !c) return 32;
uint32_t upper = (x >> (16>>c));
uint32_t lower = (x & (0xFFFF>>mask[c]));
if (c == 3) return upper ? magic[upper] : 2 + magic[lower];
return upper ? clz2(upper, c + 1) : (16 >> (c)) + clz2(lower, c + 1);
}
- 從
clz2(x, 0)開始，將 x 分成兩半(upper and lower) - 若
upper == 0將lower代入下層遞迴，否則代入upper c == 3時終止，用magic[]來判斷剩下的兩個 bit 開頭有幾個 0- 將下層的結果加上確定的 0 數得到答案
iteration version
static inline __attribute((always_inline))
unsigned 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);
}
- y 與 upper 類似，用來紀錄前一半的 bit string
y != 0將關注的 bit string 縮小到 y ，繼續迴圈y == 0向 LSB 方向擴大 c 個 bit- 直到
c == 0終止，回傳 n-x ， x 是最後剩下的一個 bit 會等於 1 或 0
byte shift technique
static inline __attribute((always_inline))
unsigned clz(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;
}
