如何有效地计算小于或等于给定数字的2的最高功率？

Question

到目前为止我想出了三个解决方案:

极低效的标准库pow和log2功能:

int_fast16_t powlog(uint_fast16_t n)
{
  return static_cast<uint_fast16_t>(pow(2, floor(log2(n))));
}

计算后续2次幂的效率要高得多,直到我达到的数量超过我必须达到的数量:

uint_fast16_t multiply(uint_fast16_t n)
{
  uint_fast16_t maxpow = 1;
  while(2*maxpow <= n)
    maxpow *= 2;
  return maxpow;
}

到目前为止最有效的binsearching预先计算的2的权力表:

uint_fast16_t binsearch(uint_fast16_t n)
{
  static array<uint_fast16_t, 20> pows {1,2,4,8,16,32,64,128,256,512,
    1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};

  return *(upper_bound(pows.begin(), pows.end(), n)-1);
}

这可以进一步优化吗？可以在这里使用的任何技巧？

我使用的完整基准:

#include <iostream>
#include <chrono>
#include <cmath>
#include <cstdint>
#include <array>
#include <algorithm>
using namespace std;
using namespace chrono;

uint_fast16_t powlog(uint_fast16_t n)
{
  return static_cast<uint_fast16_t>(pow(2, floor(log2(n))));
}

uint_fast16_t multiply(uint_fast16_t n)
{
  uint_fast16_t maxpow = 1;
  while(2*maxpow <= n)
    maxpow *= 2;
  return maxpow;
}

uint_fast16_t binsearch(uint_fast16_t n)
{
  static array<uint_fast16_t, 20> pows {1,2,4,8,16,32,64,128,256,512,
    1024,2048,4096,8192,16384,32768,65536,131072,262144,524288};

  return *(upper_bound(pows.begin(), pows.end(), n)-1);
}

high_resolution_clock::duration test(uint_fast16_t(powfunct)(uint_fast16_t))
{
  auto tbegin = high_resolution_clock::now();
  volatile uint_fast16_t sink;
  for(uint_fast8_t i = 0; i < UINT8_MAX; ++i)
    for(uint_fast16_t n = 1; n <= 999999; ++n)
      sink = powfunct(n);
  auto tend = high_resolution_clock::now();
  return tend - tbegin;
}

int main()
{
  cout << "Pow and log took " << duration_cast<milliseconds>(test(powlog)).count() << " milliseconds." << endl;
  cout << "Multiplying by 2 took " << duration_cast<milliseconds>(test(multiply)).count() << " milliseconds." << endl;
  cout << "Binsearching precomputed table of powers took " << duration_cast<milliseconds>(test(binsearch)).count() << " milliseconds." << endl;
}

用-O2这个编译在我的笔记本电脑上给出了以下结果:

Pow and log took 19294 milliseconds.
Multiplying by 2 took 2756 milliseconds.
Binsearching precomputed table of powers took 2278 milliseconds.

Answer 1

已经在评论中建议了带有内在函数的版本,所以这里的版本不依赖于它们:

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  x |= x >> 1;
  x |= x >> 2;
  x |= x >> 4;
  x |= x >> 8;
  x |= x >> 16;
  return x ^ (x >> 1);
}

这首先将最高设置位"涂抹"到右边,然后x ^ (x >> 1)只保留与它们直接左边的位不同的位(msb被认为是左边的0),这只是最高的设置位是因为涂抹了数字是0 ⁿ 1 ^m的形式(用字符串表示法,而不是数字取幂).

由于没有人真正发布它,你可以用内在函数写(GCC,Clang)

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  return 0x80000000 >> __builtin_clz(x);
}

或者(MSVC,可能,未经测试)

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  unsigned long index;
  // ignoring return value, assume x != 0
  _BitScanReverse(&index, x);
  return 1u << index;
}

当目标硬件直接支持时,应该更好.

结果在coliru,并延迟结果对coliru(与基线相比也是如此,这应该是大致表示开销).在延迟结果中,第一个版本highestPowerOfTwoIn看起来不再那么好了(仍然可以,但它是一长串依赖指令,所以它扩大与内在函数版本的差距并不是一个大惊喜).其中哪一项最相关的比较取决于您的实际使用情况.

如果你有一些奇怪的硬件具有快速位反转操作(但可能是慢速移位或慢速clz),让我们调用它_rbit,然后你可以做

uint32_t highestPowerOfTwoIn(uint32_t x)
{
  x = _rbit(x);
  return _rbit(x & -x);
}

这当然是基于旧的x & -x隔离最低设置位,由位反转包围它隔离最高设置位.