如何有效地计算小于或等于给定数字的2的最大幂？[副本]

Question

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

效率极低的标准库< code > power 和< code>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;
}

迄今为止最有效的二次幂预计算表：

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

爬升速度更快，但回落速度相同。

        uint multiply_quick(uint n)
        {
            if (n < 2u) return 1u;
            uint maxpow = 1u;

            if (n > 256u)
            {
                maxpow = 256u * 128u;

                // fast fixing the overshoot
                while (maxpow > n)
                    maxpow = maxpow >> 2;
                // fixing the undershoot
                while (2u * maxpow <= n)
                    maxpow *= 2u;
            }
            else
            {

                // quicker scan
                while (maxpow < n && maxpow != 256u)
                    maxpow *= maxpow;

                // fast fixing the overshoot
                while (maxpow > n)
                    maxpow = maxpow >> 2;

                // fixing the undershoot
                while (2u * maxpow <= n)
                    maxpow *= 2u;
            }
            return maxpow;
        }

也许这更适合使用65k常量而不是256的32位变量。

Answer 2

查找表似乎是这里的最佳选择。因此，回答

这还能再优化吗？有什么技巧可以用在这里吗？

是的，我们可以！让我们打败标准库二进制搜索！

template <class T>
inline size_t
choose(T const& a, T const& b, size_t const& src1, size_t const& src2)
{
    return b >= a ? src2 : src1;
}
template <class Container>
inline typename Container::const_iterator
fast_upper_bound(Container const& cont, typename Container::value_type const& value)
{
    auto size = cont.size();
    size_t low = 0;

    while (size > 0) {
        size_t half = size / 2;
        size_t other_half = size - half;
        size_t probe = low + half;
        size_t other_low = low + other_half;
        auto v = cont[probe];
        size = half;
        low = choose(v, value, low, other_low);
    }

    return begin(cont)+low;
}

使用upper_bound的这个实现给了我一个实质性的改进：

g++ -std=c++14 -O2 -Wall -Wno-unused-but-set-variable -Werror main.cpp && ./a.out
Pow and log took 2536 milliseconds.
Multiplying by 2 took 320 milliseconds.
Binsearching precomputed table of powers took 349 milliseconds.
Binsearching (opti) precomputed table of powers took 167 milliseconds.

（生活在大肠杆菌上）请注意，我已经改进了您的基准测试以使用随机值;通过这样做，我删除了分支预测偏差。

现在，如果您真的需要更加努力，可以使用x86_64 asm优化choose函数以实现clang：

template <class T> inline size_t choose(T const& a, T const& b, size_t const& src1, size_t const& src2)
{
#if defined(__clang__) && defined(__x86_64)
    size_t res = src1;
    asm("cmpq %1, %2; cmovaeq %4, %0"
        :
    "=q" (res)
        :
        "q" (a),
        "q" (b),
        "q" (src1),
        "q" (src2),
        "0" (res)
        :
        "cc");
    return res;
#else
    return b >= a ? src2 : src1;
#endif
}

带输出：

clang++ -std=c++14 -O2 -Wall -Wno-unused-variable -Wno-missing-braces -Werror main.cpp && ./a.out
Pow and log took 1408 milliseconds.
Multiplying by 2 took 351 milliseconds.
Binsearching precomputed table of powers took 359 milliseconds.
Binsearching (opti) precomputed table of powers took 153 milliseconds.

(在科利鲁直播)

Answer 3

带有内部函数的版本已经在评论中提出，所以这里有一个不依赖它们的版本：

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

因为没有人真正张贴它，你可以用内部函数来写(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上的延迟结果(也与基线进行比较，基线应该大致指示开销)。在延迟结果中，< code>highestPowerOfTwoIn的第一个版本看起来不再那么好了(仍然可以，但它是一个很长的依赖指令链，所以它扩大了与内函数版本的差距也就不足为奇了)。哪一个是最相关的比较取决于你的实际使用情况。

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

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

这当然是基于旧的x