c++ - 在编译时计算小整数的阶乘

Question

我刚刚（再次）实现了一个递归模板，用于在编译时计算整数的阶乘（谁会想到有一天我会真正需要它！）。尽管如此，我并没有自己动手，而是去Boost寻找答案。但是，特殊数学中的阶乘函数特别禁止它与整数类型一起使用，所以我只写了自己的。

不过，我应该使用 Boost 中的另一个功能吗？我应该将整数转换为double并使用该boost::factorial函数吗？计算是在编译时执行的吗？

Answer 1

你不需要 Boost，如果你有 C++11，这只是 1-liner：

constexpr uint64_t factorial(uint64_t n) { 
    return n == 0 ? 1  :  n * factorial(n-1); 
}

即使您的 arg 也不是编译时间常数，它也会起作用。uint64_t 适用于 n < 21。

如果您在编译时执行此操作并乘以浮点值 - 将没有转换开销（转换也将在编译时进行）。

Answer 2

由于可以容纳在整数中的阶乘数量有限，因此您可以简单地手动预先计算前 20 个值并将它们存储在全局或静态数组中。然后使用全局或静态函数在数组中查找阶乘：

#include <iostream>

const int factorials[] =
{
    1,
    1,
    2,
    6,
    24,
    // etc...
};

inline const int factorial(int n) {return factorials[n];}

int main()
{
    static const int fourFactorial = factorial(4);
    std::cout << "4! = " << fourFactorial << "\n";
}

如果您使用文字作为 的参数factorial，则编译器应该简单地用结果替换函数调用（启用优化时）。我在 XCode 4.4（在 Mac 上）中尝试了上面的示例，我在程序集中看到它fourFactorial使用常量 24 进行初始化：

.loc    1 20 38  ## /Users/emile/Dev/sandbox/sandbox/main.cpp:20:38
movl    $24, __ZZ4mainE13fourFactorial(%rip)

与使用递归编译时技巧相比，此方法可能会导致更快的编译。