面试题64：求1+2+…+n

从“公式会算，但题目不让写”开始

普通等差数列公式能立即算出答案，却需要乘法和除法；逐项累加又需要循环或递归终止判断。面试题故意封住这些直路，考查的是能否利用C++对象模型、间接调用和编译期机制表达相同控制流。

原题“求1+2到n”要求“不能使用乘除法、循环与条件判断”，具体还禁止for、while、if、else、switch、case以及条件运算符。测试代码中的if只负责打印通过或失败，限制针对四个求和实现。

右侧公式仍可作为测试预言机，但不能出现在受限解法中。n等于0时空和为0；输入域应约定n为非负整数。

先预测四种方法在n等于0时如何停下：构造法创建零个对象；虚函数法选择返回0的基类对象；函数指针法选择终止函数；模板法命中参数0的特化。若某个方案还需要if判断0，它就没有满足题目约束。

方法一：构造函数与静态成员

Temp类用两个保存当前构造序号和累计结果。每构造一个Temp，构造函数先把N加一，再把新N加入Sum；构造n个对象自然执行n次。

这种把计算藏进对象创建过程的方式称为。数组new必须逐个构造元素，即使源码没有显式for循环。

n等于5时，五次构造依次把1、2、3、4、5加入Sum，得到15。Reset必须在每次调用前执行，否则第二次求和会从上次的N和Sum继续累计。

class Temp {
public:
    Temp() {
        ++N;
        Sum += N;
    }
 
    static void Reset() {
        N = 0;
        Sum = 0;
    }
 
    static unsigned int GetSum() {
        return Sum;
    }
 
private:
    static unsigned int N;
    static unsigned int Sum;
};
 
unsigned int Temp::N = 0;
unsigned int Temp::Sum = 0;
 
unsigned int Sum_Solution1(
    unsigned int n) {
    Temp::Reset();
 
    Temp* array = new Temp[n];
    delete[] array;
    array = nullptr;
 
    return Temp::GetSum();
}

标准允许分配零长度数组，返回的指针仍可交给delete[]，因此n等于0时没有构造副作用，结果保持0。

代价是运行时O(n)、堆空间O(n)，并依赖共享可变状态。两个线程同时Reset和构造会互相污染；递归或回调重入也会破坏计数。它是语言机制演示，不是生产求和API的推荐写法。

方法二：虚函数动态分派终止递归

作者创建基类A和派生类B。A的Sum无条件返回0，充当终止体；B的Sum把n加到“n减1的结果”上。全局Array下标0指向A，下标1指向B。

双重逻辑非把0变成0，把任何非0变成1。随后通过选择A或B，不写if：n非0时继续调用B，n等于0时调用A结束。

class A;
A* Array[2];
 
class A {
public:
    virtual unsigned int Sum(
        unsigned int n) {
        return 0;
    }
};
 
class B : public A {
public:
    unsigned int Sum(
        unsigned int n) override {
        return
            Array[!!n]->Sum(n - 1) + n;
    }
};
 
int Sum_Solution2(int n) {
    A terminator;
    B recursive;
    Array[0] = &terminator;
    Array[1] = &recursive;
 
    return Array[1]->Sum(n);
}

入口无条件先调用B。n等于0时，B计算索引0并调用A；传给A的n减1按unsigned下溢为最大值，但A忽略参数并直接返回0，所以递归仍终止。这个细节是源码行为，不等于输入允许负数。

Array是全局表，却保存函数内两个栈对象的地址。整个递归在Sum_Solution2返回前完成，因此调用期间地址有效；返回后表中留下悬空指针，下一次调用会重新赋值。并发调用会让不同线程覆盖Array，存在竞态。

运行时间O(n)、调用栈O(n)。n很大时会先耗尽栈；它用多态替代条件分支，并没有减少计算步骤。

方法三：函数指针表终止递归

第三种方法不需要类层次。作者定义两个同签名函数：终止函数总是返回0，递归函数继续求和；静态按双重逻辑非选择目标。

这与虚函数方案共享原理“虚函数或函数指针终止递归”：把条件选择编码为0或1的数组下标，把两个分支变成两个可调用对象。

using Fun =
    unsigned int (*)(unsigned int);
 
unsigned int Solution3_Teminator(
    unsigned int n) {
    return 0;
}
 
unsigned int Sum_Solution3(
    unsigned int n) {
    static Fun functions[2] = {
        Solution3_Teminator,
        Sum_Solution3
    };
 
    return n
         + functions[!!n](n - 1);
}

n等于0时，表达式仍会计算unsigned的n减1，得到UINT_MAX，再把它传给终止函数；终止函数忽略参数，所以不会继续递归。无符号下溢在这里按模定义，但会触发静态分析警告，也说明这种技巧可读性较差。

函数表初始化后不再修改，比虚函数方案的全局悬空对象指针更局部；但每层仍有间接调用和递归栈，时间与空间都是O(n)和O(n)栈。

方法四：模板特化在编译期终止

前三种方案的n可在运行时传入。第四种把n作为模板非类型参数，主模板用较小参数的N加当前n；参数1与0分别提供。

template <unsigned int n>
struct Sum_Solution4 {
    enum Value {
        N = Sum_Solution4<n - 1>::N + n
    };
};
 
template <>
struct Sum_Solution4<1> {
    enum Value { N = 1 };
};
 
template <>
struct Sum_Solution4<0> {
    enum Value { N = 0 };
};

编译器实例化从n到基例的一串类型并求出枚举常量，运行时只是读取结果，因而运行时O(1)；编译工作和实例化数量O(n)。n必须是编译期常量，这就是作者在每个Test函数里单独写const number并独立检查方案四，而不能在普通Test的运行时参数上实例化。

大n会触及编译器模板实例化深度或常量表达式范围。方案四不是“无限快”，只是把工作从运行期移到编译期，并缩窄了输入能力。

四种方法的共同递推与不同载体

四种方案都在实现同一关系：从0开始，每次把当前正整数加入较小规模结果。不同点是“重复n次”和“何时停止”由谁执行：

1. 构造法由数组new触发n次构造，静态成员保存状态。
2. 虚函数法由对象动态类型选择递归体或终止体。
3. 函数指针法由数组下标选择递归函数或终止函数。
4. 模板法由编译器实例化主模板并在特化处停止。

前三种都进行O(n)次运行时工作；构造法消耗O(n)堆空间，虚函数和函数指针消耗O(n)调用栈。模板法消耗O(n)编译资源，运行时读取常量。

题目并不要求选择一个“工程最佳”方案，而是考查在约束下能否找到其他语言通道。真实代码没有这些禁令时，清晰的公式或普通循环更可维护。

数值范围与输入契约

作者大多使用unsigned int保存n和总和。32位无符号结果能精确容纳到n等于92681，此时和为4,294,930,221；n等于92682时真实结果4,295,022,903超过上限并按无符号模回绕。

递归方案通常在到达这个算术边界前就可能因调用栈过深失败；模板方案也会先遇到默认实例化深度。构造方案能分配多少对象还受堆内存限制。数值类型、栈、堆与编译器限制是四条不同边界。

Sum_Solution2入口接收int，但虚函数参数是unsigned；其他运行时方案直接接收unsigned。负数传入会转成巨大的无符号值，引发大分配或深递归。应在进入这些演示方案前验证n非负，不能指望内部终止机制处理负数。

用等差公式做独立预言机时要先把n提升到足够宽的类型，再计算乘积，避免预言机本身先溢出。测试还应连续调用同一方案，才能发现静态状态没有重置的问题。

四组官方测试如何组织

作者测试n等于1、5、10、0，期望分别为1、15、55、0。普通Test函数接收运行时n，检查方案一、二、三；方案四要求模板参数是常量，所以在Test1到Test4中分别实例化并检查。

这些用例覆盖最小正数、普通累加、较长累加和零基例，但不覆盖重复调用污染、负数转换、并发、递归深度、模板深度或无符号溢出。

可以增加串行调用5、1、5，确认构造法每次Reset；在可控小范围内把四种结果与64位公式逐项比较；编译期方案则用static_assert验证0、1、5、10。

#include <cassert>
 
static_assert(
    Sum_Solution4<0>::N == 0);
static_assert(
    Sum_Solution4<1>::N == 1);
static_assert(
    Sum_Solution4<5>::N == 15);
static_assert(
    Sum_Solution4<10>::N == 55);
 
void testRuntimeSolutions() {
    for (unsigned n :
         {0U, 1U, 5U, 10U}) {
        const unsigned expected =
            n * (n + 1U) / 2U;
        assert(Sum_Solution1(n) ==
               expected);
        assert(Sum_Solution2(
                   static_cast<int>(n)) ==
               static_cast<int>(expected));
        assert(Sum_Solution3(n) ==
               expected);
    }
 
    assert(Sum_Solution1(5) == 15);
    assert(Sum_Solution1(1) == 1);
}

测试预言机允许使用乘除，因为禁令只约束待测实现；静态扫描还应单独检查四个解法体内没有被禁关键字和条件运算符，数值断言本身无法证明语法约束成立。

本章练习

概念说明

本章核心概念包括：构造函数与静态成员。理解这些概念是掌握解题方法的关键，需要结合具体示例与边界条件反复练习。

本章回顾

1. 求1+2到n的普通公式被题目禁用，只能作为测试预言机。
2. 约束是不能使用乘除法、循环与条件判断，测试框架不受限制。
3. 方法一用构造函数与静态成员，让new数组隐式触发n次累加。
4. 方法二用虚函数动态分派，在基类终止体与派生递归体之间选择。
5. 方法三用函数指针表完成同样选择，n等于0时下溢参数被终止函数忽略。
6. 方法四用模板特化终止编译期递归，只接受编译期常量。
7. 三种运行时方案都做O(n)工作，模板方案把O(n)实例化成本移到编译期。
8. 静态共享状态、全局对象指针、递归栈、模板深度和unsigned溢出是不同风险。
9. 作者测试0、1、5、10，方案四因模板参数要求而单独检查。

名词解释