有没有办法编写以2为底的对数函数 log(base 2)?
C语言中有两个内置函数 -->
1. log 是以自然数e为底。
2. log10 是以10为底。
但我需要以2为底的log函数。如何计算呢?
14个回答
222
简单数学：
log2 (x) = logy (x) / logy (2)
其中 y 可以是任何值，在标准对数函数中通常为 10 或 e。
- Adam Crume
58
如果您正在寻找一个积分结果，您可以确定值中最高的位并返回其位置。
- tomlogic
3
28这里还有一个不错的位运算方法（源于Java的
Integer.highestOneBit(int)方法）：i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1);。 - Joey42当
i 右移一位后，重复执行 { ++l; } 直到 i 为 0。 - Lee Daniel Crocker4假设整数是32位宽度，那么就可以这样做，对吧Joey？但是如果是64位宽度，需要额外加上
i>>32。不过由于Java只有32位整数，所以没问题。对于C/C++来说，需要考虑这个问题。 - Zoso45
#define M_LOG2E 1.44269504088896340736 // log2(e)
inline long double log2(const long double x){
return log(x) * M_LOG2E;
}
（乘法可能比除法更快）
- logicray
1
2我只是想澄清一下 - 使用对数转换规则 + log_2(e) = 1/log_e(2) 这个事实--> 我们得到了结果。 - Guy L
22
log2(int n) = 31 - __builtin_clz(n)
- w00t
9
- Patrick
8
11请注意，您可以预先计算log10(2)以提高性能。 - corsiKa
3因为
log10()是C标准中定义的函数，所以编译器可以对其进行特殊处理，包括预先计算结果，这也是@Johannes建议的内容。 - caf+1 @caf。 我从未尝试过使用
log，但我已经多次看到使用 sqrt 进行这样的优化。 - Carl Norum1@CarlNorum：我刚刚检查了一下，至少gcc 4.7会用一个常数替换
log10(2)。 - caf@abelenky：如果编译器可以验证函数遵循某些作用域规则（即仅使用参数和局部变量，并且仅调用遵循相同规则的函数），则它可以知道这一点。现在的编译器非常智能化，如果它没有被替换掉，我会感到惊讶。 - Chris Hayes
显示剩余3条评论
9
如果要使其更快，您可以使用查找表，就像在“位操作技巧”（仅限整数log2）中所示。请参考Bit Twiddling Hacks。
uint32_t v; // find the log base 2 of 32-bit v
int r; // result goes here
static const int MultiplyDeBruijnBitPosition[32] =
{
0, 9, 1, 10, 13, 21, 2, 29, 11, 14, 16, 18, 22, 25, 3, 30,
8, 12, 20, 28, 15, 17, 24, 7, 19, 27, 23, 6, 26, 5, 4, 31
};
v |= v >> 1; // first round down to one less than a power of 2
v |= v >> 2;
v |= v >> 4;
v |= v >> 8;
v |= v >> 16;
r = MultiplyDeBruijnBitPosition[(uint32_t)(v * 0x07C4ACDDU) >> 27];
此外，您应该查看编译器内置方法，例如 _BitScanReverse，因为它可能完全在硬件中计算，因此速度更快。
还要查看可能的重复内容 如何在C++中执行整数log2()？
- bkausbk
4
为什么要在最后进行乘法和表查找？你不能只做(v+1)吗？这会将其舍入到下一个2的幂。然后，您可以向右移动一位以将其舍入到下一个2的幂。 - Safayet Ahmed
@SafayetAhmed，请描述您想如何使用该方法找到一个数字的log2。我不知道有更简单的方法来获得该值。除了使用上面的算术与查找表之外，人们可以使用迭代/递归算法或使用专用/内置硬件进行计算。 - bkausbk
假设一个32位变量v的二进制位从0（LSB）到N（MSB）编号，假设v中最高有效位是n。那么说n代表floor(log2(v))是正确的吗？你不仅仅只关心如何根据v找到n吗？ - Safayet Ahmed
我意识到我描述的只会给你最接近的2的幂，而不是实际的对数。乘法和表查找是用于从2的幂到对数的转换。您正在将数字0x07C4ACDD向左移动一定量。左移的量取决于2的幂。该数字是这样的，以至于任何连续的5位序列都是唯一的。
(0000 0111 1100 0100 0110 1100 1101 1101) 给出了序列 (00000) (00001) ... (11101)。根据您向左移动的距离，您将获得其中一个5位模式。然后进行表查找。非常好。 - Safayet Ahmed
5
uint16_t log2(uint32_t n) {//but truncated
if (n==0) throw ...
uint16_t logValue = -1;
while (n) {//
logValue++;
n >>= 1;
}
return logValue;
}
基本上与 tomlogic 的相同。
- Ustaman Sangat
1
1这个解决方案有一些问题，但总的来说，如果你想避免使用浮点数，这很好。你依赖于溢出来使它工作，因为你用-1初始化了一个无符号整数。这可以通过将其初始化为0，然后返回值-1来解决，假设你检查了0的情况，你确实已经检查了。另一个问题是你依赖于当n== 0时循环停止，你应该明确说明。除此之外，如果你想避免使用浮点数，这就很棒了。 - Rian Quinn
3
log2(x) = log10(x) / log10(2)
- the_void
1
点赞支持简洁明了，基于提供的信息编写代码。 - yoyo
2
您需要包含 math.h（C）或 cmath（C++）头文件。
当然，您需要遵循我们所知道的数学知识...只有数字>0。
例如：
#include <iostream>
#include <cmath>
using namespace std;
int main(){
cout<<log2(number);
}
- user2143904
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接