LeetCode-Go 题解：1073 Adding Two Negabinary Numbers 负二进制加法——绕过十进制的直接进位模拟
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
导读
本文围绕 LeetCode 第 1073 题 "Adding Two Negabinary Numbers"（负二进制数相加）展开，完整解析LeetCode-Go仓库中该题目的官方 Go 实现：先说明为什么"先转十进制再相加"的思路会在长数据上溢出失败，再给出直接在 -2 进制上从低位向高位模拟进位的 O(n) 解法，并逐一证明进位三种情形的数学正确性。读完本文，你将掌握负进制加法的进位本质（进位值为 -1 而非 +1）、前导零的处理技巧，以及仓库中配套的测试用例是如何覆盖边界与超长数据的。
题目：以数组形式给出的 -2 进制数
给定两个基数（base）为-2的数arr1和arr2，返回它们相加的结果。
每个数以数组格式给出：数组由若干0和1组成，按**最高有效位（MSB）到最低有效位（LSB）**的顺序排列。例如arr = [1,1,0,1]表示数字：
(-2)^3 + (-2)^2 + (-2)^0 = -8 + 4 + 0 + 1 = -3数组格式的数是不含前导零的：要么arr == [0]，要么arr[0] == 1。要求返回的结果同样为不含前导零、由0和1组成的数组。
官方示例
Input: arr1 = [1,1,1,1,1], arr2 = [1,0,1] Output: [1,0,0,0,0]解释：arr1表示 11，arr2表示 5，两者之和为 16，其 -2 进制表示为[1,0,0,0,0]（即(-2)^4 = 16）。
题目约束
1 <= arr1.length <= 10001 <= arr2.length <= 1000arr1和arr2都没有前导零arr1[i]为0或1arr2[i]为0或1
也就是说，两个操作数的长度最长可达 1000 位，这正是决定算法选型的关键约束（详见下文）。
为什么"先转十进制"的思路行不通
面对进制转换类题目，最直观的直觉是：先把两个 -2 进制数转成十进制做加法，再把结果表示回 -2 进制。这个思路完全正确，但在本题的数据范围下会失败——因为数组长度最长 1000，其代表的十进制数值可以轻易超过int64（最大约 9.2×10^18）的表示范围。
仓库源码中保留了这一"错误示范"作为对照，见 解法二的实现 及其注释：
// 解法二 标准的模拟，但是这个方法不能 AC，因为测试数据超过了 64 位，普通数据类型无法存储 func addNegabinary1(arr1 []int, arr2 []int) []int { return intToNegabinary(negabinaryToInt(arr1) + negabinaryToInt(arr2)) }从源码注释可以确认：这道题在第 257 / 267 组测试数据处会出现 WA（Wrong Answer），正是由于十进制中间结果溢出int64；即便改用big.Int等大数类型，也徒增实现复杂度。因此正确方向是直接进行 -2 进制的加法，完全绕开十进制。
核心思路：直接在 -2 进制上模拟低位进位
加法天然从低位到高位逐位累加，遇到进位再从低往高推进。所以从两个数组的末尾（LSB）往前扫描，模拟低位相加的过程即可。
关键在于进位规则。假设从 k-1 位向高位 k 产生了一次进位，而 k-1 位是两个 1 相加（即1 + 1 + carry的情形），那么 k 位上的两个数字存在三种组合，逐一分析如下（原文档给出的完整数学证明）：
情形一：k 位上是 0 和 0 → 最终 k 位为 1
证明：由于进位是由 k-1 位进过来的，所以 k-1 位是 2 个 1；现在 k 位是 2 个 0，加起来的和是2 * (-2)^(k-1)。
- 当 k 为奇数时：
2 * (-2)^(k-1) = (-1)^(k-1) * 2 * 2^(k-1) = 2^k - 当 k 为偶数时：
2 * (-2)^(k-1) = (-1)^(k-1) * 2 * 2^(k-1) = -2^k
综合起来就是(-2)^k，所以最终 k 位上有一个 1。
情形二：k 位上是 0 和 1 → 最终 k 位为 0
证明：由于进位是由 k-1 位进过来的，所以 k-1 位是 2 个 1；现在 k 位是 1 个 0 和 1 个 1，加起来的和是(-2)^k + 2 * (-2)^(k-1)。
- 当 k 为奇数时：
(-2)^k + 2 * (-2)^(k-1) = -2^k + 2^k = 0 - 当 k 为偶数时：
(-2)^k + 2 * (-2)^(k-1) = 2^k - 2^k = 0
综合起来就是 0，所以最终 k 位上有一个 0。
情形三：k 位上是 1 和 1 → 最终 k 位为 1
证明：由于进位是由 k-1 位进过来的，所以 k-1 位是 2 个 1；现在 k 位是 2 个 1，加起来的和是2 * (-2)^k + 2 * (-2)^(k-1)。
- 当 k 为奇数时：
2 * (-2)^k + 2 * (-2)^(k-1) = -2^(k+1) + 2^k = 2^k * (1 - 2) = -2^k - 当 k 为偶数时：
2 * (-2)^k + 2 * (-2)^(k-1) = 2^(k+1) - 2^k = 2^k * (2 - 1) = 2^k
综合起来就是(-2)^k，所以最终 k 位上有一个 1。
结论：负进制的进位是 -1
综上所述，-2 进制的进位原理与 2 进制完全一致，唯一的差别是：2 进制的进位是 +1，而 -2 进制的进位是 -1。
更直白地说：低位一旦产生进位（k-1 位两个 1 相加），无论高位两位如何取值，都可以用"当前位结果 + 向更高位产生一个值为 -1 的进位"来统一表达。这就是下面源码中那两行核心公式的由来。
源码实现逐行解析：O(n) 直接进位模拟
仓库中的 解法一实现 将上述推导浓缩为极简代码：
// 解法一 模拟进位 func addNegabinary(arr1 []int, arr2 []int) []int { carry, ans := 0, []int{} for i, j := len(arr1)-1, len(arr2)-1; i >= 0 || j >= 0 || carry != 0; { if i >= 0 { carry += arr1[i] i-- } if j >= 0 { carry += arr2[j] j-- } ans = append([]int{carry & 1}, ans...) carry = -(carry >> 1) } for idx, num := range ans { // 去掉前导 0 if num != 0 { return ans[idx:] } } return []int{0} }循环条件：i >= 0 || j >= 0 || carry != 0
三个子条件缺一不可：
i >= 0：arr1尚未扫完；j >= 0：arr2尚未扫完；carry != 0：两个数组都扫完后，可能仍残留向更高位的进位，必须继续"吐出"。
由于负进制进位可能为负（-1），carry的取值在单轮内可能为-1、0、1、2等，因此用carry != 0而非carry > 0判断，这是负进制与正进制实现上最容易被忽略的差异点。
核心公式一：ans = append([]int{carry & 1}, ans...)
carry累加了本位两个数字与低位传来的进位，carry & 1取出其最低位作为当前位结果。使用& 1而非% 2，是因为 Go 中负数取模结果仍为负（如-1 % 2 == -1），而按位与& 1对-1同样得到1（-1 的二进制补码最低位为 1），恰好符合负进制的位值约定。每次把结果头插到ans前面，保证最终数组仍是 MSB 在前的顺序。
核心公式二：carry = -(carry >> 1)
这是整个算法最精妙的一行：把累加值右移一位（相当于除以 2 并向下取整），再取相反数，作为向更高一位传递的进位。
它的正确性正是前述三种情形证明的直接编码：
- 低位两个 1（连同可能传来的进位）产生进位时，
carry >> 1得到向 k 位的"权值 1"，取负后即为-1，对应"负进制的进位是 -1"这一结论； - 当
carry为负数（例如前一轮留下的 -1 与本位数字相加）时，>> 1与取负的组合依然把"2 的权值"正确地换算成(-2)的权值，保证数学推导与位运算严格一致。
去除前导零：负进位可能产生多余的 0
由于进位可能为 -1，模拟过程中可能在结果最高位之前产生多余的0，因此最后需要扫描一次结果数组，把前导零全部去掉：
for idx, num := range ans { // 去掉前导 0 if num != 0 { return ans[idx:] } } return []int{0}如果整条结果全为 0（例如0 + 0），循环结束后返回[]int{0}，符合题目"不含前导零"的格式约定（arr == [0]是允许的）。在 测试文件 中，{0} + {0}的期望输出正是[0]。
备选方案：十进制往返实现（仅供对照，不可 AC）
除正式解法外，仓库还保留了"十进制往返"的完整实现（addNegabinary1），由两个辅助函数组成，它们本身是负进制与十进制互转的标准写法，很有参考价值。
负进制转十进制：negabinaryToInt
func negabinaryToInt(arr []int) int { if len(arr) == 0 { return 0 } res := 0 for i := 0; i < len(arr)-1; i++ { if res == 0 { res += (-2) * arr[i] } else { res = res * (-2) res += (-2) * arr[i] } } return res + 1*arr[len(arr)-1] }其本质是霍纳法则（Horner's rule）的负基数版本：从最高位开始，每读入一位数字就把当前结果乘(-2)再加上该位的贡献，最后一位（LSB）权重为(-2)^0 = 1。空切片分支返回 0 的边界处理在 测试文件 中有专门覆盖。
十进制转负进制：intToNegabinary
func intToNegabinary(num int) []int { if num == 0 { return []int{0} } res := []int{} for num != 0 { remainder := num % (-2) num = num / (-2) if remainder < 0 { remainder += 2 num++ } res = append([]int{remainder}, res...) } return res }负数基数的整除取余有个陷阱：Go 中num % (-2)可能得到负余数，此时需要修正——余数加 2、商加 1，以保证余数落在合法的{0, 1}范围内。这是负进制与正进制转换唯一需要特判的地方。
需要再次强调：该方案仅用于对照与学习，在本题 1000 位长度的数据下会溢出int64导致 WA，正式提交必须使用解法一。
测试用例与验证方式
仓库为本题编写了完整的 单元测试，Test_Problem1073覆盖了：
- 超长数据组：两个长度约 600 位、1000 位量级的随机二进制数组，用于验证解法一在大数场景下不溢出、结果正确（这正是"十进制往返"方案会 WA 的那类用例，源码注释中提到的第 257 / 267 组测试即属此类）；
- 题目示例：
[1,1,1,1,1] + [1,0,1] == [1,0,0,0,0]（11 + 5 = 16）； - 边界用例：
{0} + {0} -> [0]、{0} + {1,1} -> [1,1]、{0} + {1,0,0,1} -> [1,0,0,1]、{0} + {1,0} -> [1,0]，验证含 0 操作数与"结果即另一操作数"的情况； - 覆盖率补丁：
negabinaryToInt([]int{})的空切片分支（对应源码len(arr) == 0的防御逻辑）。
若本机已安装 Go 工具链，可在仓库根目录按 gotest.sh 的方式运行全量测试并统计覆盖率：
go test -covermode=atomic -coverprofile=coverage.txt ./leetcode/...单独验证本题时，可直接进入对应目录执行：
go test -v -run Test_Problem1073 ./leetcode/1073.Adding-Two-Negabinary-Numbers/复杂度分析
- 时间复杂度：O(n)，其中 n 为两个数组中较长的长度。一次从低位到高位的扫描即完成全部加法，进位处理是常数时间，最后的去前导零扫描同样是 O(n)。
- 空间复杂度：O(n)，结果数组
ans的长度与输入规模同阶。
总结
LeetCode 1073 题的核心收获有三点：
- 进制转换并非必须经过十进制：当数据规模超出原生整数范围时，"直接在当前进制内模拟进位"往往比"中转十进制"更简洁、更可靠；
- 负进制的进位是 -1：
carry = -(carry >> 1)一行同时处理了正负进位，配合carry & 1取位，是负进制加法最优雅的编码方式； - 格式细节决定成败：负进位会带来多余的高位 0，必须扫描并去除前导零；
0 + 0时结果须为[0]以符合题目格式约定。
完整的题目说明、三种进位情形的数学证明与对照实现，均收录于 本题 README；可直接运行验证的源码与测试见 实现文件 与 测试文件。
【免费下载链接】LeetCode-Go✅ Solutions to LeetCode by Go, 100% test coverage, runtime beats 100% | LeetCode 题解项目地址: https://gitcode.com/GitHub_Trending/le/LeetCode-Go
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
