整数位和与位积：公理、证明与存在性边界

计算器入口：返回计算器。本文对应 /cpp-cloud/bit-arithmetic/theory/，讨论整数域上的条件性定理，不把有限位计算成功当作全域存在证明。

1. 定义域与逻辑前提

ℤ 是全部整数，ℕ₀ = {0,1,2,…}。a、b、c、x、y 属于 ℤ；移位次数 k 与截断位数 n 属于 ℕ₀（k ≥ 0，n ≥ 0）。固定参数 t = F(1,1) ∈ ℤ；计算器可另外限制输入参数，但那是实现范围，不是本文定理的存在性结论。

每个整数都采用欧几里得除法，而不是向零截断：

x = 2⌊x/2⌋ + (x mod 2),       x mod 2 ∈ {0,1}.
x mod 2ⁿ ∈ {0,…,2ⁿ−1};        x ≡ x mod 2ⁿ (mod 2ⁿ).
n = 0 时模数为 1，余数为 0。
例如 −1 = 2·(−1)+1，−3 = 2·(−2)+1。

负整数使用无限符号扩展的二进制补码。对正整数 n，−n = NOT(n−1)，其中 NOT(x) = −x−1；这是通常二进制按位取反的定义，不是对参数化 F 的额外公理。负数不能以“高位最终全为零”处理，也不能靠对负数不断除以 2 的递归保证终止。

全文前提：先假设相应的整数值全域函数存在，再证明它必须满足哪些性质。F 的存在与 G 的存在是独立问题；唯一性不蕴含存在性。下面没有“任意 t 都存在整数位积”的承诺。

2. 位和 F（记作 |）的五条公理

写 a | b = F(a,b)。仅假设以下五条，不把结合律当作公理：

(F1) F(a,0) = a.
(F2) F(a,b) = F(b,a).
(F3) F(a mod 2ᵏ,b mod 2ᵏ) mod 2ᵏ = F(a,b) mod 2ᵏ，k≥0。
(F4) F(2a,2b) = 2F(a,b).
(F5) F(a,b) = F(2F(⌊a/2⌋,⌊b/2⌋), F(a mod 2,b mod 2)).

所有变量都可为负整数。F5 中的商必须是 floor/2，余数必须是 mod 2。F1 与 F2 给出 F(0,a)=a；特别是 F(0,0)=0，F(0,1)=F(1,0)=1。

2.1 不借助结合律的最低位递推

将 F5 应用于 (2x,1)，用 F1 得到：

F(2x,1) = F(2F(x,0),F(0,1)) = F(2x,1).

这一步本身只是恒等式，不能据此直接宣称 F(2x,1)=2x+1。真正的推导是将 F5 应用于 (2x+1,0)：

2x+1 = F(2x+1,0)
     = F(2F(x,0),F(1,0))
     = F(2x,1).

这是后续进位证明的关键。令 t = 2s+r，其中 s=⌊t/2⌋、r=t mod 2∈{0,1}。F5、F4 与刚证明的恒等式给出：

F(2X,t) = F(2F(X,s),r) = 2F(X,s)+r.

令 a=2A+α，b=2B+β，α,β∈{0,1}：
F(a,b) = 2F(A,B)+α+β                    若 αβ=0；
F(a,b) = 2F(F(A,B),s)+r                  若 α=β=1。

右侧的 + 和倍乘都是普通整数运算。第二式中的 F(F(A,B),s) 有指定括号，此时尚未证明可交换括号。F4 反复应用立即得到 F(2ᵏa,2ᵏb)=2ᵏF(a,b)，k≥0。

3. 有限低位、数字公式与 F 的结合律

3.1 F 的模 2ⁿ 相容性

对 n 归纳。n=0 显然；上述最低位递推说明，输出最低位只依赖输入最低位和 r，输出的高位是若干个 F 的复合。若输入模 2ⁿ 相同，则最低位相同、商模 2ⁿ⁻¹ 相同；由归纳假设，所有高位 F 复合模 2ⁿ⁻¹ 也相同。因此：

a ≡ a′ (mod 2ⁿ), b ≡ b′ (mod 2ⁿ)
⇒ F(a,b) ≡ F(a′,b′) (mod 2ⁿ).
特别地 F(a,b) ≡ F(a mod 2ⁿ,b mod 2ⁿ) (mod 2ⁿ)。

此归纳只用二元递推，不用结合律。记 Rₙ=ℤ/2ⁿℤ，F 因而诱导 Rₙ 上的良定义二元运算。

3.2 数字公式 h 与进位计数恒等式

对 m≥0 个最低位 1，定义进位数 h(m) 与最终最低位 ε(m)：

r=0：h(m)=⌊m/2⌋，     ε(m)=m mod 2；
r=1：h(m)=max(m−1,0)， ε(m)=0（m=0），否则 ε(m)=1。
统一式：m = (2−r)h(m)+ε(m)，ε(m)∈{0,1}。

解释：两个 1 合并后变成最低位 r，并向高位送入一个 s；最低位的 1 数量减少 2−r。于是对任意非负整数 p、q，直接代入定义可验证：

ε(p+q) = ε(ε(p)+ε(q)),
h(p+q) = h(p)+h(q)+h(ε(p)+ε(q))。

第一式配合第二式就是“先分组归约，再合并”和“整体归约”的进位计数一致性；r=0 是通常的成对进位，r=1 是只要非空便保留一个 1。

3.3 结合律的归纳证明（不循环论证）

证明 Rₙ 上 F 结合且交换。交换律来自 F2，R₀ 只有一个元素。假设 Rₙ₋₁ 上结合律已成立，那里有限次 F 的括号与顺序可以消去。

把任意有限组输入写成 xᵢ=2Xᵢ+αᵢ，αᵢ∈{0,1}，m=Σαᵢ。最低位递推与进位计数恒等式给出数字公式：

任一括号树的 F 合并结果（模 2ⁿ）为
2·[ X₁ | ⋯ | Xⱼ | s | ⋯ | s ] + ε(m)，
                         └─ h(m) 份 ─┘
方括号在 Rₙ₋₁ 中计算；空合并为 0。

严格地，对括号树归纳：左右子树分别贡献 h(p)、h(q) 份 s，合并其残留最低位又贡献 h(ε(p)+ε(q)) 份 s；总数恰为 h(p+q)。高位只在 Rₙ₋₁ 中重新分组，合法性正是归纳假设，而不是待证的 Rₙ 结合律。这也证明该数字公式。

对三项输入，任何括号都具有相同的 X₁、X₂、X₃、h(m) 与 ε(m)，故 Rₙ 上结合律成立。归纳完成。于是对全部整数 a、b、c：

F(F(a,b),c) ≡ F(a,F(b,c)) (mod 2ⁿ)，对每个 n≥0 成立。

一个非零整数不可能被任意大的 2ⁿ 整除，因此两边相等。F 的结合律由五公理推出，而非预先假设。后文才可自由使用有限次位和记号 ⊕；它表示 F 合并，不表示通常加法，也不默认是 XOR。

附带结论：对固定 t，最低位递推逐层确定每个输出的模 2ⁿ 余数，因此若整数全域 F 存在，则唯一。递推可能只确定一个非普通整数的 2-adic 值；这仍不证明整数值存在。

4. 位积 G（记作 &）的公理

在已存在的 F 上，假设整数值函数 G:ℤ×ℤ→ℤ 存在，写 a & b = G(a,b)。仅要求：

(G1) G(0,b) = 0.
(G2) G(2a,b) = 2G(a,b).
(G3) G(2a+1,b) = F(2G(a,b),b).

这里 a 可以为负整数；未假设 G 的交换律、分配律、结合律或双变量移位性质。a=0 代入 G3 给出 G(1,b)=F(0,b)=b。

5. G 的有限低位展开、唯一性与交换律

令 aᵢ=⌊a/2ⁱ⌋ mod 2，bⱼ=⌊b/2ʲ⌋ mod 2。负数的这些位无限符号扩展。对 G2/G3 只展开 n 次，F 的结合律与双变量移位性质给出一个有限恒等式：

G(a,b) = ( ⊕_{0≤i<n, aᵢ=1} 2ⁱb )
         | 2ⁿG(⌊a/2ⁿ⌋,b)。

空位和是 0。对每个有限 n，尾项仍是整数乘以 2ⁿ；由 F 模相容性和 F(x,0)=x，该尾项模 2ⁿ 可去掉。由此得：

G(a,b) ≡ ⊕_{0≤i<n, aᵢ=1} 2ⁱb                (mod 2ⁿ)。

每项的模余数只依赖 b 的前 n 位；a 的选项也只依赖前 n 位。因此 G 具有双变量模相容性：

G(a,b) ≡ G(a mod 2ⁿ,b mod 2ⁿ)               (mod 2ⁿ)。

若 G 与 G′ 都满足公理，则同一有限展开给出 G(a,b)≡G′(a,b) (mod 2ⁿ) 对所有 n 成立，故 G=G′。这是存在时唯一，不是存在证明。

为证明交换律，需要把上式展开为对称的双重位和。以下有限二进制拼接引理不使用 G：

若 u 的第 j 位为 0，则 F(u,2ʲ)=u+2ʲ。

证明：把 u 写成 2ʲ⁺¹v+w，0≤w<2ʲ。由最低位递推连续 j 次剥去 w 的低位，得到 F(u,2ʲ)=2ʲF(2v,1)+w；再用 F(2v,1)=2v+1 即得结论。因而有限个互不重叠的二进制位，其 F 合并等于普通二进制拼接；尤其 b mod 2ⁿ = ⊕_{j<n,bⱼ=1}2ʲ。

代回单变量展开，使用 F 的移位、结合律与模相容性，得到：

G(a,b) ≡ ⊕_{0≤i,j<n, aᵢ=bⱼ=1, i+j<n} 2ⁱ⁺ʲ    (mod 2ⁿ)。

这不是普通整数双重求和：相同位权的多个项要用 F 合并，进位由 t 决定。i+j≥n 的项是 2ⁿ 的倍数，可模去掉。双重位和交换 i、j 后不变，故 G(a,b)≡G(b,a) 对所有 n 成立，最终 G(a,b)=G(b,a)。由 G2 和交换律又得 G(a,2ᵏb)=2ᵏG(a,b)，k≥0。

6. 分配律：先非负输入，再全部整数

若 a≥0，其二进制展开有限，尾项最终为 G(0,b)=0，所以精确成立：

G(a,b) = ⊕_{i: aᵢ=1} 2ⁱb。

此时 b、c 已可为任意整数。由 F 的双变量移位与结合、交换律：

G(a,F(b,c))
 = ⊕_{i: aᵢ=1} 2ⁱF(b,c)
 = ⊕_{i: aᵢ=1} F(2ⁱb,2ⁱc)
 = F(⊕_{i: aᵢ=1}2ⁱb, ⊕_{i: aᵢ=1}2ⁱc)
 = F(G(a,b),G(a,c))。

这是非负首变量的直接证明，不要求 F(b,c) 非负，也不要求 t 非负。若只称“先在非负域验证”，必须注意中间结果未必仍在非负域；上述证明避开了该漏洞。

对任意整数 a、b、c 和任意 n≥0，令 A=a mod 2ⁿ、B=b mod 2ⁿ、C=c mod 2ⁿ，均为非负整数。先对 A 使用已证分配律，再由 F、G 模相容性将每个输入与复合运算逐一换回 a、b、c。于是：

G(a,F(b,c)) ≡ F(G(a,b),G(a,c)) (mod 2ⁿ)。

对所有 n 成立，故是整数等式。结合 G 的交换律还得到另一侧分配律：G(F(a,b),c)=F(G(a,c),G(b,c))。

7. 结合律：非负归纳，再模转移到 ℤ

先对非负首变量 a 作强归纳，允许 b、c 是任意整数。a=0 时两边都为 0。a>0 时写 a=2u 或 a=2u+1，其中 0≤u<a。

偶数情形只用 G2 与归纳假设：

G(G(2u,b),c)
 = G(2G(u,b),c)
 = 2G(G(u,b),c)
 = 2G(u,G(b,c))
 = G(2u,G(b,c))。

奇数情形使用刚证明的全整数分配律，不能偷用结合律：

G(G(2u+1,b),c)
 = G(F(2G(u,b),b),c)
 = F(G(2G(u,b),c),G(b,c))
 = F(2G(G(u,b),c),G(b,c))
 = F(2G(u,G(b,c)),G(b,c))
 = G(2u+1,G(b,c))。

归纳成立。现在取任意整数 a、b、c，以 A、B、C 为模 2ⁿ 的非负代表。对 A、B、C 应用已证等式；即使 G(A,B) 或 G(B,C) 是负数，归纳命题允许其他变量是任意整数，所以仍合法。再由 G 模相容性逐层替换，得到：

G(G(a,b),c) ≡ G(a,G(b,c)) (mod 2ⁿ)，对所有 n≥0。

整数差被所有 2ⁿ 整除，故为零。G 在存在时交换、分配且结合；这三条都是结论。

8. 存在性不能省略：t=0 的整数反例

t=0 时，s=r=0。F 的递推成为每一位的 XOR，通常的无限补码 XOR 是一个满足五公理的整数值 F。在非负整数上，G 是二进制无进位乘法，有限展开确实存在。但它不能按上述三条公理自然扩展成全部整数上的整数值 G。

反证：若这样的 G 存在，令 c=G(−1,−1)∈ℤ。由于 −1=2·(−1)+1，G3 要求：

c = F(2c,−1)
  = (2c) XOR (−1)
  = NOT(2c)
  = −2c−1。
所以 3c=−1。

不存在满足 3c=−1 的整数。因此 t=0 下 F 虽然存在，自然数位积虽然存在，全整数位积仍不存在。把 −1 截成 n 位全 1，会得到一系列有限低位结果；它们可以相容，却不能因此认定有整数结果 c。此例的模方程 3c≡−1 (mod 2ⁿ) 每层有唯一解，但不存在同时表示这些余数的普通整数。若改用 2-adic 数，−1/3 可以存在，那已改变目标值域，不是本计算器的整数答案。

作为对照，t=2 时通常整数加法 F(a,b)=a+b 与乘法 G(a,b)=ab 满足全部公理，因此至少有可存在的参数；这不是对所有其他参数的认证。

9. 对计算器结果的正确解读

• 定义域是整数，负数采用无限补码；程序内部的有限位数只是算法或资源限制。
• 固定参数下：如果整数全域 F、G 存在，以上代数律与唯一性必然成立。
• 一次有限归约成功，仅证明该次输入得到一个可验证结果，不证明全域存在。
• 截断低位、预算超限或没有找到有限结果，都不能替代存在性证明或不存在性证明。
• 不能对负数无限符号位做“最后一位”归纳；本文通过每个有限模数证明，再利用整数差为零收束。
• 静态证明不扩大计算器已有参数认证、输入范围、资源限制或错误处理承诺。

返回计算器