C++ From Wikipedia
See Wikipedia\'s Negative Base Addition.\n\nWe start from the least signifficant bit, and do the binary summation as usual. However, our carry can have three st
See [Wikipedia\'s Negative Base Addition](https://en.wikipedia.org/wiki/Negative_base#Addition).\n\nWe start from the least signifficant bit, and do the binary summation as usual. However, our carry can have three states: -1, 0, and 1.\n\nIf the sum for the current bit is greater than 2, the carry becomes -1, not 1 as in the base 2 case. Because of that, our sum can become -1. In this case, the carry should be set to 1.\n```\nvector<int> addNegabinary(vector<int>& a1, vector<int>& a2) {\n  vector<int> res;\n  int bit = 0, carry = 0, sz = max(a1.size(), a2.size());\n  for (auto bit = 0; bit < sz || carry != 0; ++bit) {\n    auto b1 = bit < a1.size() ? a1[a1.size() - bit - 1] : 0;\n    auto b2 = bit < a2.size() ? a2[a2.size() - bit - 1] : 0;\n    auto sum = b1 + b2 + carry;\n    res.push_back(abs(sum) % 2); \n    carry = sum < 0 ? 1 : sum > 1 ? -1 : 0;\n  }\n  while (res.size() > 1 && res.back() == 0) res.pop_back();\n  reverse(begin(res), end(res));\n  return res;\n}\n```
[]