[C++] Observation that (1 + 1) == (4 + -2) and (-2 + -2) == (-8 + 4)
(1 + 1) == (4 + -2)  \n2. (-2 + -2) == (-8 + 4)\n3. 001 + 001 == 110\n4. Add carry for bit + 1 and bit + 2.\n\nJust do a normal bit addition for base 2. But if 
1. `(1 + 1) == (4 + -2)`  \n2. `(-2 + -2) == (-8 + 4)`\n3. `001` + `001` == `110`\n4. Add carry for bit + 1 and bit + 2.\n\nJust do a normal bit addition for base 2. But if there is a carry, carry applies for ith + 1 and ith + 2 position.\n\n```\nclass Solution {\npublic:\n    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {\n        /*\n        carry lhs rhs\n        0     0   0     0\n        0     0   1     1\n        0     1   0     1\n        0     1   1     0 + (1 + 1)\n        1     0   0     1\n        1     0   1     0 + (1 + 1)\n        1     1   0     0 + (1 + 1)\n        1     1   1     1 + (1 + 1)\n        */\n        int n = arr1.size(), m = arr2.size();\n        int lhs = n - 1, rhs = m - 1;\n        vector<int> ans(max(n,m)+2);\n        for (int i = ans.size() - 1; i >= 0 && lhs >= 0; --i) {\n            ans[i] += arr1[lhs--];\n        }\n        for (int i = ans.size() - 1; i >= 0 && rhs >= 0; --i) {\n            ans[i] += arr2[rhs--];\n        }\n        for (int i = ans.size() - 1; i >= 0; --i) {\n            int newval = ans[i] % 2;\n            int carry = ans[i] / 2;\n            if (i - 1 >= 0) ans[i-1] += carry;\n            if (i - 2 >= 0) ans[i-2] += carry; \n            ans[i] = newval;\n        }\n\t\t// Remove leading zeros\n        int i = 0;\n        for (; i < ans.size() && ans[i] != 1; ++i) {\n            \n        }\n        int diff = i;\n        vector<int> cans(ans.size() - i);\n        for (; i < ans.size(); ++i) {\n            cans[i - diff] = ans[i];\n        }\n        if (cans.size() == 0) return {0};\n        return cans;\n        \n    }\n};\n```
['Bit Manipulation']