Python3中如何用纯算术方式实现自然数的XOR运算

现有方法的失效根源 #

此前流传的适用于0/1布尔域的XOR算术公式，本质是对布尔真值表的低次多项式插值，完全没有实现二进制位的逐位映射逻辑，一旦输入的自然数取值大于1，多项式的取值就会快速偏离XOR的定义，因此无法直接推广到全体自然数场景。
三类常见测试方法的失效原因：

• 原帖子中的三次多项式 a + b - a*b*(1 + a + b - (a*b))：仅在a,b取0或1的四个离散点上能得到正确结果，超出定义域后数值会快速失真，代入a=12、b=5得到2537就是典型的多项式膨胀效应。
• 差值平方公式 (a-b)**2：只是偶然在a,b∈{0,1}时匹配XOR真值表，本身和二进制逐位异或的逻辑没有关联，大数值下结果完全无参考价值。

正确的纯算术实现逻辑 #

XOR的本质定义为：对两个自然数的二进制表示，逐位单独做布尔异或，再将各位结果按二进制权重累加，最终结果即为两数的XOR值。将该逻辑完全转化为纯算术操作仅需要两步：

1. 用纯算术方式提取任意自然数n的第k位（k从0开始，对应2^k权重位）的0/1取值，表达式为：

   bit_k(n) = floor(n / 2**k) - 2 * floor(n / 2**(k+1))
   

   该表达式等价于传统按位操作的指定位提取，全程仅依赖取整、幂运算、减法，不涉及位运算。
2. 对两个数在第k位的0/1取值，使用严格匹配布尔真值表的异或公式计算该位结果：当x,y∈{0,1}时，异或结果为 x + y - 2*x*y。
   将所有位的计算结果乘以对应权重2^k后累加，就得到覆盖全体自然数的XOR算术表达式：

a ⊕ b = Σ（k从0到覆盖两数最高位的上限，即2^k > max(a,b)） [ 2^k * (bit_k(a) + bit_k(b) - 2 * bit_k(a) * bit_k(b)) ]

测试验证 #

以a=12、b=5为测试用例：

• k=0（权重1）：bit_0(12)=0，bit_0(5)=1，异或结果=1，贡献值1
• k=1（权重2）：bit_1(12)=0，bit_1(5)=0，异或结果=0，贡献值0
• k=2（权重4）：bit_2(12)=1，bit_2(5)=1，异或结果=0，贡献值0
• k=3（权重8）：bit_3(12)=1，bit_3(5)=0，异或结果=1，贡献值8
• 累加总结果为9，与原生a^b的计算结果完全一致。
  该实现全程依赖初等算术操作，不存在大数值下的结果失真问题，符合对“算术特征实现”的要求。

内容的提问来源于stack exchange，提问作者Nand0san