Go bits.Add64 怎么实现多字长整数加法

bits.Add64 实现多字长整数加法的关键，是把整数拆成若干个 uint64 字，并从最低位字开始相加。每次调用得到当前 64 位的 sum 和一位 carryOut，再把这个进位作为下一个更高位字的 carry 输入。

我第一次手写这段逻辑时，真正容易出错的不是 Add64 的调用，而是字序：如果切片索引 0 放最高位，循环和进位方向会变得别扭；改成低位字在前后，进位链就自然变成从索引 0 向上移动。对于可变宽度结果，循环结束后还要把最终进位追加为一个新字。

Go math/bits 文档：https://pkg.go.dev/math/bits#Add64

Go 数值类型规范：https://go.dev/ref/spec#Numeric_types

先看清 bits.Add64 的输入和输出

bits.Add64(x, y, carry) 计算 x + y + carry，返回低 64 位 sum 和高出的单比特 carryOut。官方要求 carry 输入只能是 0 或 1，否则行为未定义；输出进位则保证仍是 0 或 1。

package main

import (
    "fmt"
    "math"
    "math/bits"
)

func main() {
    // 最大 uint64 加 1：低 64 位回到 0，同时产生一位进位。
    sum, carry := bits.Add64(math.MaxUint64, 1, 0)
    fmt.Printf("sum=%d carry=%d\n", sum, carry)
}

这个调用没有返回 128 位类型，因为 Go 没有预定义的 uint128。它把结果拆成“当前字”和“下一字的进位”，正好适合多字长整数。文档还说明单次 Add64 的执行时间不依赖输入值，但这不代表包含切片长度、扩容和分支的整个自定义函数自动成为密码学常量时间实现。

先把多字长整数存成低位字在前

本文约定 words[0] 保存最低 64 位，words[1] 保存接下来的 64 位。一个两字整数表示为 words[0] + words[1] × 2^64。这种顺序常被称为 little-endian limbs；它描述的是字数组顺序，不等同于最终网络字节序。

例如 []uint64{12, 33} 表示 33 × 2^64 + 12。最低位相加后产生的进位，直接交给索引 1 的高位字即可。

我更愿意把字序写进类型注释，而不是只靠团队默契。高低位顺序一旦混用，普通小数值可能看不出问题，直到进位跨字时才暴露。

先实现固定 128 位加法

固定 128 位是最容易理解的版本。数组长度为 2，索引 0 是低位，索引 1 是高位；第二次调用返回的进位就是 128 位之外的溢出。

package wide

import "math/bits"

// Uint128 使用低位字在前的固定宽度表示。
type Uint128 [2]uint64

func Add128(x, y Uint128) (sum Uint128, overflow uint64) {
    // 低 64 位没有外部进位，从 0 开始。
    sum[0], overflow = bits.Add64(x[0], y[0], 0)

    // 把低位产生的进位加入高 64 位，并返回最终溢出位。
    sum[1], overflow = bits.Add64(x[1], y[1], overflow)
    return sum, overflow
}

如果调用方处理的是固定宽度寄存器、协议字段或模 2^128 运算，可以保留两字结果，并明确决定是否忽略 overflow。如果希望得到数学意义上的完整无符号和，最终进位就必须成为第三个字。

把固定 128 位推广为任意长度

可变长度版本先取两个输入的较大长度，结果预留一个额外字的容量。循环中，输入不存在的高位按 0 补齐。这样同一段逻辑既能处理等长整数，也能处理一长一短的情况。

package wide

import "math/bits"

func AddWords(x, y []uint64) []uint64 {
    // 零也保留一个字，避免返回值没有明确的零表示。
    if len(x) == 0 && len(y) == 0 {
        return []uint64{0}
    }

    n := len(x)
    if len(y) > n {
        n = len(y)
    }

    // 长度先取较大输入，容量多留一格给最高进位。
    sum := make([]uint64, n, n+1)
    var carry uint64

    for i := 0; i 

这段代码采用新切片保存结果，不修改输入，调用方更容易推理别名和生命周期。它保留较大输入的宽度；只有最终进位为 1 时才扩展。若项目要求唯一的最短表示，可以在返回前去掉多余的最高位零，但固定宽度协议字段通常不该做这一步。

用跨多个字的例子检查进位链

最值得检查的不是普通的 1 + 2，而是进位连续跨过多个全 1 字。假设：

• x = []uint64{math.MaxUint64, math.MaxUint64}
• y = []uint64{1}

索引 0 的结果是 0、进位 1；索引 1 再计算 MaxUint64 + 0 + 1，结果仍是 0、进位仍是 1；循环结束后追加最高字 1，因此结果是 []uint64{0, 0, 1}，也就是 2^128。

package wide_test

import (
    "math"
    "reflect"
    "testing"

    "example.com/wide"
)

func TestAddWordsCarryAcrossAllLimbs(t *testing.T) {
    // 两个连续的全 1 字加 1，应把进位传播到新的最高字。
    x := []uint64{math.MaxUint64, math.MaxUint64}
    y := []uint64{1}
    want := []uint64{0, 0, 1}

    if got := wide.AddWords(x, y); !reflect.DeepEqual(got, want) {
        // 错误信息同时保留实际字数组和期望字数组，便于定位字序问题。
        t.Fatalf("AddWords() = %v, want %v", got, want)
    }
}

除了连续进位，还应覆盖空输入、只有一个输入、输入长度不同、最高位不进位、最高位进位和带多余最高零字的输入。这里的测试代码是边界用例模板，不是性能基准。

最终进位该追加还是当成溢出

对我来说，这个选择应该由调用方的数据模型决定，而不是藏在加法函数里。固定宽度 API 返回 overflow 最清楚；可变宽度 API 直接追加最高字更符合数学结果。若业务要求溢出即失败，可以在固定宽度函数外检查最终进位并转换成领域错误。

什么时候不值得自己维护字数组

bits.Add64 适合底层数值结构、固定 limb 布局、序列化格式或需要精确控制进位的实现。如果项目只是要做一般任意精度整数计算，math/big.Int 往往更合适，它已经提供加减乘除、比较、字符串转换和成熟的内部表示。

自己维护 []uint64 的代价包括字序约定、零值规范化、序列化、负数设计、容量复用、别名规则和完整测试。只为一次普通大整数相加而承担这些约束，通常得不偿失。反过来，如果上层格式本来就是固定的 64 位字数组，Add64 能让进位语义非常直接。

实现时的检查清单

1. 明确索引 0 是低位字，并把约定写进类型注释。
2. 只把 0 或 1 传给 Add64 的 carry 参数。
3. 从最低位索引开始循环，把上一轮 carry 传给下一轮。
4. 不等长输入按缺失高位为 0 处理。
5. 根据固定宽度或可变宽度模型处理最终进位。
6. 分别测试单字进位、连续进位、最高位溢出和空输入。
7. 涉及密码学时，不要仅凭 Add64 单次定时特性推断整个算法是常量时间。

多字长加法的代码很短，但它依赖三个必须一致的约定：低位字在前、进位只能是单比特、最终进位由数据宽度策略处理。把这三点固定下来后，从 128 位扩展到任意数量的 64 位字，只是把同一个 Add64 单元沿切片重复使用。

相关问题

bits.Add64 能直接返回 uint128 吗？

不能。它返回当前 64 位和一位进位，调用方需要用两个或更多 uint64 组合更宽的整数。

carry 可以传大于 1 的值吗？

不可以。官方文档要求 carry 输入为 0 或 1，其他值的行为未定义。连续调用时直接使用上一轮的 carryOut 即可。

为什么切片要低位字在前？

因为加法进位从低位向高位传播，低位放在索引 0 后可以按递增索引顺序循环，代码更直接。

能在原切片上原地相加吗？

可以设计专门的原地 API，但必须明确目标容量和切片重叠规则。初版优先返回新切片，更容易避免别名覆盖和扩容问题。