使2的幂小于特定数的最快方法是什么？ [英] What is the fastest way to get the power of 2 less than a certain number?

问题描述

我使用的是这种逻辑：

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

其中 chase = 1 ，<$ c最初$ c> n = 0 和 num 是我想找到2的幂的值，该值小于它。

where chase=1,n=0 initially and num is the value for which I want to find the power of 2 that is just less than it.

循环后，我简单地应用

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

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

Although I get the correct answer, I am just trying to find the fastest way to do it. Are there any faster methods?

推荐答案

对于正整数 v ，幂 v 的2个更少或等于的值是 2 ^ [log2（v）] （即 1<< [log2（v）] ），其中中的 [] [log2（v）] 表示向下舍入 。 （如果您需要2的幂，尤其是小于 v 的，则可以轻松调整算法。）

For positive integer v the power of 2 less or equal to v is 2^[log2(v)] (i.e. 1 << [log2(v)]), where [] in [log2(v)] stands for rounding down. (If you need a power of 2 that is specifically less than v, you can easily adjust the algorithm.)

对于非零的 v ， [log2（v）] 是最高的索引 v 的二进制表示形式的1位。

For nonzero v, [log2(v)] is the index of the highest 1 bit in the binary representation of v.

您必须已经知道以上所有内容，因为这正是您在原始代码中所做的。但是，它可以更有效地完成。 （当然，配置文件并查看新的更有效的解决方案实际上是否对您的数据更有效总是一个好主意。）

You must already know all the above, since that is exactly what you do in your original code. However, it can be done more efficiently. (Of course, it is always a good idea to profile and see whether the new "more efficient" solution is actually more efficient on your data.)

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

The generic platform-independent trick for finding the index of the highest 1 bit is based on DeBruijn sequences. Here's an implementation for 32 bit integers

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

There are other bit-algorithmic solutions, which can be found here: https://graphics.stanford.edu/~seander/bithacks.html

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

However, if you need maximum efficiency, take note that many modern hardware platforms support this operation natively, and compilers provide intrinsics for accessing the corresponding hardware features. For example, in MSVC it might look as follows

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

在GCC中，可能看起来如下

while in GCC it might look as follows

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

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

If you need 64-bit version of the functions, you can rewrite them in the same fashion. Or, due to nice properties of logarithm, you can easily build them by splitting the 64-bit value into two 32-bit halves and applying the 32-bit function to the highest-order non-zero half.

这篇关于使2的幂小于特定数的最快方法是什么？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！