contribute by <kaizsv
>
int recursive(uint32_t N, int length)
{
int shift = length >> 1;
int left = 32 - shift;
uint32_t MAX = 0xFFFFFFFF;
uint16_t upper = (N >> shift) & (MAX >> left);
uint16_t lower = (N & (MAX >> left));
if (shift == 1) {
return upper ? 0 : (lower ? 1 : 2);
}
return upper ? recursive(upper, shift) : shift + recursive(lower, shift);
}
這個一直試不好,後來看了這篇把table
的順序調一下,我在程式碼內都有插入assert
確保這些修改的程式碼是對的。
int harley_algorithm(uint32_t N)
{
static int const table[] = {
32, 31, 0xff, 16, 0xff, 30, 3, 0xff,
15, 0xff, 0xff, 0xff, 29, 10, 2, 0xff,
0xff, 0xff, 12, 14, 21, 0xff, 19, 0xff,
0xff, 28, 0xff, 25, 0xff, 9, 1, 0xff,
17, 0xff, 4, 0xff, 0xff, 0xff, 11, 0xff,
13, 22, 20, 0xff, 26, 0xff, 0xff, 18,
5, 0xff, 0xff, 23, 0xff, 27, 0xff, 6,
0xff, 24, 7, 0xff, 8, 0xff, 0, 0xff
};
N = N | (N >> 1);
N = N | (N >> 2);
N = N | (N >> 4);
N = N | (N >> 8);
N = N | (N >> 16);
N = (N << 3) - N;
N = (N << 8) - N;
N = (N << 8) - N;
N = (N << 8) - N;
return table[N >> 26];
}
直接下make plot
就會產生這兩張,上面是i = 0 ~ 1,000,000
每個點的時間,若是 32bit 太花時間,就算加上OpenMP
還是要很久,且檔案很大根本塞不進記憶體,就先算到1,000,000。
下面是1,000,000次的平均值,就我的結果而言,binary search and bit shift
的
assigment_4
clz