C++ O(N) Time with Explanation (carry = -(sum >> 1))
See more code in my repo LeetCode\n\nWhen adding two numbers in base 2 I use a variable carry to store the carryover.\n\nAssume we are adding two bits a, b and 
*See more code in my repo [LeetCode](https://github.com/lzl124631x/LeetCode)*\n\nWhen adding two numbers in base `2` I use a variable `carry` to store the carryover.\n\nAssume we are adding two bits `a`, `b` and `carry`. The `sum` can be `0, 1, 2, 3`, and the leftover bit value is `sum % 2` and the new value of `carry` is `sum / 2`.\n\n\nLet\'s try the same approach for this problem.\n\nAssume the current bit represents `k = (-2)^n`, (`n >= 0`).\n\n* Consider `carry = 0`, `sum` can be `0, 1, 2`.\n  * When `sum = 0` or `1`, `leftover = sum`, `carry = 0`.\n  * When `sum = 2`, the value is `2k = -1 * (-2k)`, so it\'s the same as `leftover = 1, carry = -1`\n* Consider `carry = -1`, `sum` can be `-1, 0, 1`.\n  * For the new case `sum = -1`, the value is `-k = -2k + k`, so it\'s the same as `leftover = 1, carry = 1`.\n* Consider `carry = 1`, `sum` can be `1, 2, 3`.\n  * For the new case `sum = 3`, the value is `3k = -1 * (-2k) + k`, so it\'s the same as `leftover = 1, carry = -1`.\n\nNow we\'ve considerred all cases. In sum:\n\nsum|leftover|carry|\n---|---|---\n-1|1|1\n0|0|0\n1|1|0\n2|0|-1\n3|1|-1\n\nThe pattern is:\n```\nleftover = (sum + 2) % 2\ncarry = 1 - (sum + 2) / 2\n```\nOr\n```\nleftover = sum & 1\ncarry = -(sum >> 1)\n```\n\n```cpp\n// OJ: https://leetcode.com/problems/adding-two-negabinary-numbers/\n// Author: github.com/lzl124631x\n// Time: O(N)\n// Space: O(N)\nclass Solution {\npublic:\n    vector<int> addNegabinary(vector<int>& A, vector<int>& B) {\n        vector<int> ans;\n        for (int i = A.size() - 1, j = B.size() - 1, carry = 0; i >= 0 || j >= 0 || carry;) {\n            if (i >= 0) carry += A[i--];\n            if (j >= 0) carry += B[j--];\n            ans.push_back(carry & 1);\n            carry = -(carry >> 1);\n        }\n        while (ans.size() > 1 && ans.back() == 0) ans.pop_back();\n        reverse(ans.begin(), ans.end());\n        return ans;\n    }\n};\n```
[]