在 C++ 标准库中，我发现只有一个浮点日志方法。现在我使用 log 来查找二叉树 ( floor(2log(index))) 中索引的级别。
代码（C++）：
int targetlevel = int(log(index)/log(2));
恐怕对于某些边缘元素（值为 2^n 的元素），log 将返回 n-1.999999999999 而不是 n.0。这种恐惧正确吗？如何修改我的陈述以使其始终返回正确答案？
问问题
76152 次
17 回答
83
如果您使用的是最新的 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;
}
于 2009-06-15T06:24:13.463 回答
53
您可以改用此方法：
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
注意：这将修改索引。如果您需要它保持不变，请创建另一个临时 int。
极端情况是索引为 0 时。如果索引 == 0，您可能应该单独检查并抛出异常或返回错误。
于 2009-06-15T05:47:37.183 回答
23
如果你只是想要一个快速的整数 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 的补码中设置的最高位）。我不建议使用它们，除非速度至关重要（我自己更喜欢可读性），但你应该知道它们的存在。
于 2009-06-15T05:59:03.727 回答
15
以 2 为底的整数对数
这是我为 64 位无符号整数所做的。这会计算以 2 为底的对数的下限，它相当于最高有效位的索引。这种方法对于大量数据来说非常快，因为它使用了一个展开的循环，该循环总是以 log₂64 = 6 步执行。
从本质上讲，它所做的是在序列 { 0 ≤ k ≤ 5: 2^(2^k) } = { 2³², 2¹⁶, 2⁸, 2⁴, 2², 2¹ } = { 4294967296, 65536, 256 , 16, 4, 2, 1 } 并将减去值的指数 k 相加。
int uint64_log2(uint64_t n)
{
#define S(k) if (n >= (UINT64_C(1) << k)) { i += k; n >>= k; }
int i = -(n == 0); S(32); S(16); S(8); S(4); S(2); S(1); return i;
#undef S
}
请注意，如果给定无效输入 0（这是初始-(n == 0)值检查的内容），则返回 –1。如果您从未期望使用 调用它n == 0，则可以替换int i = 0;初始化程序并将assert(n != 0);at entry 添加到函数中。
以 10 为底的整数对数
可以使用类似的方法计算以 10 为底的整数对数 - 测试的最大平方为 10¹⁶ 因为 log₁₀2⁶⁴ ≅ 19.2659...
int uint64_log10(uint64_t n)
{
#define S(k, m) if (n >= UINT64_C(m)) { i += k; n /= UINT64_C(m); }
int i = -(n == 0);
S(16,10000000000000000); S(8,100000000); S(4,10000); S(2,100); S(1,10);
return i;
#undef S
}
请注意，一个好的编译器会将此处的整数除法运算优化为乘法指令，因为除法始终是常数。（这很重要，因为与乘法指令相比，即使在最快的现代 CPU 上，整数除法指令仍然非常慢。）
于 2014-07-15T01:37:45.173 回答
10
这已在上述评论中提出。使用 gcc 内置函数：
static inline int log2i(int x) {
assert(x > 0);
return sizeof(int) * 8 - __builtin_clz(x) - 1;
}
static void test_log2i(void) {
assert_se(log2i(1) == 0);
assert_se(log2i(2) == 1);
assert_se(log2i(3) == 1);
assert_se(log2i(4) == 2);
assert_se(log2i(32) == 5);
assert_se(log2i(33) == 5);
assert_se(log2i(63) == 5);
assert_se(log2i(INT_MAX) == sizeof(int)*8-2);
}
于 2014-03-15T01:26:45.250 回答
9
于 2020-09-21T07:22:44.493 回答
5
如果您使用的是 C++11，则可以将其设为 constexpr 函数：
constexpr std::uint32_t log2(std::uint32_t n) noexcept
{
return (n > 1) ? 1 + log2(n >> 1) : 0;
}
于 2016-03-02T21:23:37.283 回答
3
我从未对您使用的公式的浮点精度有任何问题（并且快速检查从 1 到 2 31 - 1 的数字没有发现错误），但如果您担心，您可以使用此功能相反，它返回相同的结果，并且在我的测试中快了大约 66%：
int HighestBit(int i){
if(i == 0)
return -1;
int bit = 31;
if((i & 0xFFFFFF00) == 0){
i <<= 24;
bit = 7;
}else if((i & 0xFFFF0000) == 0){
i <<= 16;
bit = 15;
}else if((i & 0xFF000000) == 0){
i <<= 8;
bit = 23;
}
if((i & 0xF0000000) == 0){
i <<= 4;
bit -= 4;
}
while((i & 0x80000000) == 0){
i <<= 1;
bit--;
}
return bit;
}
于 2009-06-15T06:00:12.613 回答
2
int targetIndex = floor(log(i + 0.5)/log(2.0));
于 2009-06-15T05:51:25.990 回答
2
这不是标准的，也不一定是可移植的，但它通常可以工作。我不知道它的效率如何。
将整数索引转换为足够精度的浮点数。假设精度足够，表示将是准确的。
查找 IEEE 浮点数的表示，提取指数，并进行必要的调整以找到以 2 为底的对数。
于 2009-06-15T14:06:00.293 回答
2
上面也有类似的答案。这个答案
- 适用于 64 位数字
- 让您选择舍入类型和
- 包括测试/示例代码
职能：
static int floorLog2(int64_t x)
{
assert(x > 0);
return 63 - __builtin_clzl(x);
}
static int ceilLog2(int64_t x)
{
if (x == 1)
// On my system __builtin_clzl(0) returns 63. 64 would make more sense
// and would be more consistent. According to stackoverflow this result
// can get even stranger and you should just avoid __builtin_clzl(0).
return 0;
else
return floorLog2(x-1) + 1;
}
测试代码：
for (int i = 1; i < 35; i++)
std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
<<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;
于 2017-04-22T18:58:13.590 回答
1
此函数确定表示数字区间需要多少位：[0..maxvalue]。
unsigned binary_depth( unsigned maxvalue )
{
int depth=0;
while ( maxvalue ) maxvalue>>=1, depth++;
return depth;
}
通过从结果中减去 1，您得到floor(log2(x))，它是2的幂的精确表示。log2(x)x
xyy-1
00-1
110
221
321
432
532
632
732
843
于 2013-02-20T21:26:13.540 回答
1
int log2(int x) {
return sizeof(int)*8 - 1 - __builtin_clz(x);
}
假设你的 x > 0
于 2019-12-01T11:32:12.433 回答
0
您将树投影到多深？您可以将一个范围说... +/- 0.00000001 设置为数字以强制它为整数值。
我实际上不确定你会达到 1.99999999 这样的数字，因为你的 log2 在计算 2^n 值时不应该失去任何准确性（因为浮点四舍五入到最接近的 2 次方）。
于 2009-06-15T05:49:26.820 回答
0
我在这里写的这个函数
// The 'i' is for int, there is a log2 for double in stdclib
inline unsigned int log2i( unsigned int x )
{
unsigned int log2Val = 0 ;
// Count push off bits to right until 0
// 101 => 10 => 1 => 0
// which means hibit was 3rd bit, its value is 2^3
while( x>>=1 ) log2Val++; // div by 2 until find log2. log_2(63)=5.97, so
// take that as 5, (this is a traditional integer function!)
// eg x=63 (111111), log2Val=5 (last one isn't counted by the while loop)
return log2Val ;
}
于 2013-02-14T17:43:57.910 回答
0
重写Todd Lehman的答案更通用：
#include <climits>
template<typename N>
constexpr N ilog2(N n) {
N i = 0;
for (N k = sizeof(N) * CHAR_BIT; 0 < (k /= 2);) {
if (n >= static_cast<N>(1) << k) { i += k; n >>= k; }
}
return i;
}
Clang with-O3展开循环：
0000000100000f50 pushq %rbp
0000000100000f51 movq %rsp, %rbp
0000000100000f54 xorl %eax, %eax
0000000100000f56 cmpl $0xffff, %edi
0000000100000f5c setg %al
0000000100000f5f shll $0x4, %eax
0000000100000f62 movl %eax, %ecx
0000000100000f64 sarl %cl, %edi
0000000100000f66 xorl %edx, %edx
0000000100000f68 cmpl $0xff, %edi
0000000100000f6e setg %dl
0000000100000f71 leal (,%rdx,8), %ecx
0000000100000f78 sarl %cl, %edi
0000000100000f7a leal (%rax,%rdx,8), %eax
0000000100000f7d xorl %edx, %edx
0000000100000f7f cmpl $0xf, %edi
0000000100000f82 setg %dl
0000000100000f85 leal (,%rdx,4), %ecx
0000000100000f8c sarl %cl, %edi
0000000100000f8e leal (%rax,%rdx,4), %eax
0000000100000f91 xorl %edx, %edx
0000000100000f93 cmpl $0x3, %edi
0000000100000f96 setg %dl
0000000100000f99 leal (%rdx,%rdx), %ecx
0000000100000f9c sarl %cl, %edi
0000000100000f9e leal (%rax,%rdx,2), %ecx
0000000100000fa1 xorl %eax, %eax
0000000100000fa3 cmpl $0x1, %edi
0000000100000fa6 setg %al
0000000100000fa9 orl %ecx, %eax
0000000100000fab popq %rbp
当n为常数时，结果在编译时计算。
于 2018-06-16T19:07:08.610 回答
0
考虑到浮点数的工作方式（粗略地说，尾数 * 2^exponent），那么任何不超过 2^127 的数字（即 2 的幂）都将准确无误地表示。
这确实给出了一个微不足道但相当老套的解决方案——将浮点数的位模式解释为整数，然后只看指数。这是上面大卫桑利的解决方案。
float f = 1;
for (int i = 0; i < 128; i++)
{
int x = (*(int*)(&f)>>23) - 127;
int l = int(log(f) / log(2));
printf("i = %d, log = %d, f = %f quick = %d\n",
i, l, f, x);
f *= 2;
}
任何整数都可以表示为浮点数是不正确的 - 只有那些位数少于尾数的整数才能表示。在 32 位浮点数中，这是 23 位的价值。
于 2019-06-11T09:57:54.163 回答