编译期随机数生成：线性同余生成器与梅森旋转算法的编译期版本
随机数生成，听起来像是运行时的事，对吧？
但有时候，我们偏偏需要在编译期就拿到一串“随机”数。比如模板元编程中的测试数据生成、编译期哈希种子、或者某些静态配置的混淆处理。我最初接触这个需求，是在做一个编译期单元测试框架的时候——需要在编译期生成一批测试数据，但又不想手动写死几百个常量。
嗯，今天我们就来聊聊，怎么在编译期把随机数“算”出来。
编译期随机数的核心矛盾
随机数的本质是“不可预测”。但编译期计算是纯函数式的——同样的输入，永远得到同样的输出。这听起来像是死胡同。
其实不然。我们需要的不是真正的随机，而是伪随机。只要种子不同，序列就不同。而种子，我们可以从编译期常量、时间戳（比如__DATE__、__TIME__）或者模板参数中获取。
关键点：编译期随机数 = 确定性算法 + 编译期种子。
线性同余生成器（LCG）的编译期实现
线性同余生成器是最简单的伪随机数算法。公式就一行：
X_{n+1} = (a * X_n + c) mod m其中 a、c、m 是精心挑选的常数。我习惯用 glibc 中 rand() 的那组参数：a=1103515245, c=12345, m=2^31。
用 constexpr 函数实现，简直不要太轻松：
constexpr std::uint32_t lcg_next(std::uint32_t current) {
constexpr std::uint32_t a = 1103515245;
constexpr std::uint32_t c = 12345;
constexpr std::uint32_t m = 1u << 31;
return (a * current + c) % m;
}
constexpr std::uint32_t lcg_seed = 42; // 可以换成 __TIME__ 的哈希
constexpr std::uint32_t r1 = lcg_next(lcg_seed);
constexpr std::uint32_t r2 = lcg_next(r1);
// 以此类推...你看，就这么简单。但 LCG 有个问题——周期短，统计特性差。我在项目中用它生成过几万个测试数据，结果发现明显的周期性模式。嗯，后来就换成了梅森旋转。
梅森旋转算法（Mersenne Twister）的编译期版本
梅森旋转算法（MT19937）是 C++ 标准库 std::mt19937 的底层算法。它的周期长达 2^19937-1，统计特性远优于 LCG。
但它的状态有 624 个 32 位整数。要在编译期维护这么大一个状态数组，怎么办？
答案是：用 std::array 加 constexpr 函数。
我当年第一次尝试写编译期 MT19937 时，踩了个大坑——constexpr 函数里不能修改全局变量。所以状态必须通过返回值传递。说白了，就是每次生成一个随机数，都要返回新的状态数组。
来看核心实现：
template <std::size_t N>
struct mt_state {
std::array<std::uint32_t, N> data;
std::size_t index;
};
constexpr std::uint32_t twist(std::uint32_t u, std::uint32_t v) {
return (u & 0x80000000u) | (v & 0x7fffffffu);
}
constexpr mt_state<624> twist_all(mt_state<624> state) {
for (std::size_t i = 0; i < 624; ++i) {
std::uint32_t x = twist(state.data[i], state.data[(i + 1) % 624]);
state.data[i] = state.data[(i + 397) % 624] ^ (x >> 1);
if (x & 1u) {
state.data[i] ^= 0x9908b0dfu;
}
}
state.index = 0;
return state;
}
constexpr auto temper(std::uint32_t y) {
y ^= (y >> 11);
y ^= (y << 7) & 0x9d2c5680u;
y ^= (y << 15) & 0xefc60000u;
y ^= (y >> 18);
return y;
}
constexpr auto mt_next(mt_state<624> state) {
if (state.index >= 624) {
state = twist_all(state);
}
auto result = temper(state.data[state.index]);
state.index++;
return std::pair{result, state};
}注意看，每次调用 mt_next 都返回一个 pair：随机数 + 新状态。这就是纯函数式的代价——状态必须显式传递。
小技巧：可以用一个辅助类封装状态传递，让调用方不用手动维护状态。比如：
template <std::uint32_t Seed>
struct mt19937_constexpr {
static constexpr auto initial_state = init(Seed);
// 提供静态方法生成序列
};两种算法的对比
| 特性 | LCG | MT19937 |
|---|---|---|
| 状态大小 | 1 个整数 | 624 个整数 |
| 周期 | 2^31 | 2^19937-1 |
| 编译期开销 | 极低 | 较高（624次迭代） |
| 统计质量 | 差（有周期性） | 好（通过多数统计检验） |
| 适用场景 | 简单测试、种子生成 | 需要高质量随机数的场景 |
我个人建议：如果只是生成几个种子值，用 LCG 就够了。如果需要生成大量编译期随机数（比如几百个），那就上 MT19937。
编译期随机数的实际应用
我在一个编译期哈希表项目中用过编译期随机数。当时需要为每个键生成一个随机偏移量，以减少哈希冲突。如果用 LCG 生成 32 个偏移量，编译期开销几乎可以忽略。
另一个场景是编译期测试数据生成。比如：
constexpr auto test_data = generate_random_array<100>(42);
static_assert(test_data[0] != test_data[1]); // 编译期验证这样可以在编译期就发现一些边界情况，不用等到运行时。
注意：编译期随机数生成会显著增加编译时间。尤其是 MT19937，每次生成都需要复制 624 个整数的状态数组。我建议只在需要少量随机数时使用，或者用 LCG 作为轻量替代。
知识体系总览
下面这张图总结了编译期随机数生成的核心脉络：
避坑指南
我曾经在编译期 MT19937 的实现中犯过一个低级错误——忘记在 twist_all 之后重置 index。结果生成的随机数序列全是重复的。排查了半天才发现，原来是状态更新了但索引没归零。
另一个坑是 constexpr 函数的递归深度限制。如果你试图在编译期生成 10000 个随机数，编译器可能会报错。C++20 放宽了一些限制，但最好还是控制数量。
嗯，最后提醒一句：编译期随机数终究是伪随机。如果你需要密码学安全的随机数，请务必在运行时用系统提供的 CSPRNG。编译期那点“随机”，骗骗测试用例还行，骗不了攻击者。
公众号:蓝海资料掘金营，微信deep3321