如何在 C++ 中做一个整数 log2()？
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/994593/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
How to do an integer log2() in C++?
提问by Peter Smit
In the C++ standard libraries I found only a floating point log method. Now I use log to find the level of an index in a binary tree ( floor(2log(index))).
在 C++ 标准库中，我只找到了一个浮点日志方法。现在我使用 log 来查找二叉树 ( floor(2log(index))) 中索引的级别。
Code (C++):
代码（C++）：
int targetlevel = int(log(index)/log(2));
I am afraid that for some of the edge elements (the elements with value 2^n) log will return n-1.999999999999 instead of n.0. Is this fear correct? How can I modify my statement so that it always will return a correct answer?
恐怕对于某些边缘元素（值为 2^n 的元素），日志将返回 n-1.999999999999 而不是 n.0。这种恐惧是否正确？如何修改我的陈述，以便它始终返回正确答案？
回答by Matt J
If you are on a recent-ish x86 or x86-64 platform (and you probably are), use the bsrinstruction which will return the position of the highest set bit in an unsigned integer. It turns out that this is exactly the same as log2(). Here is a short C or C++ function that invokes bsrusing inline ASM:
如果您使用的是最新的 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;
}
回答by Igor Krivokon
You can use this method instead:
您可以改用此方法：
int targetlevel = 0;
while (index >>= 1) ++targetlevel;
Note: this will modify index. If you need it unchanged, create another temporary int.
注意：这将修改索引。如果您需要它保持不变，请创建另一个临时 int。
The corner case is when index is 0. You probably should check it separately and throw an exception or return an error if index == 0.
极端情况是 index 为 0 时。您可能应该单独检查它并在 index == 0 时抛出异常或返回错误。
回答by paxdiablo
If you just want a fast integer log2operation, the following function mylog2()will do it without having to worry about floating-point accuracy:
如果你只是想要一个快速的整数 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;
}
The code above also has a small test harness so you can check the behaviour:
上面的代码还有一个小的测试工具，所以你可以检查行为：
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
It will return UINT_MAXfor an input value of 0 as an indication of an undefined result, so that's something you should check for (no valid unsigned integer will have a logarithm that high).
它将返回UINT_MAX输入值 0 作为未定义结果的指示，因此您应该检查一下（没有有效的无符号整数会有那么高的对数）。
By the way, there are some insanely fast hacks to do exactly this (find the highest bit set in a 2's complement number) available from here. I wouldn't suggest using them unless speed is of the essence (I prefer readability myself) but you should be made aware that they exist.
顺便说一句，有一些疯狂的快速黑客做的正是这一点（找到一个2的补数的最高位设置），可从这里。我不建议使用它们，除非速度至关重要（我自己更喜欢可读性），但您应该意识到它们的存在。
回答by Todd Lehman
Base-2 Integer Logarithm
以 2 为底的整数对数
Here is what I do for 64-bit unsigned integers. This calculates the floor of the base-2 logarithm, which is equivalent to the index of the most significant bit. This method is smokingly fastfor large numbers because it uses an unrolled loop that executes always in log?64 = 6 steps.
这是我对 64 位无符号整数所做的。这将计算以 2 为底的对数的下限，它相当于最高有效位的索引。这种方法对于大数字来说非常快，因为它使用一个展开的循环，该循环总是在 log?64 = 6 步中执行。
Essentially, what it does is subtracts away progressively smaller squares in the sequence { 0 ≤ k ≤ 5: 2^(2^k) } = { 232, 21?, 2?, 2?, 22, 21 } = { 4294967296, 65536, 256, 16, 4, 2, 1 } and sums the exponents k of the subtracted values.
本质上，它的作用是减去序列 { 0 ≤ k ≤ 5: 2^(2^k) } = { 232, 21?, 2?, 2?, 22, 21 } = { 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
}
Note that this returns –1 if given the invalid input of 0 (which is what the initial -(n == 0)is checking for). If you never expect to invoke it with n == 0, you could substitute int i = 0;for the initializer and add assert(n != 0);at entry to the function.
请注意，如果给定无效输入 0（这是初始-(n == 0)检查的内容），则返回 –1 。如果您从不希望使用 调用它n == 0，则可以替换int i = 0;初始化程序并assert(n != 0);在函数的入口处添加。
Base-10 Integer Logarithm
以 10 为底的整数对数
Base-10 integer logarithms can be calculated using similarly —?with the largest square to test being 101? because log??2?? ? 19.2659...
可以使用类似的方法计算以 10 为底的整数对数 -? 测试的最大平方是 101？因为日志??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
}
回答by zbyszek
This has been proposed in the comments above. Using gcc builtins:
这已在上述评论中提出。使用 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);
}
回答by Kelmar
If you're using C++11 you can make this a constexpr function:
如果您使用的是 C++11，则可以将其设为 constexpr 函数：
constexpr std::uint32_t log2(std::uint32_t n)
{
return (n > 1) ? 1 + log2(n >> 1) : 0;
}
回答by P Daddy
I've never had any problem with floating-point accuracy on the formula you're using (and a quick check of numbers from 1 to 231- 1 found no errors), but if you're worried, you can use this function instead, which returns the same results and is about 66% faster in my tests:
我从来没有对您使用的公式的浮点精度有任何问题（并且快速检查从 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;
}
回答by David Thornley
This isn't standard or necessarily portable, but it will in general work. I don't know how efficient it is.
这不是标准的，也不一定是可移植的，但它通常可以工作。我不知道它的效率如何。
Convert the integer index into a floating-point number of sufficient precision. The representation will be exact, assuming the precision is sufficient.
将整数索引转换为足够精度的浮点数。假设精度足够，表示将是精确的。
Look up the representation of IEEE floating-point numbers, extract the exponent, and make the necessary adjustment to find the base 2 log.
查找 IEEE 浮点数的表示形式，提取指数，并进行必要的调整以找到以 2 为底的对数。
回答by maxaposteriori
int targetIndex = floor(log(i + 0.5)/log(2.0));
回答by Trade-Ideas Philip
There are similar answers above. This answer
上面也有类似的回答。这个回答
- Works with 64 bit numbers
- Lets you choose the type of rounding and
- Includes test/sample code
- 适用于 64 位数字
- 让您选择舍入的类型和
- 包括测试/示例代码
Functions:
职能：
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;
}
Test Code:
测试代码：
for (int i = 1; i < 35; i++)
std::cout<<"floorLog2("<<i<<") = "<<floorLog2(i)
<<", ceilLog2("<<i<<") = "<<ceilLog2(i)<<std::endl;
