c - 获得小于某个数字的 2 的幂的最快方法是什么？

Question

我正在使用这个逻辑:

while ((chase<<(++n))< num) ;

其中 chase=1,n=0 最初和 num 是我想要找到 2 的幂的值只是比它少。

在循环之后我简单地应用

chase=1; 
chase<<(n-1);

虽然我得到了正确答案，但我只是想找到最快的方法。有没有更快的方法？

Answer 1

对于正整数 v v 的 2 小于或等于的幂是2^[log2(v)] (即 1 << [log2(v)] )，其中 []在[log2(v)]代表向下舍入。 (如果您需要 小于 v 的 2 的幂，您可以轻松调整算法。)

对于非零 v , [log2(v)]是v的二进制表示中最高1位的索引.

您必须已经了解以上所有内容，因为这正是您在原始代码中所做的。但是，它可以更有效地完成。 (当然，分析并查看新的“更高效”解决方案是否实际上对您的数据更高效始终是个好主意。)

用于查找最高 1 位索引的通用平台无关技巧基于 DeBruijn 序列。这是 32 位整数的实现

unsigned ulog2(uint32_t v)
{ /* Evaluates [log2 v] */
  static const unsigned MUL_DE_BRUIJN_BIT[] = 
  {
     0,  9,  1, 10, 13, 21,  2, 29, 11, 14, 16, 18, 22, 25,  3, 30,
     8, 12, 20, 28, 15, 17, 24,  7, 19, 27, 23,  6, 26,  5,  4, 31
  };

  v |= v >> 1;
  v |= v >> 2;
  v |= v >> 4;
  v |= v >> 8;
  v |= v >> 16;

  return MUL_DE_BRUIJN_BIT[(v * 0x07C4ACDDu) >> 27];
}

还有其他的位算法解决方案，可以在这里找到:https://graphics.stanford.edu/~seander/bithacks.html

但是，如果您需要最大效率，请注意许多现代硬件平台本身就支持此操作，并且编译器提供了用于访问相应硬件功能的内部函数。例如，在 MSVC 中它可能如下所示

unsigned ulog2(uint32_t v)
{ /* Evaluates [log2 v] */
  unsigned long i;
  _BitScanReverse(&i, v);
  return (unsigned) i;
}

在 GCC 中它可能如下所示

unsigned ulog2(uint32_t v)
{ /* Evaluates [log2 v] */
  return 31 - __builtin_clz(v);
}

如果你需要 64 位版本的函数，你可以用同样的方式重写它们。或者，由于对数的良好特性，您可以通过将 64 位值分成两个 32 位的一半并将 32 位函数应用于最高阶非零一半来轻松构建它们。