1073. Adding Two Negabinary Numbers

题解

负二进制两个数相加，有两个地方需要注意：

穷举计算出负二进制的进位法则，双进位。

1073. Adding Two Negabinary Numbers - 图1

解决无穷循环的问题。

我们用carry1记录正常进位，carry2记录跳跃进位，如果连续有两位双进位的情况，会导致出现carry1=2，carry2=1的情况。根据进位法则， carry1=2表示需要继续进位，会无限出现carry1=2，carry2=1的情况。由于我们是有限数相加，不会出现无限循环的情况，因此我们来探讨carry1=2和carry2=1是否可以抵消。
由下面的数学公式可知，carry1=2可以和carry2=1抵消，因此加上特殊判断来解决无限循环问题。

1073. Adding Two Negabinary Numbers - 图4

代码

class Solution {
public:
    vector<int> addNegabinary(vector<int>& a, vector<int>& b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        vector<int> c;
        int carry1 = 0, carry2 = 0;
        for (int i = 0; i < a.size() || i < b.size() || carry1 || carry2; i ++) {
            if (carry1 == 2 && carry2 == 1) {
                carry1 = 0;
                carry2 = 0;
            }
            int res = carry1;
            carry1 = carry2;
            carry2 = 0;
            if (i < a.size()) {
                res += a[i];
            }
            if (i < b.size()) {
                res += b[i];
            }
            c.push_back(res % 2);
            if (res >= 2) {
                carry1 += 1;
                carry2 += 1;
            }
        }
        while (c.size() > 1 && c.back() == 0) {
            c.pop_back();
        }
        reverse(c.begin(), c.end());
        return c;
    }
};