C++另辟蹊径计算1到n的和

前言计算 1 到 n 的和最直接的做法是一个循环。但这个问题在面试和习题里经常被加上各种限制「不许用循环」「不许用乘除法」「不许用 if」于是出现了许多「另辟蹊径」的写法公式、递归、模板元编程、构造函数副作用、虚函数分派。了解这些写法与其说是为了炫技不如说是借它把 C 的几套机制串起来看一遍。常见的误解有三个。第一认为公式n(n1)/2永远安全——当 n 很大且用int计算时乘法会溢出而有符号整数溢出是未定义行为undefined behavior, UB。第二认为递归比循环「更优雅」——递归深度等于 n 时栈溢出是实实在在的风险。第三把构造函数累加这类谜题写法当成工程手段——它依赖静态状态不可重入也不适合多线程。本文按「公式 → 循环与递归 → 编译期计算 → 构造函数技巧」展开每个方案都说明它的限制最后给出一个可以实际使用的版本。代码以 C17 为准。一、公式法高斯求和公式1 2 ... n n(n 1) / 2// 适用于 C17#include cstdintstd::uint64_t sumFormula(std::uint32_t n) {const std::uint64_t m n;return m * (m 1) / 2;}这段代码有两个细节值得说先转成 64 位再乘。如果写成n * (n 1) / 2且n是std::uint32_t乘法会在 32 位无符号数上进行结果按模 2³² 回绕——虽然无符号回绕是良定义的但答案已经错了。先转成std::uint64_t中间结果最大约 2⁶³放得下。必须是先乘后除。m / 2 * (m 1)在 m 为奇数时会丢掉 0.5结果偏小。由于m与m1中必有一个偶数先乘再除以 2 不会丢精度。如果 n 用int且可能接近INT_MAX那么n * (n 1)会在int上溢出这是 UB不是「得到一个负数」这么简单。公式法本身没问题问题在于类型选得太窄。二、循环与递归循环版本最直白// 适用于 C17#include cstdintstd::uint64_t sumLoop(std::uint32_t n) {std::uint64_t total 0;for (std::uint32_t i 1; i n; i) {total i;}return total;}注意当n UINT32_MAX时i n永远成立i回绕到 0 后继续循环形成死循环。把i改成std::uint64_t或换成for (std::uint32_t i 1; i ! n 1; i)并单独处理边界都可以规避。这类边界在真实数据里很少出现但写库函数时值得留意。递归版本// 适用于 C17std::uint64_t sumRecursive(std::uint32_t n) {if (n 0) return 0;return n sumRecursive(n - 1);}时间 O(n)、空间 O(n)调用栈。n 稍大就可能栈溢出而且编译器不一定能把它优化成循环尾递归优化不是标准保证。递归在这里没有任何优势只是用来演示「同一个问题的另一种表达」。如果题目要求「不能用 if」可以用逻辑与的短路特性代替判断// 适用于 C17std::uint64_t sumShortCircuit(std::uint32_t n) {std::uint64_t total 0;n 0 (total n sumShortCircuit(n - 1));return total;}从左到右求值左边为假时右边不会执行起到了if的作用。可读性很差递归深度问题也依然存在只适合做智力题。三、编译期计算如果 n 是编译期常量可以让编译器直接算出结果运行期零成本。constexpr 函数C14 起支持循环// 适用于 C17constexpr std::uint64_t sumConstexpr(std::uint64_t n) {std::uint64_t total 0;for (std::uint64_t i 1; i n; i) {total i;}return total;}static_assert(sumConstexpr(100) 5050, 100 的和应为 5050);C11 的constexpr函数体只能有一条 return 语句写循环需要递归C14 放宽后可以直接写循环和局部变量。static_assert在编译期检查结果不满足就编译失败。模板递归// 适用于 C17template unsigned Nstruct Sum {static constexpr unsigned long long value N SumN - 1::value;};template struct Sum0 {static constexpr unsigned long long value 0;};static_assert(Sum100::value 5050, 编译期求和);模板特化提供了递归的终止条件。C17 起静态数据成员默认是内联的不需要在类外再写定义。这种写法在 C11 时代很常见现在有constexpr函数后已经不再必要——模板递归的编译错误信息通常很难读实例化层次也有上限。四、构造函数的副作用经典谜题利用「创建 n 个对象」这件事本身完成累加。每个对象构造时把静态计数器加一并累加到总和。// 适用于 C17#include cstdint#include vectorclass Summer {public:Summer() {current_;total_ current_;}static std::uint64_t total() { return total_; }static void reset() {current_ 0;total_ 0;}private:static std::uint64_t current_;static std::uint64_t total_;};std::uint64_t Summer::current_ 0;std::uint64_t Summer::total_ 0;std::uint64_t sumByCtor(std::uint32_t n) {Summer::reset();std::vectorSummer objects(n); // 构造 n 个对象逐个累加return Summer::total();}std::vectorSummer objects(n)会值初始化 n 个元素每个元素调用默认构造函数。第 k 个对象构造时current_变成 ktotal_累加 k最终得到 1 2 … n。这个写法的问题很明显依赖可变的静态状态不可重入多线程同时调用会数据竞争属于 UB为了求和分配了 n 个对象的存储时间与空间都不划算如果编译器把对象优化掉理论上不允许因为构造函数有副作用但依赖这一点本身就很脆弱。它适合作为「展示构造函数调用时机」的例子不适合放进生产代码。五、完整示例// 适用于 C17#include cstdint#include iostreamstd::uint64_t sumFormula(std::uint32_t n) {const std::uint64_t m n;return m * (m 1) / 2;}constexpr std::uint64_t sumConstexpr(std::uint64_t n) {std::uint64_t total 0;for (std::uint64_t i 1; i n; i) {total i;}return total;}static_assert(sumConstexpr(10) 55, 1 到 10 的和应为 55);int main() {for (std::uint32_t n : {0u, 1u, 10u, 100u, 1000u}) {std::cout n - sumFormula(n) \n;}// 与循环结果对照小范围std::uint64_t check 0;for (std::uint32_t i 1; i 1000; i) check i;std::cout check check \n; // 500500std::cout compile-time sumConstexpr(1000) \n; // 500500return 0;}按标准语义输出依次是 0、1、55、5050、500500随后check 500500最后一行同样是 500500。三个结果互相印证比单独看一个数字更可靠。sumFormula对n 0返回 0无需特判这是因为0 * 1 / 2 0公式在边界上自然成立。常见坑点1. 先用 32 位乘再转 64 位❌return n * (n 1) / 2;n 较大时结果错误。 ✅std::uint64_t m n; return m * (m 1) / 2;。2. 先除后乘❌return m / 2 * (m 1);m 为奇数时少算一半。 ✅ 先乘后除m与m1必有一个偶数不会丢精度。3. 用有符号 int 计算并溢出❌int total n * (n 1) / 2;溢出是 UB。 ✅ 用std::uint64_t或先做范围检查。4. 递归深度过大❌sumRecursive(1000000)栈溢出。 ✅ 用循环或公式递归只用于教学演示。5. 循环变量回绕❌for (std::uint32_t i 1; i n; i)且n UINT32_MAX死循环。 ✅ 用更宽的循环变量或把上界单独处理。6. 认为尾递归一定会被优化❌ 依赖编译器把递归改成循环。 ✅ 标准不保证尾递归优化需要稳定行为就手写循环。7. 在构造函数技巧里使用静态变量却忽略线程安全❌ 多线程同时调用sumByCtor静态计数器被并发修改。 ✅ 这个技巧只用于单线程演示生产代码用无状态的公式或循环。8. 模板递归层数过深❌Sum100000::value实例化层次过深编译失败或极慢。 ✅ 编译期求和优先用constexpr函数。总结方案时间空间适用场景主要风险公式O(1)O(1)生产代码首选类型宽度不足导致溢出循环O(n)O(1)教学、需要逐项处理边界回绕递归O(n)O(n)教学栈溢出constexpr编译期无运行期开销n 为常量需要 C14 及以上模板递归编译期无运行期开销老代码、模板练习编译错误难读、层次上限构造函数O(n)O(n)谜题/演示静态状态、非线程安全「另辟蹊径」的写法大多是为了绕开题目限制而不是为了解决实际问题。真正写代码时n(n1)/2配一个足够宽的无符号类型就够了需要编译期结果就用constexpr。其余方案了解其原理即可不必在工程里使用。