下面是一个使用二分搜索的 constexpr 平方根实现。它使用 gcc 和 clang 可以正常工作到 2^64,其他更简单的版本通常会因数字 > 2^32 而失败,因为编译器将递归深度限制为例如 200。
// C++11 compile time square root using binary search
#define MID ((lo + hi + 1) / 2)
constexpr uint64_t sqrt_helper(uint64_t x, uint64_t lo, uint64_t hi)
{
return lo == hi ? lo : ((x / MID < MID)
? sqrt_helper(x, lo, MID - 1) : sqrt_helper(x, MID, hi));
}
constexpr uint64_t ct_sqrt(uint64_t x)
{
return sqrt_helper(x, 0, x / 2 + 1);
}
下面是一个更好的版本(用于整数常量),它需要 C++14,它类似于 Baptiste Wicht 的博客文章中介绍的版本。C++14 constexpr 函数允许使用局部变量和 if 语句。
// C++14 compile time square root using binary search
template <typename T>
constexpr T sqrt_helper(T x, T lo, T hi)
{
if (lo == hi)
return lo;
const T mid = (lo + hi + 1) / 2;
if (x / mid < mid)
return sqrt_helper<T>(x, lo, mid - 1);
else
return sqrt_helper(x, mid, hi);
}
template <typename T>
constexpr T ct_sqrt(T x)
{
return sqrt_helper<T>(x, 0, x / 2 + 1);
}