LeetCode 1073. 负二进制数相加

2026-01-13 HGNULB 约 5 分钟

文章信息 6 个分类 · 2 个标签

分类

LeetCode CodeTop 中等 未解决 2-5 字节

标签

数组 数学

题目描述

✅ 1073. 负二进制数相加

题意分析

两个数组按从高位到低位保存负二进制数，每位只能为 0 或 1，第 k 位的权重是 $(-2)^k$。求两数之和并按相同格式返回，不能有多余前导零；结果为零时返回一位 0。

解法：进位模拟

核心思路

[!blue]

仍然从最低位开始逐位相加，用两个下标取当前输入位，缺少的一位按 0 处理，再加上低一位传来的 carry，得到当前总量 sum。区别只在于，高一位的权重是当前位的 -2 倍，而不是 2 倍。

设当前结果位为 bit、传给高一位的新进位为 nextCarry，必须满足 sum = bit - 2 * nextCarry。让 bit 取与 sum 同奇偶的 0 或 1，就能得到整数进位 nextCarry = -(sum - bit) / 2，每一步都保持数值不变。

进位可能为负。用 bit = sum & 1 可在 sum 为负数时仍得到合法的 0 或 1；直接取 % 2 则可能得到 -1。进位初始为 0，递推中始终属于 -1、0、1，所以 sum 只可能在 -1 到 3 之间。输入耗尽后，进位 1 下一轮变成 0，进位 -1 最多经过 -1 到 1 再到 0，两轮就能收尾。

结果按低位到高位追加。完成进位后，列表末尾才是高位，先从末尾删掉多余的 0，再反转成题目要求的高位在前顺序；删除时至少保留一位。

解题步骤

1. 两个下标从各自数组末尾开始，初始化 carry = 0 和结果列表 res。
2. 只要任一输入还有位，或 carry != 0，就将当前输入位与进位相加。
3. 把 bit = sum & 1 追加到 res，再令 carry = -(sum - bit) / 2。
4. 当结果长度大于 1 且末位为 0 时，删除末位，去掉高位的多余零。
5. 反转结果，返回从高位到低位排列的数组。

代码实现

class Solution {
    public int[] addNegabinary(int[] arr1, int[] arr2) {
        int i = arr1.length - 1;
        int j = arr2.length - 1;
        int carry = 0;

        List<Integer> res = new ArrayList<>();

        while (i >= 0 || j >= 0 || carry != 0) {
            int sum = carry;

            if (i >= 0) {
                sum += arr1[i--];
            }

            if (j >= 0) {
                sum += arr2[j--];
            }

            // 负总量也要取合法的零或一，不能直接用负余数。
            int bit = sum & 1;

            res.add(bit);
            // 高一位权重是负二倍，移到高位的量因此带负号。
            carry = -(sum - bit) / 2;
        }

        // 只去掉多余高位零，零值仍保留一位。
        while (res.size() > 1 && res.get(res.size() - 1) == 0) {
            res.remove(res.size() - 1);
        }

        int[] answer = new int[res.size()];

        for (int k = 0; k < res.size(); k++) {
            answer[k] = res.get(res.size() - 1 - k);
        }

        return answer;
    }
}

func addNegabinary(arr1 []int, arr2 []int) []int {
    i := len(arr1) - 1
    j := len(arr2) - 1
    carry := 0

    res := make([]int, 0)

    for i >= 0 || j >= 0 || carry != 0 {
        sum := carry
        if i >= 0 {
            sum += arr1[i]
            i--
        }
        if j >= 0 {
            sum += arr2[j]
            j--
        }

        // 负总量也要取合法的零或一，不能直接用负余数。
        bit := sum & 1
        res = append(res, bit)
        // 高一位权重是负二倍，移到高位的量因此带负号。
        carry = -(sum - bit) / 2
    }

    // 只去掉多余高位零，零值仍保留一位。
    for len(res) > 1 && res[len(res)-1] == 0 {
        res = res[:len(res)-1]
    }

    for l, r := 0, len(res)-1; l < r; l, r = l+1, r-1 {
        res[l], res[r] = res[r], res[l]
    }

    return res
}

复杂度分析

• 时间复杂度：$O(\max(m,n))$，其中 m、n 是两个输入数组的长度；逐位相加后最多再处理两轮进位，去零和反转也为线性。
• 空间复杂度：结果需要 $O(\max(m,n))$ 空间；不计返回值时，Java 的中间列表仍占 $O(\max(m,n))$，Go 原地反转结果缓冲，额外空间为 $O(1)$。

关键点总结

[!green]

• 进位可以为负，不能套普通二进制加法。
• 循环还需处理输入耗尽后的非零进位。

易错点总结

[!yellow]

• sum 对 2 取余可能产生 -1，违反每位只能为 0 或 1 的要求。
• 进位漏负号会把结果当正二进制处理。
• 清掉全部零会返回空数组，而零应有一位表示。

相似题目

题目	难度	关联与区别
67. 二进制求和	简单	逐位加法框架相同，但本题基数为-2，进位可能为负，不能照搬普通二进制进位。

转载与许可

作者 HGNULB

链接 https://hgnulb.github.io/blog/2026/46603774

许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！