求出小于某个数的 2 次方最快的方法是什么？

我正在使用这个逻辑：

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

where chase=1,n=0最初和num是我想要找到略小于它的 2 次幂的值。

循环之后我只需应用

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

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

对于正整数v2的幂小于或等于 to v is 2^[log2(v)] (i.e. 1 << [log2(v)]）， 在哪里[] in [log2(v)]代表四舍五入down。 （如果您需要 2 的幂，即less than v，您可以轻松调整算法。）

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

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

用于查找最高 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 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 位函数应用于最高阶非零一半来轻松构建它们。