计算log_2(n)的最快方法,其中n是2 ^ k的形式？

Question

说我得到n = 32.我想知道log_2(n)是什么.在这种情况下,log_2(32)= 5.

一般来说,计算2 ^ k数的对数的最快方法是什么？

即给定n = 2 ^ k.log_2(n)= b.找到b.

允许按位操作.

Answer 1

这个页面在C中提供了六种不同的方法; 将它们改为C#应该是微不足道的.试一试,看看哪个最快.

http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

但是,我注意到这些技术旨在适用于所有 32位整数.如果你可以保证输入总是 1到2 ^ 31之间的2的幂,那么你可以用查找表做得更好.我提交以下内容; 我没有对它进行性能测试,但我认为它没有理由不应该很快:

static int[] powers = new[] {0, 0, 1, 26, 2, 23, 27, 0, 3, 16, 24, 
                        30, 28, 11, 0, 13, 4, 7, 17, 0, 25, 22, 
                        31, 15, 29, 10, 12, 6, 0, 21, 14, 9, 5, 
                        20, 8, 19, 18};

static int Log2OfAPower(int x)
{
    return powers[((uint)x) % 37]
} 

该解决方案依赖于以下事实:当除以37时,两个中的前32个幂具有不同的余数.

如果你需要它来长时间工作,那么使用67作为模数; 我让你找出数组的正确值.

评论者LukeH正确地指出,有一个功能据称采用负数的对数(1<<31是一个负的有符号整数)是奇怪的.该方法可以被修改为取一个uint,或者可以使它抛出异常或断言如果给出的数字不符合方法的要求.没有给出哪个是正确的做法; 关于这里正在处理的确切数据类型,这个问题有些模糊.

挑战:

假设:当除以p时,每个2的前n个幂具有不同的模数,其中p是大于n的最小素数.

如果假设是真的那么证明它.如果假设是假的,那么提供一个证明其虚假的反例.