如何确定二次幂值所需的右位移位次数

本文关键字：何确定 二次幂 | 更新日期: 2023-09-27 18:27:04

我有一个函数，它接收值的二次幂。

我需要将其转换为枚举范围（0、1、2、3等），然后将其移回2的幂范围。

 0         1
 1         2
 2         4
 3         8
 4        16
 5        32
 6        64
 7       128
 8       256
 9       512
10      1024
... and so on.

如果我的函数接收到1024的值，我需要将其转换为10。在C#中，最好的方法是什么？我应该在一个循环中一直除以2并计算迭代次数吗？

我知道我可以用（1<<10）把它放回去。

如何确定二次幂值所需的右位移位次数

只需使用以2为底的对数：

Math.Log(/* your number */, 2)

例如，Math.Log(1024, 2)返回10。

更新：

这里有一个相当强大的版本，可以检查传入的数字是否是2的幂：

public static int Log2(uint number)
{
  var isPowerOfTwo = number > 0 && (number & (number - 1)) == 0;
  if (!isPowerOfTwo)
  {
    throw new ArgumentException("Not a power of two", "number");
  }
  return (int)Math.Log(number, 2);
}

number为2的幂的检查来自http://graphics.stanford.edu/~seander/bithacks.html#DetermineInfoPowerOf2

从这里开始，还有更多的技巧可以在该页面上找到整数的log2：http://graphics.stanford.edu/~seander/bithacks.html#IntegerLogObvious

当您的CPU没有位扫描指令或无法访问该指令时，这可能是最快的算法：

unsigned int v;  // find the number of trailing zeros in 32-bit v 
int r;           // result goes here
static const int MultiplyDeBruijnBitPosition[32] = 
{
  0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
  31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9
};
r = MultiplyDeBruijnBitPosition[((uint32_t)((v & -v) * 0x077CB531U)) >> 27];

如果你想知道它是如何工作的，请看这篇论文，基本上，它只是一个完美的散列。

使用_BitScanForward。它正是这样做的。

相关文章：