Given a number N, return a string consisting of "0"s and "1"s that represents its value in base -2 (negative two).
The returned string must have no leading zeroes, unless the string is "0".
 

Example 1:
Input: 2
Output: "110"
Explantion: (-2) ^ 2 + (-2) ^ 1 = 2


Example 2:
Input: 3
Output: "111"
Explantion: (-2) ^ 2 + (-2) ^ 1 + (-2) ^ 0 = 3


Example 3:
Input: 4
Output: "100"
Explantion: (-2) ^ 2 = 4

 
Note:

0 <= N <= 10^9

Difficulty: interview

Starter code:

class Solution:
    def baseNeg2(self, N: int) -> str:
        

Solutions:
class Solution:
    def baseNeg2(self, N: int) -> str:
        # res = []
        # x = N
        # while x:
        #     res.append(x & 1)
        #     x = -(x >> 1)
        # return \"\".join(map(str, res[::-1] or [0]))
        
        neg = [1 << i for i in range(1, 33, 2)]
        for mask in neg:
            if N & mask: N += mask*2
        return bin(N)[2:]

class Solution:
    def baseNeg2(self, N):
        res = []
        while N != 0:
            m = N %(-2)
            if m == -1:
                m = 1
            N = (N-m) // (-2)
            res.append(str(m))
            
        return ''.join(res[::-1]) or '0'

class Solution:
    def baseNeg2(self, N: int) -> str:
        return str(bin((0xAAAAAAAAAAAAAAAA+N)^0xAAAAAAAAAAAAAAAA))[2:]