很棒的編程資源，Bit Twiddling Hacks，在這里提出了以下方法來計(jì)算32位整數(shù)的log2：#define LT(n) n, n, n, n, n, n, n, n, n, n, n, n, n, n, n, nstatic const char LogTable256[256] = { -1, 0, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3, LT(4), LT(5), LT(5), LT(6), LT(6), LT(6), LT(6), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7), LT(7)};unsigned int v; // 32-bit word to find the log ofunsigned r; // r will be lg(v)register unsigned int t, tt; // temporariesif (tt = v >> 16){ r = (t = tt >> 8) ? 24 + LogTable256[t] : 16 + LogTable256[tt];}else { r = (t = v >> 8) ? 8 + LogTable256[t] : LogTable256[v];}并提到查找表方法僅需執(zhí)行大約7個(gè)操作即可查找32位值的日志。如果擴(kuò)展為64位，則大約需要9次操作。但是，可惜的是，它沒有提供任何其他有關(guān)將算法擴(kuò)展到64位整數(shù)的實(shí)際方法的信息。關(guān)于這種64位算法的外觀有何暗示？
3 回答
qq_遁去的一_1
TA貢獻(xiàn)1725條經(jīng)驗(yàn) 獲得超8個(gè)贊
如果您使用的是GCC，則在這種情況下不需要查找表。
GCC提供了一個(gè)內(nèi)置函數(shù)來確定前導(dǎo)零的數(shù)量：
內(nèi)置函數(shù)： 從最高有效位位置開始，返回x中前導(dǎo)0位的數(shù)量。如果x為0，則結(jié)果不確定。int __builtin_clz (unsigned int x)
因此，您可以定義：
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
它適用于任何unsigned long long int。結(jié)果四舍五入。
對(duì)于x86和AMD64，GCC會(huì)將其編譯為bsr指令，因此解決方案非?？欤ū炔檎冶砜斓枚啵?。
工作示例：
#include <stdio.h>
#define LOG2(X) ((unsigned) (8*sizeof (unsigned long long) - __builtin_clzll((X)) - 1))
int main(void) {
unsigned long long input;
while (scanf("%llu", &input) == 1) {
printf("log(%llu) = %u\n", input, LOG2(input));
}
return 0;
}
鴻蒙傳說
TA貢獻(xiàn)1865條經(jīng)驗(yàn) 獲得超7個(gè)贊
我正在嘗試通過蠻力強(qiáng)制使用幻數(shù)將O（lg（N））操作中的N位整數(shù)的對(duì)數(shù)基數(shù)2與乘法和查找轉(zhuǎn)換為64位。不用說這需要一段時(shí)間。
然后，我找到了戴斯蒙德的答案，并決定嘗試以他的幻數(shù)作為起點(diǎn)。由于我有一個(gè)6核處理器，因此我從0x07EDD5E59A4E28C2 / 6倍數(shù)開始并行運(yùn)行它。我很驚訝它立即發(fā)現(xiàn)了一些東西。原來0x07EDD5E59A4E28C2 / 2工作。
因此，這是0x07EDD5E59A4E28C2的代碼，可節(jié)省您的移位并減去：
int LogBase2(uint64_t n)
{
static const int table[64] = {
0, 58, 1, 59, 47, 53, 2, 60, 39, 48, 27, 54, 33, 42, 3, 61,
51, 37, 40, 49, 18, 28, 20, 55, 30, 34, 11, 43, 14, 22, 4, 62,
57, 46, 52, 38, 26, 32, 41, 50, 36, 17, 19, 29, 10, 13, 21, 56,
45, 25, 31, 35, 16, 9, 12, 44, 24, 15, 8, 23, 7, 6, 5, 63 };
n |= n >> 1;
n |= n >> 2;
n |= n >> 4;
n |= n >> 8;
n |= n >> 16;
n |= n >> 32;
return table[(n * 0x03f6eaf2cd271461) >> 58];
}
- 3 回答
- 0 關(guān)注
- 1156 瀏覽
添加回答
舉報(bào)
0/150
提交
取消