在C ++標準庫中，我僅找到一個浮點日志方法。現在，我使用log在二叉樹（floor(2log(index))）中查找索引的級別。代碼（C ++）：int targetlevel = int(log(index)/log(2));恐怕對于某些邊緣元素（值為2 ^ n的元素），日志將返回n-1.999999999999，而不是n.0。這種恐懼正確嗎？我該如何修改我的陳述，使其始終返回正確答案？
3 回答
慕少森
TA貢獻2019條經驗 獲得超9個贊
您可以改用以下方法：
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
注意：這將修改索引。如果您不需要它，則創建另一個臨時int。
極端情況是index為0時。如果index == 0，則可能應單獨檢查它并引發異?；蚍祷劐e誤。
弒天下
TA貢獻1818條經驗 獲得超8個贊
如果您使用的是最近使用的x86或x86-64平臺（可能是），請使用bsr指令，該指令將以無符號整數形式返回最高設置位的位置。事實證明，這與log2（）完全相同。這是bsr使用內聯ASM 調用的簡短C或C ++函數：
#include <stdint.h>
static inline uint32_t log2(const uint32_t x) {
uint32_t y;
asm ( "\tbsr %1, %0\n"
: "=r"(y)
: "r" (x)
);
return y;
}
素胚勾勒不出你
TA貢獻1827條經驗 獲得超9個贊
如果只想進行快速整數log 2操作，則可以使用以下函數mylog2()，而不必擔心浮點精度：
#include <limits.h>
static unsigned int mylog2 (unsigned int val) {
if (val == 0) return UINT_MAX;
if (val == 1) return 0;
unsigned int ret = 0;
while (val > 1) {
val >>= 1;
ret++;
}
return ret;
}
#include <stdio.h>
int main (void) {
for (unsigned int i = 0; i < 20; i++)
printf ("%u -> %u\n", i, mylog2(i));
putchar ('\n');
for (unsigned int i = 0; i < 10; i++)
printf ("%u -> %u\n", i+UINT_MAX-9, mylog2(i+UINT_MAX-9));
return 0;
}
上面的代碼還具有一個小的測試工具，因此您可以檢查行為：
0 -> 4294967295
1 -> 0
2 -> 1
3 -> 1
4 -> 2
5 -> 2
6 -> 2
7 -> 2
8 -> 3
9 -> 3
10 -> 3
11 -> 3
12 -> 3
13 -> 3
14 -> 3
15 -> 3
16 -> 4
17 -> 4
18 -> 4
19 -> 4
4294967286 -> 31
4294967287 -> 31
4294967288 -> 31
4294967289 -> 31
4294967290 -> 31
4294967291 -> 31
4294967292 -> 31
4294967293 -> 31
4294967294 -> 31
4294967295 -> 31
它將返回UINT_MAX輸入值0來指示未定義的結果，因此您應檢查一下（沒有有效的無符號整數的對數應很高）。
順便說一句，有一些瘋狂的快速黑客做的正是這一點（找到最高位2的補數設置），可從這里。除非速度至關重要（我個人更喜歡可讀性），否則我不建議使用它們，但是應該使您意識到它們的存在。
- 3 回答
- 0 關注
- 2120 瀏覽
添加回答
舉報
0/150
提交
取消