获得小于某个数字的 2 的幂的最快方法是什么? [英] What is the fastest way to get the power of 2 less than a certain number?

问题描述

我正在使用这个逻辑:

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

where chase=1,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.

在循环之后我简单地应用

After the loop I simply apply

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 2 less or equal to v 的幂> 是 2^[log2(v)](即 1 <<[log2(v)])，其中 [] 在[log2(v)] 代表四舍五入向下.(如果您需要 < 小于 v 的 2 的幂，您可以轻松调整算法.)

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屋！