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

极其低效的标准库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;
}

迄今为止最有效的对预先计算的 2 幂表进行 bin 搜索:

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.

最佳答案

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

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;
}

当目标硬件直接支持时，应该会更好。

Results on coliru , 和 latency results on coliru (也与基线进行比较，这应该大致表明开销)。在延迟结果中，highestPowerOfTwoIn 的第一个版本看起来不再那么好(仍然可以，但它是一长串依赖指令，因此它扩大与内在版本)。其中哪一项是最相关的比较取决于您的实际使用情况。

如果你有一些奇怪的硬件具有快速位反转操作(但可能是慢速移位或慢clz)，我们称之为_rbit，那么你可以这样做

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

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

关于c++ - 如何有效地计算小于或等于给定数字的 2 的最高幂？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/42595326/