java 2ms solution with explanation
The basic idea is sum bit by bit. The key is how to process carry. There are five situations for the bit sum:\n1. sum = 0 -> carry = 0, result = 0\n2. sum = 1 -
The basic idea is sum bit by bit. The key is how to process carry. There are five situations for the bit sum:\n1. sum = 0 -> carry = 0, result = 0\n2. sum = 1 -> carry = 0, result = 1\n3. sum = 2 -> carry = -1, result = 0\n4. sum = 3 -> carry = -1, result = 1\n5. sum = -1 -> carry = 1, result = 1\n\nHere, ```carry``` will be added to the sum of next calculation and ```result``` is what we put on current bit. We can either enumerate all five situations or use bit manipulation:\n1. carry = -1 * (sum >> 1)\n2. result = sum & 1\n\nto calculate ```carry``` and ```result``` quickly.\n\n```\npublic int[] addNegabinary(int[] arr1, int[] arr2) {\n    int i1 = arr1.length - 1, i2 = arr2.length - 1, carry = 0;\n    List<Integer> resultList = new ArrayList<Integer>();\n\t\n\t// 1. calculate sum of arr1 and arr2\n    while (i1 >= 0 || i2 >= 0 || carry != 0) {\n        int n1 = i1 >= 0 ? arr1[i1--] : 0;\n        int n2 = i2 >= 0 ? arr2[i2--] : 0;\n        int sum = n1 + n2 + carry;\n\t\tint result = sum & 1;\n        carry = -1 * (sum >> 1) ;\n\t\tresultList.add(0, result);        \n    }\n\t\n\t// 2. remove leading zero\n    int beginIndex = 0;\n    while (beginIndex < resultList.size() && resultList.get(beginIndex) == 0)\n        beginIndex++;\n\t\t\n    if (beginIndex == resultList.size())\n        return new int[]{0};\n    int resultArray[] = new int[resultList.size() - beginIndex];\n    for (int i = 0; i < resultArray.length; i++)\n        resultArray[i] = resultList.get(i + beginIndex);\n    return resultArray;\n}\n```
['Bit Manipulation', 'Java']