C++中没有内置的方法可以在编译时计算幂吗？

Question

我有以下非常简单的模板。据我所学，^不是指数运算符。现在我正在寻找一种计算这个幂的方法。互联网上有许多使用递归模板的示例。这并不太困难。

但我想知道：实际上在C++中没有“内置”的方法可以在编译时计算吗？

template <int DIM>
class BinIdx : Idx
{
        static const int SIZE = 3 ^ DIM; // whoops, this is NOT an exponential operator!
}

- Michael

---

如果它只是2的幂次方，请使用1 << DIM。否则，不行。 - Zeta

对于2的幂次方... 1 << DIM :p - melak47

这不一定是2的次方；-) - Michael

不，也没有内置的编译时 sqrt，或者内置的编译时 exp 或者内置的编译时 log ... 你真的认为需要吗？ - Jonathan Wakely

你可以使用constexpr函数来创建一些东西... - wilx

你总是可以使用一些脚本语言进行预处理和源代码生成。这在选项类等情况下有时会被采用。否则，答案就像 "<< " 一样简短，对于 C++ 编程来说，最好自己查找。 - Cheers and hth. - Alf

Answer 1

如前所述，如果指数是2的幂，则可以使用<<。

否则，如果指数为非负整数，则可以编写像这样的constexpr函数。

template<typename T, typename U>
auto constexpr pow(T base, U exponent) {
    static_assert(std::is_integral<U>(), "exponent must be integral");
    return exponent == 0 ? 1 : base * pow(base, exponent - 1);
}

显然，这种方法对于大指数以及负指数都会失效。

我不太清楚编译器在常量表达式中优化函数调用的情况。以下是一种手动优化方式，适用于指数为2的幂的情况。这也将减少递归的数量。

template<typename T>
bool constexpr is_power_of_two(T x) {
    return (x != 0) && ((x & (x - 1)) == 0);
}

template<typename T, typename U>
auto constexpr pow(T base, U exponent) {
    static_assert(std::is_integral<U>(), "exponent must be integral");
    if (is_power_of_two(exponent)) {
        return base << exponent;
    }
    return exponent == 0 ? 1 : base * pow(base, exponent - 1);
}

还有更高效的算法可供使用。但是，由于我不擅长计算机科学，所以不知道如何实现它们。

- user1804599

---

我认为你的函数名称应该更改 - 因为 std::pow >o< - ikh

你的最后一点很重要：如果不小心，编译时计算很容易使编译器崩溃。这是不在标准库中提供此类功能的一个很好的理由。 - Jonathan Wakely

@ikh：你为什么这么说？std 命名空间的整个目的就是允许你为自己的函数起一个合理的名称，而不会与库名称冲突。 - Mike Seymour

@MikeSeymour 然而，pow()是从C继承而来的。在许多情况下，我们可以看到人们包含<math.h>而不是<cmath>，这会导致事情出错。 - ikh

如果你想进行优化，更好的优化方法是使用“平方求幂”（Exponentiation by Squaring）：http://en.wikipedia.org/wiki/Exponentiation_by_squaring - Sebastian Redl

Answer 2

你可以使用模板元编程。让我展示一下代码。

template <int A, int B>
struct get_power
{
    static const int value = A * get_power<A, B - 1>::value;
};
template <int A>
struct get_power<A, 0>
{
    static const int value = 1;
};

使用方法：

std::cout << get_power<3, 3>::value << std::endl;

(live example)

- ikh

---

OP 明确要求一种内置的比模板元编程更直接的替代方案。因此，这不是一个答案。 - Cheers and hth. - Alf

@Cheersandhth.-Alf 哦，你说得对；我没有仔细阅读问题 >o< - ikh

Answer 3

作为对elyse的回答的补充，这里提供了一个递归深度为log(n)的版本：

template<typename T>
constexpr T sqr(T a) {
    return a * a;
}

template<typename T>
constexpr T power(T a, std::size_t n) {
    return n == 0 ? 1 : sqr(power(a, n / 2)) * (n % 2 == 0 ?  1 : a);
}

- Anton Savin

Answer 4

没有通用的内置方法来计算值的幂。标准库中有 pow 函数，对于特殊情况 2^x 可以使用 << 移位运算符。

这种情况下 (*) 可以工作：

static const int SIZE = (1 << DIM);

* = 在我回答完你的问题后，你将问题从2^x更新为3^x。

对于另一种特殊情况x^y，其中x和y是静态的，您可以编写一个长乘法：

const result int = x*x*x*x*x;

- Flovdis

Answer 5

一个命名运算符库：

namespace named_operator {
  template<class D>struct make_operator{
    constexpr make_operator(){}
  };
  template<class T, char, class O> struct half_apply { T&& lhs; };

  template<class Lhs, class Op>
  constexpr
  half_apply<Lhs, '*', Op>
  operator*( Lhs&& lhs, make_operator<Op> ) {
    return {std::forward<Lhs>(lhs)};
  }

  template<class Lhs, class Op, class Rhs>
  constexpr auto
  times( Lhs&& lhs, Op, Rhs&& rhs, ... ) // ... keeps this the worst option
  -> decltype( invoke( std::declval<Lhs>(), Op{}, std::declval<Rhs>() ) )
  {
    // pure ADL call, usually based off the type Op:
    return invoke( std::forward<Lhs>(lhs), Op{}, std::forward<Rhs>(rhs)     );
  }

  template<class Lhs, class Op, class Rhs>
  constexpr auto
  operator*( half_apply<Lhs, '*', Op>&& lhs, Rhs&& rhs )
  -> decltype(
    times( std::declval<Lhs>(), Op{}, std::declval<Rhs>() )
  )
  {
    return times( std::forward<Lhs>(lhs.lhs), Op{}, std::forward<Rhs>(rhs) );
  }
}

它只支持 operator*，但扩展它应该很明显。选择 times 等效名称有点棘手。

@Anton 的解决方案，增加了一个命名的运算符：

namespace power {
  template<typename T>
  constexpr T sqr(T a) {
    return a * a;
  }

  template<typename T>
  constexpr T power(T a, std::size_t n) {
    return n == 0 ? 1 : sqr(power(a, n / 2)) * (n % 2 == 0 ?  1 : a);
  }

  namespace details {
    struct pow_tag {};
    constexpr named_operator::make_operator<pow_tag> pow;

    template<class Scalar>
    constexpr Scalar times( Scalar lhs, pow_tag, std::size_t rhs ) {
      return power( std::forward<Scalar>(lhs), rhs );
    }
  }
  using details::pow;
}

现在这个功能可以正常使用：

using power::pow;
int array[ 2 *pow* 10 ] = {0};

live example.

- Yakk - Adam Nevraumont