class Solution(object):
    def addNegabinary(self, arr1, arr2):
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: List[int]
        """

        def convert_2(x):
            res = []
            if not x:
                return [0]
            while x:
                res.append(x & 1)
                x = -(x >> 1)
            return res[::-1]

        def convert_10(arr):
            res = 0
            for i in xrange(len(arr)):
                res += arr[i] * (-2) ** (len(arr) - i - 1)

            return res

        s = convert_10(arr1) + convert_10(arr2)
        return convert_2(s)


if __name__ == '__main__':
    print Solution().addNegabinary([0], [0])
    print Solution().addNegabinary([1, 1, 1, 1, 1], [1, 0, 1])
