Java Solution With Explanation
Idea\n\n\n\n\nRef: https://en.wikipedia.org/wiki/Negative_base#Addition\n\nFirst observe the pattern,  \n Carry = -sum/2 mathematically except for sum == -1.\nW
**Idea**\n\n![image](https://assets.leetcode.com/users/naveenkothamasu/image_1569181686.png)\n\n\n*Ref*: https://en.wikipedia.org/wiki/Negative_base#Addition\n\nFirst observe the pattern,  \n* Carry = -sum/2 mathematically except for sum == -1.\nWe can directly do this with special case when `sum == -1`. \nSince this is divison by 2<sup>k</sup> where k=1, we can right shift k times too. One observation here is we do not need special case for `sum == -1`. Why? Java right shift operator `>>`  is actually the Signed right shift operator. So for sum = -1, we are doing \n`11 >> 1` which is agian `11` which is what we want.\n\n* Bit is the last bit that can be obtained with modulo 2.\nWe can do `(int)Math.abs(c) % 2` to get the last bit. We need to take absolute value here in Java because Java remainders can be negative and division is truncated to zero. Remember, modulo is never negative (those are the digits we use to represent the output so `-` sign shouldn\'t be present).\n\nWe can also use the observation that remainder is just the last k-bits when doing divison by 2<sup>k</sup>. So we just need to `&` with k 1\'s i.e. `c & 1`\n*Ref* https://stackoverflow.com/questions/15457893/java-right-shift-on-negative-number\nhttps://stackoverflow.com/questions/5385024/mod-in-java-produces-negative-numbers\n\n```\npublic int[] addNegabinary(int[] a1, int[] a2) {\n        Stack<Integer> s = new Stack<>();\n        int i=a1.length-1, j = a2.length-1, c = 0;\n        while(i >= 0 || j >= 0 || c != 0){\n            if(i >= 0)\n                c += a1[i--];\n            if(j >= 0)\n                c += a2[j--];\n            //s.push((int)Math.abs(c) % 2);\n            s.push(c & 1);\n            //c = c < 0 ? 1 : c <= 1 ? 0 : -1;\n            c = -(c >> 1);\n        }\n        while(!s.isEmpty() && s.peek() == 0)\n            s.pop();\n        int[] res = new int[s.size()];\n        i=0;\n        while(!s.isEmpty())\n            res[i++] = s.pop();\n        return res.length == 0 ? new int[1] : res;\n    }\n}\n```
[]