Python | O ( log N ) solution | Detailed Addition Kernel
Python | O ( log N ) solution | Detailed Addition Kernel\n\nThe code below has a dedicated Addition Kernel, which simulates the process of converting an integer
**Python | O ( log N ) solution | Detailed Addition Kernel**\n\nThe code below has a dedicated Addition Kernel, which simulates the process of converting an integer (N) to its representation in "-2" base in O( log N ) time.\n\nThe code makes a lot of sense. It first converts the number N into a standard binary representation, and then it maps these binary powers into their "-2" base counterpart. (Multiples of 4 are identical, other numbers map as 8 = -8 + 16 or x = -x + 2*x).\n\nSince many overlaps occur while converting the binary powers, the Addition Kernel handles the additional "carries" obtained, such that the properties of base "-2" numbers are fulfilled. I hope the code is helpful. Cheers,\n\n```\ndef makebin(N):\n    while N:\n        yield N & 1\n        N >>= 1\n#\nclass Solution:\n    def baseNeg2(self, N: int) -> str:\n        if not N:\n            return "0"\n        #\n        b = [ *makebin(N) ]\n\t\t#\n        # Convert to base -2 binary (sum overlaps are fixed later)\n        res = [0 for _ in range(len(b)+1)]\n        for i,x in enumerate(b):\n            if x:\n                res[i] += 1 # if "i" is even, everything is fine (1,4,8,16, etc.)\n                if i%2:\n                    res[i+1] += 1 # if "i" was odd, we need to add one to the next power\n        # ---------------------------------\n        #        Addition Kernel\n\t\t# ---------------------------------\n        i,L = 0, len(res)\n        while i<L:\n            print(res)\n            x = res[i]\n            if x<2:\n                i += 1 \n                continue      # everything was fine\n            res[i] -= 2       # delete 2, and try to scalate issue\n            while not i+2<L:  # ensure we have enough space\n                res.append(0)\n                L += 1\n            if res[i+1]:      \n                res[i+1] -= 1 # if the next power is filled, we can take cancel them out\n            else:\n                res[i+1] += 1 # if the next power is empty, we can represent the number appropriately by adding to[i+1,i+2] (E.g., -16 = 16 - 32 or 32 = -32 + 64)\n                res[i+2] += 1\n        while res and not res[-1]:\n            res.pop() # Pop unused space\n        return \'\'.join(map(str,res))[::-1]\n```
['Python', 'Python3']