如果我有一个整数n,并且我想知道最高位的位置(也就是说,如果最低有效位在右边,我想知道最左边位的位置是1),找出最快捷/最有效的方法是什么？
我知道POSIX支持ffs()strings.h中的一个方法来查找第一个设置位,但似乎没有相应的fls()方法.
是否有一些非常明显的方法可以解决这个问题？
如果你不能使用POSIX功能来实现可移植性呢？
编辑:如何在32位和64位架构上运行的解决方案(许多代码清单似乎只能在32位整数上运行).
问题是
是否还有其他(和/或更快)的基本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 …如何最有效地计算C#中整数(日志基数2)所需的位数？例如:
int bits = 1 + log2(100);
=> bits == 7
StackOverflow上有很多关于此的问题.很多.但是我找不到答案:
比...快:
private static int Obvious(ulong v)
{
int r = 0;
while ((v >>= 1) != 0)
{
r++;
}
return r;
}
甚至
int r = (int)(Math.Log(v,2));
我在这里假设一个64位Intel CPU.
一个有用的参考是Bit Hacks页面,另一个是fxtbook.pdf. 然而,虽然这些提供了解决问题的有用方向,但它们没有给出准备好的答案.
我正在使用一个可重用的函数,它只能为C#执行与_BitScanForward64和_BitScanReverse64类似的操作.