[C++] with detailed explanation, easy to understand
There are four scenarios, a+b=0/1/2/3/4, \nafter summing up the current digit, carry is set to second carry while second carry is set to 0, this is like shiftin
There are four scenarios, a+b=0/1/2/3/4, \nafter summing up the current digit, carry is set to second carry while second carry is set to 0, this is like shifting the carry\n* 0/1: there is no need to update carry, \n* 2/3: their secondCarry is set to 1 while carry is increased by 1, since 2*(-2)^i = (-2)^(i+1) + (-2)^(i+2) = -2*(-2)^i+4*(-2)^i\n* 4: secondCarry is set to 1\n\nOne special case to notice is that when secondCarry=1 and carry=2, they are cancel to 0\n\n```\nclass Solution {\npublic:\n    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {\n        vector<int> res;\n        int carry=0; // the carry to the next digit,\n        int secondCarry=0; // the carry to the digit after next digit.\n        int i=arr1.size()-1,j=arr2.size()-1;\n        \n        auto helper = [&](int cur) {\n            carry=secondCarry;\n            secondCarry=0;\n            if (cur>=2) {\n                if (cur<4) carry++; // case 2,3\n                if (carry == 2) {\n                    carry = 0; // special case\n                } else {\n                    secondCarry = 1; // case 2,3,4\n                }\n            }\n            res.push_back(cur%2);\n        };\n        \n        for (;i>=0 && j>=0; i--,j--) helper(arr1[i]+arr2[j]+carry); // calc the share digits\n        while (i>=0) helper(arr1[i--]+carry); // calc the remain digit of arr1\n        while (j>=0) helper(arr2[j--]+carry); // calc the remain digit of arr2\n        while (secondCarry!=0 || carry!=0) helper(carry); // calc the remain carry\n        \n\t\t// remove the leading zero\n        while (res.size()>=2) {\n            if (res.back()==0) res.pop_back();\n            else break;\n        }\n        reverse(res.begin(),res.end());\n        \n        return res;\n    }\n};
[]