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

Question

假设我有 n=32。我想知道 log_2(n) 是什么。 在本例中，log_2(32) = 5。

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

IE 给定 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]
} 

该解决方案依赖于这样一个事实：2 的前 32 次幂除以 37 时每个都有不同的余数。

如果您需要它对长数进行处理，然后使用 67 作为模数；我让您计算出数组的正确值。

评论者 LukeH 正确地指出，有一个函数据称采用负数的对数（1<<31 是一个负符号整数。）该方法可以修改为采用uint，或者如果给定的数字不满足方法的要求，则可以引发异常或断言。没有给出哪一个是正确的做法；对于此处正在处理的确切数据类型，问题有些模糊。

挑战：

假设：除以 p 时，2 的前 n 次幂具有不同的模数，其中 p 是大于 n 的最小质数。

如果假设成立，则证明它。如果假设是错误的，则提供一个反例来证明其错误。

Answer 2

我认为，如果你保证 n 是 2 的幂，那么找到 b 的快速方法是将 n 转换为二进制字符串并查找 1 的索引。特别考虑 n = 0

using System.Linq;
...
var binaryStringReversed = Convert.ToString(value, 2).Reverse();
var b = binaryStringReversed.IndexOf("1");

编辑的情况：

var b = Convert.ToString(value, 2).Length - 1;