最快的log2（int）和log2（float）实现
问题是
是否还有其他（和/或更快）的基本2log实现？
应用
log2（int）和log2（float）操作在许多不同的上下文中非常有用。 仅举几例：压缩算法，3d引擎和机器学习。 在几乎所有这些上下文中，它们都被用在被称为数十亿次的低级代码中……尤其是log2（int）操作非常有用。
因为我发现自己一直在使用log2，所以我不想给出我正在处理的特定应用程序。 同样的事实是，这是一个真正的性能排水器（如各种应用程序的性能测试所示）。 对我来说，尽可能快地获得这个是关键。
底部添加了测试所有实现的完整源代码，因此您可以自己查看。
当然……运行你的测试至少3次，并确保计数器足够大，可以达到几秒钟。 我也做’添加’操作，以确保整个循环不被JIT’ter神奇地移除。 让我们开始真正的工作吧。
琐碎的实施
C＃中2log的简单实现是：
(int)(Math.Log(x) / Math.Log(2)) 这种实现很简单，但也很慢。 它需要2个Log操作，这本身就很慢。 当然，我们可以通过使1.0/Math.Log(2)成为常数来优化它。
请注意，我们需要稍微修改此常量以获得正确的结果（作为浮点错误的结果）或添加一个小数字以获得正确的结果。 我选择了后者，但这并不重要 – 最终结果在所有情况下都很慢。
表查找
更快的解决方案是使用查找表。 虽然您可以使用任何2的幂的查找表，但我通常使用256或64K条目的表大小。
首先我们创建查找表：
lookup = new int[256]; for (int i = 1; i < 256; ++i) { lookup[i] = (int)(Math.Log(i) / Math.Log(2)); }
接下来，我们实现2log如下：
private static int LogLookup(int i) { if (i >= 0x1000000) { return lookup[i >> 24] + 24; } else if (i >= 0x10000) { return lookup[i >> 16] + 16; } else if (i >= 0x100) { return lookup[i >> 8] + 8; } else { return lookup[i]; } }
正如您所看到的，表查找是一个更快，更快的实现 – 但作为一个骗局，它不能用于计算log2(float) 。
分支删除
众所周知，处理器不是很擅长分支，所以我认为可以通过删除分支来改进表查找。 而不是if的串，我引入了第二个表，其中包含值和移位位以查找表中的条目：
nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 }; private static int LogDoubleLookup(int i) { int n = (i | (i >> 4)); n = (n | (n >> 2)); n = (n | (n >> 1)); n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1); int br = nobranch[n]; return lookup[i >> br] + br; }
如果运行此测试，您会发现它实际上比if-then-else解决方案慢。
然后是英特尔80386
英特尔多年前就明白这是一项重要的操作，因此他们在其处理器中实现了位扫描转发（BSF）。 其他处理器有类似的指令。 这是迄今为止我知道的2log最快的方法 – 但不幸的是我现在知道如何使用C＃中的这些不错的函数…我不喜欢有一个不再运行的实现的想法当新的平板电脑或手机进入市场时 – 我不知道任何跨平台解决方案使我能够直接使用此function。
其他实现
正如l4V指出的那样（谢谢！）还有其他一些实现，特别是：
- 琐碎的循环。 我省略了这个，因为它不是很简单。 在
TestTrivial实现。 - 可以使用的64位IEEE / int联合。 在
TestFloat实现 - DeBruijn查找表。 在
TestDeBruijn实现 - 二进制搜索。 在
TestBinary实现
除了我喜欢这个名字，DeBruijn查找表和普通的查找表一样快，这使得它成为这里最快的算法之一……我尝试过的所有其他算法都慢得多。
完整的测试代码
public class Log2Test { public static void TestNaive() { Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i >= 1) > 0) // unroll for more speed... { r++; } return r; } public static void TestTrivialLoop() { Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i > 20) - 0x3FF; } public static void TestFloat() { Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i < 100000000; ++i) { n += LogFloat(i); } sw.Stop(); Console.WriteLine("Result: {0} - IEEE float implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds); } [StructLayout(LayoutKind.Explicit)] private struct Helper { [FieldOffset(0)] public int U1; [FieldOffset(4)] public int U2; [FieldOffset(0)] public double D; } public static void TestConstant() { double c = 1.0 / Math.Log(2.0); Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i = 0x1000000) { return lookup[i >> 24] + 24; } else if (i >= 0x10000) { return lookup[i >> 16] + 16; } else if (i >= 0x100) { return lookup[i >> 8] + 8; } else { return lookup[i]; } } public static void TestLookup() { lookup = new int[256]; for (int i = 1; i < 256; ++i) { lookup[i] = (int)(Math.Log(i) / Math.Log(2)); } Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i > 4)); n = (n | (n >> 2)); n = (n | (n >> 1)); n = ((n & 0x1000000) >> 21) | ((n & 0x10000) >> 14) | ((n & 0x100) >> 7) | (n & 1); int br = nobranch[n]; return lookup[i >> br] + br; } public static void TestDoubleLookup() { // Lookup table was already constructed earlier Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i = 0; i--) // unroll for speed... { if ((v & b[i]) != 0) { v >>= S[i]; r |= S[i]; } } return r; */ int r = (((v > 0xFFFF)) ? 0x10 : 0); v >>= r; int shift = ((v > 0xFF) ? 0x8 : 0); v >>= shift; r |= shift; shift = ((v > 0xF) ? 0x4 : 0); v >>= shift; r |= shift; shift = ((v > 0x3) ? 0x2 : 0); v >>= shift; r |= shift; r |= (v >> 1); return r; } public static void TestBinary() { // Lookup table was already constructed earlier Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i > 1; // first round down to one less than a power of 2 v |= v >> 2; v |= v >> 4; v |= v >> 8; v |= v >> 16; return MultiplyDeBruijnBitPosition[(uint)(v * 0x07C4ACDDU) >> 27]; } public static void TestDeBruijn() { // Lookup table was already constructed earlier Stopwatch sw = new Stopwatch(); sw.Start(); int n = 0; for (int i = 1; i < 100000000; ++i) { n += LogDeBruijn(i); } sw.Stop(); Console.WriteLine("Result: {0} - de Bruijn implementation took {1:0.000}s", n, sw.Elapsed.TotalSeconds); } private static int[] lookup; private static readonly int[] nobranch = new int[16] { 0, 0, 8, 8, 16, 16, 16, 16, 24, 24, 24, 24, 24, 24, 24, 24 }; static void Main(string[] args) { TestConstant(); TestNaive(); TestDeBruijn(); TestBinary(); TestFloat(); TestTrivialLoop(); TestLookup(); TestDoubleLookup(); Console.ReadLine(); } }
这里有一些整数算法 。
在C＃中：
public static uint FloorLog2(uint x) { x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return (uint)(NumBitsSet(x) - 1); } public static uint CeilingLog2(uint x) { int y = (int)(x & (x - 1)); y |= -y; y >>= (WORDBITS - 1); x |= (x >> 1); x |= (x >> 2); x |= (x >> 4); x |= (x >> 8); x |= (x >> 16); return (uint)(NumBitsSet(x) - 1 - y); } public static int NumBitsSet(uint x) { x -= ((x >> 1) & 0x55555555); x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); x = (((x >> 4) + x) & 0x0f0f0f0f); x += (x >> 8); x += (x >> 16); return (int)(x & 0x0000003f); } private const int WORDBITS = 32;
您应该查看我为上下文链接的站点上的原始代码，尤其是Log2（0）所发生的情况。
采用已经提到的二进制解决方案并删除了分支。 做了一些测试，结果比DeBruijn快1.3倍。
public static int Log2(int v) { int r = 0xFFFF - v >> 31 & 0x10; v >>= r; int shift = 0xFF - v >> 31 & 0x8; v >>= shift; r |= shift; shift = 0xF - v >> 31 & 0x4; v >>= shift; r |= shift; shift = 0x3 - v >> 31 & 0x2; v >>= shift; r |= shift; r |= (v >> 1); return r; }
有关更多算法，请参阅http://www.asmcommunity.net/forums/topic/?id=15010
还在C ++中进行了一些测试，我的BSR实现比查找表慢
- 我正在使用BDS2006，可能会因asm指令的状态推送/弹出而减慢速度
- 你的查找很好，但我使用11位表而不是8位
- 它将32位分为3个分支而不是4个
- 并且它仍然足够小，无需init函数即可处理
码：
//--------------------------------------------------------------------------- DWORD log2_slow(const DWORD &x) { DWORD m,i; if (!x) return 0; if (x>=0x80000000) return 31; for (m=1,i=0;m=0x00400000) return _log2[x>>22]+22; else if (x>=0x00000800) return _log2[x>>11]+11; else return _log2[x]; } //---------------------------------------------------------------------------
测试代码：
DWORD x,j,i,n=256; tbeg(); for (i=0;i<32;i++) for (j=0;jLines->Add(tstr(1)); tbeg(); for (i=0;i<32;i++) for (j=0;jLines->Add(tstr(1)); tbeg(); for (i=0;i<32;i++) for (j=0;jLines->Add(tstr(1));
我对AMD A8-5500 3.2 GHz的结果：
[ 0.040 ms] log2 (x) - 11bit lookup table [ 0.060 ms] log2_asm (x) - BSR [ 0.415 ms] log2_slow(x) - shift loop
注意：
- log2（0） – > 0因为使用了DWORDS，实际应该是-inf
- 所有其他值对于所有函数都是正确的
inline int fast_log2(register double x) { return (reinterpret_cast(x) >> 52) - 1023; };
这是我用过的：
unsigned log2(register unsigned n) { register unsigned i; for (i=0; (n & 1); n>>=1, i++); return i; }
编辑：检查这些（ffz变体）： https ：//patchwork.kernel.org/patch/8845631/