Problem:
 Score : 300 points    Problem Statement Given an integer N , find the base -2 representation of N .  Here, S is the base -2 representation of N when the following are all satisfied:   S is a string consisting of 0 and 1 .  Unless S =  0 , the initial character of S is 1 .  Let S = S_k S_{k-1} ... S_0 , then S_0 \times (-2)^0 + S_1 \times (-2)^1 + ... + S_k \times (-2)^k = N .   It can be proved that, for any integer M , the base -2 representation of M is uniquely determined.      Constraints  Every value in input is integer.  -10^9 \leq N \leq 10^9         Input Input is given from Standard Input in the following format:  N       Output Print the base -2 representation of N .        Sample Input 1 -9      Sample Output 1 1011  As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9 , 1011 is the base -2 representation of -9 .       Sample Input 2 123456789      Sample Output 2 11000101011001101110100010101       Sample Input 3 0      Sample Output 3 0

Solution (Python):
n = int(input())
if n ==0:
    print(0)
else:
    f = 1
    res = ""
    while n != 0:
        if n% (2**f) != 0:
            res = "1"+res
            n -= (-2)**(f-1)
        else:
            res = "0"+res
        f += 1
    print(res)

Solution (Python):
lmax = [0]
lmin = [0]
tmin = 0
tmax = 0
for i in range(0,40):
    if i % 2 == 1:
        tmin -= 2**i
    else:
        tmax += 2**i
    lmax.append(tmax)
    lmin.append(tmin)

def main():
    n = int(input())

    print(int(base(n,35)))

def base(n,a):
    if a == 0:
        if n == 1:
            return '1'
        else:
            return "0"
    if n >lmax[a] or n <lmin[a]:
        return '1'+base(n-(-2)**a,a-1)
    else:
        return '0'+base(n,a-1)

main()

Solution (Python):
N = int(input())
res = []
while N != 0:
    if N % -2 != 0:
        res.append("1")
    else:
        res.append("0")
    
    if N == 1:
        break

    if N % -2 != 0:
        N -= 1
    N //= -2

if N != 0:
    print("".join(reversed(res)))
else:
    print(0)

Solution (Python):
import math
import copy
import sys
import fractions
import numpy as np
from functools import reduce



def getInputInt():
    inputNum = int(input())
    return inputNum

def getInputListInt():
    outputoData = []
    inputData = input().split()
    outputData = [int(n) for n in inputData]

    return outputData

def getSomeInputInt(n):
    outputDataList = []
    for i in range(n):
        inputData = int(input())
        outputDataList.append(inputData)

    return outputDataList

def getSomeInputListInt(n):
    inputDataList = []
    outputDataList = []
    for i in range(n):
        inputData = input().split()
        inputDataList = [int(n) for n in inputData]
        outputDataList.append(inputDataList)

    return outputDataList




n = getInputInt()

ans = 0

flg = True
i=0
while(flg):
    tmp = pow(-2,i+1)
    if n % tmp != 0:
        ans+=pow(10,i)
        n -= pow(-2,i)

    if n==0:
        flg=False
    i+=1

print(ans)

Solution (Python):
n = int(input())
if n==0:
    print(0)
    exit()
x = n
ans = []
while x!=1:
    if x%2==0:
        ans.append("0")
    else:
        ans.append("1")
        x -= 1
    x = x//(-2)
ans.append("1")
print("".join(ans[::-1]))

Solution (Python):
N = int(input())

if N == 0:
    print(0)
    exit()

ans = []
x = N

while x != 1:
    if x % 2 == 0:
        ans.append('0')
    else:
        ans.append('1')
        x -= 1
    x /= -2
ans.append('1')

r = "".join(ans[::-1])
print(r)

Solution (Python):
N = int(input())

if N == 0:
    print(0)
    exit()

ans = []
x = N

while x != 1:
    if x % 2 == 0:
        ans.append('0')
    else:
        ans.append('1')
        x -= 1
    x /= -2
ans.append('1')

r = "".join(ans[::-1])
print(r)

Solution (Python):
n = int(input())
if n == 0:
    print(0)
else:
    m, ans = n, ''
    while m:
        m, r = divmod(m, 2)
        m, ans = -m, '{}{}'.format(r, ans) 
    print(ans)

Solution (Python):
import sys
inputs = sys.stdin.readlines()

n = int(inputs[0])
if n == 0:
    print(0)
else:
    def f(x):
        q, r = divmod(x, -2)
        return (q+1, 1) if r == -1 else (q, r)

    m = n
    ans = ''
    while m:
        m, r = f(m)
        ans = str(r) + ans
    print(ans)

Solution (Python):
n = int(input())

if n == 0:
    print(0)
else:
    p = 1
    ans_list = []
    while n != 0:
        ans_list.append(str(n%2))
        n = - (n//2)
    ans_list.reverse()
    print("".join(ans_list))

Solution (Python):
N=int(input())
s=''
for i in range(1,35):
    if N%(2**i)==0:
        s='0'+s
    else:
        s='1'+s
    N-=N%-((-2)**i)
    if N==0:
        break
print(s)

Solution (Python):
N = int(input())

if N == 0 :
    print(0)
else :
    ret = ''
    while N != 1 :
        ret += str(N % 2)
        N = -(N // 2)
        
    print('1' + ret[::-1])

Solution (Python):
import math

N = int(input())


def max_negative2(d):
    if d == 1:
        return 1
    elif d%2 == 1:
        return int((1-4**(math.ceil(d/2)))/(1-4))
    else:
        return (-2)**(d-1) + int((1-4**(math.ceil(d/2)))/(1-4))

def min_negative2(d):
    if d == 1:
        return 0
    elif d%2 == 1:
        return (-2)**(d-1) + int((-2)*(1-4**(d//2))/(1-4))
    else:
        return int((-2)*(1-4**(d//2))/(1-4))


def top_bit_flag(n,d):
    if n == 0 and d == 1:
        return False
    else:
        return True if min_negative2(d) <= n <= max_negative2(d) else False



S = ""
n = N
for d in reversed(range(1,33)):
    if top_bit_flag(n,d):
        S += "1"
        n -= (-2)**(d-1)
    else:
        S += "0"

print(int(S))

Solution (Python):
n=int(input())
if n==0:
    print(0)
    exit()
ans=''
i=1
k=n
while k!=0:
    if k%(2**i)!=0:
        ans='1'+ans
        k-=(-2)**(i-1)
    else:
        ans='0'+ans
    i+=1
print(ans)

Solution (Python):
N = int(input())

if N == 0:
    print(0)

ans = ''
while N != 0:
    if N%2 == 1:
        ans += '1'
        N -= 1
    else:
        ans += '0'
    N //= -2

print(ans[::-1])

Solution (Python):
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string



def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
inf=float('inf')



show_flg=False
show_flg=True

n=I()
ans=0
d=0

while n!=0:
    k=2**(d+1)
    if n%k!=0:
        ans+=1*10**d
        n-=(-2)**d
    d+=1
    
print(ans)

Solution (Python):
n = int(input())
x = ""
while n != 0:
    x = str(n % 2) + x
    n = -(n//2)
if x == "":
    print(0)
else:
    print(x)

Solution (Python):
N = int(input())

if N == 0:
  print(0)
  exit()

ans = ''
while(N != 0):
  r = N % 2
  ans += str(r)
  N = (N-r) // (-2)
  
print(''.join(reversed(ans)))

Solution (Python):
s = int(input())
p =1
ans = []
while True:
    mod = s%(4**p)
    mods_sum = sum([ans[x]*((-2)**x)for x in range(len(ans))])%(4**p)
    now_mod = (mod-mods_sum)%(4**p)
    for a,b in zip([1,1,0,0],[0,1,0,1]):
        if (a-2*b)*(4**(p-1))%(4**p) == now_mod:
            ans.append(a)
            ans.append(b)
    total = 0
    for i,digit in enumerate(ans):
        total += digit*((-2)**i)
    if total == s:
        break
    p +=1
ans.reverse()
ans = list(map(str,ans))
ans =int(''.join(ans))
print(ans)

Solution (Python):
from sys import stdin

N = int(stdin.readline().rstrip())
ans = ''

if N == 0:
    print(0)
    exit()

while N != 0:
    if N % 2 == 1:
        N -= 1
        ans += '1'
    else:
        ans += '0'
    N //= -2

print(ans[::-1])

Solution (Python):
n = int(input())
if n == 0:
    print(0)
else:
    s = []
    while n != 0:
        p = n % 2
        s.append(p)
        n -= p
        n *= -1
        n >>= 1

    print(''.join(map(str, reversed(s))))

Solution (Python):
n=int(input())
if n==0:
	print('0')
else:
	L=[]
	while n!=0:
		if n>0:
			r=n%2
			n=-(n//2)
		else:
			r=(-n)%2
			n=(-n)//2
			if r==1:
				n+=1
		L.append(r)
	print(''.join(map(str,L[::-1])))

Solution (Python):
def to_m2(n):
    if n == 0:
        return '0'

    digits = []
    base = 1
    while n != 0:
        if n % (base * 2) == 0:
            digits.append(0)
        else:
            digits.append(1)
            n -= base
        base *= -2
    return ''.join(map(str, reversed(digits)))


print(to_m2(int(input())))

Solution (Python):
N=int(input())
ans=[]
if N==0:ans.append(0)
while N!=0:
    x=N%2
    N=(N-x)//-2
    ans.append(x)
ans.reverse()
print(*ans,sep='')

Solution (Python):
N = int(input())
ans = ""
while True:
    ans = str(abs(N % -2)) + ans
    N += N % -2
    N = N // -2
    if N == 0:
        break
print(ans)

Solution (Python):
N = int(input())

ans = ''
while N != 0:
    if N % 2 == 0:
        ans = '0' + ans
        N //= (-2)
    else:
        ans = '1' + ans
        N = (N-1)//(-2)

if ans == '':
    print(0)
else:
    print(ans)

Solution (Python):
N = int(input())

binary_s = ''

while N != 0:
    mod = N % 2
    binary_s = str(mod) + binary_s
    N = -(N // 2)

print(binary_s if binary_s != '' else 0)

Solution (Python):
n = int(input())
s = ''
while n != 0:
    div, mod = divmod(n, 2)
    s = str(mod)+s
    n = -div
print(s or 0)

Solution (Python):
N = int(input())
ans = []
if N == 0:
    print(0)
    exit()
for i in range(10**10):
    if N == 0:
        break
    if N%2 == 1:
        ans.append("1")
        N -= (-1)**(i)
    else:
        ans.append('0')
    N = N // 2

print(''.join(ans[::-1]))

Solution (Python):
n = int(input())

string = ""

for i in range(10**10):
    if n == 0:
        break
    if n % 2 == 1:
        string = "1" + string
        n -= (-1)**(i)
    else:
        string = "0" + string
    n = n // 2

print(string if string != "" else 0)

Solution (Python):
N = int(input())
ans = ""
i = 0
while N != 0:
	if N % (2 ** (i + 1)) == 0:
		ans += "0"
	else:
		ans += "1"
		N -= (-2) ** i
	i += 1
if ans == "":
	print(0)
else:
	print(ans[::-1])

Solution (Python):
import sys
input = sys.stdin.readline

def main():
    N = int(input())
    ans = ""
    while N != 0:
        if N % 2 != 0:
            N -= 1
            ans = "1" + ans
        else:
            ans = "0" + ans
        N //= -2
    if ans == "":
        ans = "0"
    
    print(ans)

if __name__ == "__main__":
    main()

Solution (Python):
N = int(input())

ans = ""

while N != 0:
    if N % 2 != 0:
        N -= 1
        ans = "1" + ans
    else:
        ans = "0" + ans
    N /= -2

if ans == "":
    ans = "0"

print(ans)

Solution (Python):
def is_even(n):
    if n % 2 == 0:
        return True
    else:
        return False

def mainas_number():
    N = int(input())

    k =[]
    if N == 0:
        print(0)
        exit()

    if is_even(N):
        k.append(0)
    else:
        N -= 1
        k.append(1)

    for i in range(1,100):
        if (N // (-2)**i) % 2 == 1:
            N -= (-2)**i
            k.append(1)

        else:
            k.append(0)

        if N == 0:
            break

    ans = ""
    for c in k[::-1]:
        ans += str(c)
    print(ans)
    
if __name__ == "__main__":
    mainas_number()

Solution (Python):

import math

N = int(input().split()[0])
s = ""

for i in range(math.ceil(math.log2(10 ** 10)) + 1):
    s = str(N % 2) + s
    N = -(N // 2)

ans = s.lstrip("0")
ans = "0" if ans == "" else ans
print(ans)

Solution (Python):
N = int(input())
if N==0:
  print(0)
  exit()
k=[]
if N%2==1:
  N = N-1
  k.append(1)
else:
  k.append(0)
for i in range(1,50):
  if (N//(-2)**i)%2==1:
    N -=(-2)**i 
    k.append(1)
  else:
    k.append(0)
  if N==0:
    break
for i in range(len(k)-1,-1,-1):
  print(k[i],end="")

"""
for bit in range(1<<30):
  ans = 0
  an = 0
  for i in range(30):
    if bit&(1<<i):
      an += k[i]
      ans += 1<<i
  if an==N:
    ans =  format(ans, 'b')
    print(ans)
    exit()
"""

Solution (Python):
n=int(input())
if n!=0:
    string="<=Started"

    while n!=1:
        if abs(n)%2==0:
            string="0"+string
            n=int(n/(-2))
        else:
            string="1"+string
            n=int((n-1)/(-2))
    base2="1"+string
    wanted=base2[:-9]
    print(int(wanted))
if n==0:
    print(0)

Solution (Python):
n=int(input())
s=""
while True:
  if n%2==1:
    n-=1
    s="1"+s
  else:
    s="0"+s
  n//=-2
  if n==0:
    print(s)
    break

Solution (Python):
N = int(input())

if N == 0:
    print(0)
def f(N):
    if N == 0:
        return ''
    if N % 2 == 0:
        return f(N//(-2)) + '0'
    else:
        return f((N-1)//(-2)) + '1'

answer = f(N)
print(answer)

Solution (Python):
N=int(input())
ans=""
k=1
s=[]
while N!=0:
    if N%(k*(-2))!=0:
        s.append("1")
        N-=k
    else:
        s.append("0")
    k*=-2

for i in range(len(s)):
    ans+=s[len(s)-1-i]

if ans=="":
    ans+="0"
print(ans)

Solution (Python):
n=int(input())
a="";k=1
while n:
	t=k;k*=-2
	if n%k:n-=t;a+="1"
	else:a+="0"
print(a[::-1]or 0)

Solution (Python):
n=int(input())
ans=""
k=1
if n==0:
	ans="0"
while n:
	t=k
	k*=-2
	if n%k:
		n-=t
		ans+="1"
	else:
		ans+="0"
print(ans[::-1])

Solution (Python):
n = int(input())

if n == 0:
    print(0)
else:
    s = ''
    while n != 0:
        if n % 2 == 0:
            s = '0' + s
        else:
            s = '1' + s
        n = -(n // 2)
    print(s)

Solution (Python):
n = int(input())

if n == 0:
    print(0)
else:
    s = ''
    while n != 0:
        if n % 2 == 0:
            s = '0' + s
        else:
            s = '1' + s
            n -= 1
        n //= -2
    print(s)

Solution (Python):
n = int(input())

m = abs(n)
res = [0] * 100
i = 0
while m > 0:
    res[i] = m % 2
    i += 1
    m //= 2
for i in range(len(res) - 1):
    if i % 2 == int(n >= 0) and res[i] == 1:
        res[i + 1] += 1
    elif res[i] == 2:
        res[i] = 0
        res[i + 1] += 1

s = ''
started = False
for x in res[::-1]:
    if not started and x == 1:
        started = True
    if started:
        s += str(x)
if len(s) == 0:
    s = '0'
print(s)

Solution (Python):
S = int(input())
if S == 0:
  print(0)
  exit()
x = ""
while abs(S)>0:
  if abs(S) % 2 == 1:
    x += '1'
    S -=1
  else:
    x += '0'
  S = S //(-2)

x = x[::-1]
print(x)

Solution (Python):

n = int(input())
if n == 0:
    print(0)
else:
    s = ""
    while n != 0:
        if n%2 != 0:
            s = '1'+s
            n -= 1
        else:
            s = '0'+s
        n //= -2
    print(s)

Solution (Python):
def func(n,s=''):
    while True:
        if n == 1:
            break
        elif n == 0:
            break
        div = -(-n//-2)
        mod = n - (-2)*div
        n = div
        s = str(mod) + s
    return '1' + s

if __name__ == '__main__':
    n = int(input())
    if n == 1:
        print(1)
        exit()
    elif n == 0:
        print(0)
        exit()
    print(func(n))

Solution (Python):
import sys
input=sys.stdin.readline

def main():
    N = int(input())
    if N == 0:
        print("0")
        return
    s = ""
    while N != 0:
        r = N%2
        s = str(r) + s
        N = (N-r)//-2
    print(s)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
if n == 0:
  print('0')
else:
  s = ''
  while n != 0:
    if -(n % 2) == 0:
      s = '0' + s
    else:
      s = '1' + s
    n = -(n // 2)
  s.lstrip('0')
  print(s)

Solution (Python):
n=int(input())
x=""
while n!=0:
    x=str(n%2)+x
    n=-(n//2)
print(0 if x=="" else x)

Solution (Python):
N = int(input())

ans = ""

if N == 0:
    print(0)
else:
    while True:
        if N == 0:
            break
        if N % -2 == 0:
            ans = ans + "0"
            N = N // -2
        else:
            ans = ans + "1"
            N = (N-1) // -2
    print(ans[::-1])

Solution (Python):
import math
n = int(input())
thress = [0]

tmp = 0
for i in range(30):
    if tmp > 10000000000:
        break
    tmp += 4 ** i
    thress.append(tmp)
    thress.append(tmp)

num = 0
s = ''
for i in range(len(thress)):
    if n == 0:
        print(0)
        break
    if num == n:
        print(s)
        break
    bit = math.ceil((n - thress[i]) / (2 ** i)) % 2
    if bit == 0:
        s = '0' + s
    else:
        s = '1' + s
        num += (-2) ** i

Solution (Python):
N=int(input())
X=''
while N!=0:
  X=str(N%2)+X
  N=-(N//2)
print(0 if X=='' else X)

Solution (Python):
n = int(input())
x = ""
while n != 0:
    x = str(n % 2) + x
    n =- (n//2)
print(0 if x == "" else x)

Solution (Python):
import sys
n = int(input())

if n == 0:
    print(0)
    sys.exit(0)

res = ''
while n != 0:
    res = ''.join([str(abs(n%(-2))), res])
    n = (n - abs(n%(-2))) // -2

print(res)

Solution (Python):
n=int(input())
ans=""
if n==0:print("0");exit()
while n!=0:
    ans +=str(n%2)
    n=-(n//2)
print("".join(ans[::-1]))

Solution (Python):
n=int(input())
ans=""
if n==0:print("0");exit()
while n!=0:
    ans +=str(n%2)
    n=-(n//2)
print("".join(ans[::-1]))

Solution (Python):
n=int(input())
ans=""
if n==0:print("0");exit()
while abs(n)>0:
    if n%2!=0:
        n -=1
        ans +="1"
    else:ans +="0"
    n /=-2

print("".join(ans[::-1]))

Solution (Python):
n=int(input())
ans=""
if n==0:print("0");exit()
while abs(n)>0:
    if n%2!=0:
        n -=1
        ans +="1"
    else:
        ans +="0"
    n /=-2

print("".join(ans[::-1]))

Solution (Python):
import sys
N = int(input())
ans = ''
if N == 0:
    print(0)
    sys.exit()
while N != 0:
    if N % 2 != 0:
        N -= 1
        ans = '1' + ans
    else:
        ans = '0' + ans

    N = N // (-2)
print(ans)

Solution (Python):
n = int(input())
I = [[0,1]]
while n < I[-1][0] or I[-1][1] < n:
  if len(I)%2 != 0:
    I += [[I[-1][0]-2**(len(I)),I[-1][1]]]
  else:
    I += [[I[-1][0],I[-1][1]+2**(len(I))]]
ans = ''
for i in range(len(I)):
  if abs((I[-i-1][0]+I[-i-1][1])/2) < abs(n) and n * (-1)**(len(I)-i-1) > 0:
    ans += '1'
    n -= (-2)**(len(I)-i-1)
  else:
    ans += '0'
print(int(ans))

Solution (Python):
n = int(input())
i = 0
a,s= divmod(n, -2)
if s == -1: a,s = a+1,1
s = str(s)
while a:
    a,b = divmod(a, -2)
    if b == -1: a,b = a+1,1
    s = str(b)+s
print(s)

Solution (Python):
invtwos = [1]
i = 0
while abs(invtwos[i]) <= 10**10:
    invtwos.append(invtwos[i]*(-2))
    i += 1
invtwos.append(invtwos[-1]*(-2))

n = int(input())
ans = []
i = 0
while n != 0:
    if n%abs(invtwos[i+1]) != 0:
        ans.append(1)
        n -= invtwos[i]
    else:
        ans.append(0)
    i += 1
ans.reverse()

if len(ans) == 0:
    print("0")
else:
    for i in range(len(ans)):
        if i != len(ans)-1:
            print(ans[i],end="")
        else:
            print(ans[i])

Solution (Python):
n=int(input())

ans=''
while n!=0:
  ans=str(n%2)+ans
  n=-(n//2)
print(ans if ans!='' else 0)

Solution (Python):
n = int(input())

if n == 0:
    print(0)
else:
    s = ''
    while n != 0:
        if n % 2 != 0:
            n -= 1
            s = '1' + s
        else:
            s = '0' + s
        n //= -2
    print(s)

Solution (Python):
N = int(input())

import sys
if N == 0:
    print(0)
    sys.exit()

ans = ""
i = 1
while abs(N) > 0:
    if N%2 == 1:
        ans = "1" + ans
        N -= 1
        N //= -2
    else:
        ans = "0" + ans
        N //= -2

print(ans)

Solution (Python):
n=int(input())
if n==0:
  print('0')
else:
  ls=[]
  while(n!=0):
    ls.append(str(n%2))
    n=-1*(n-n%2)//2
  ls.reverse()
  oneLinerString="".join(ls)
  print(oneLinerString)

Solution (Python):
N = int(input())
n, ans, t = N, '', 2

while abs(n) > 0:
  if n%t == 0:
    ans = '0' + ans
  else:
    ans = '1' + ans
  n = n - n % t
  t = t * (-2)
  
print('0' if N==0 else ans)

Solution (Python):
N = int(input())

n, ans, d = N, '', 2
while abs(n) > 0:
    ans = '0' + ans if n % d == 0 else '1' + ans
    n, d = n - n % d, d * (-2)
print('0' if N == 0 else ans)

Solution (Python):
N = int(input())
S = ""

while N!=0:
  
  if N%(-2) == 0:
    S = "0" + S
  else:
    S = "1" + S
    N -= 1
  
  N /= (-2)

if S == "":
  S = "0"

print(S)

Solution (Python):
N = int(input())
L = []
c = N
for i in range(64):
  d = c%2
  L.append(d)
  if i%2 == 0:
    c = (c-d)//2
  else:
    c = (c+d)//2
L = list(reversed(L))
try:
  i = L.index(1)
  L = L[i:]
  s = "".join(map(str, L))
  print(s)
except:
  print("0")

Solution (Python):
n = int(input())

if n == 0:
    print(0)

else:
    dig = []

    while n:
        quo = (n - 1) // -2
        sur = n + 2 * quo
        dig.append(str(sur))
        n = quo

    print("".join(dig[::-1]))

Solution (Python):
def sigma4jou(k):
    total = 0
    for i in range(k):
        total += 4 ** (i)
    return(total)

def pketa(N):
    k = 1
    while N - sigma4jou(k) > 0:
        k += 1
    return(2 * k - 1)

def mketa(N):
    k = 1
    while N + 2 * sigma4jou(k) < 0:
        k += 1
    return(2 * k)

def getResult(N):
    result = ""
    if N == 0:
        result += "0"
    elif N > 0:
        k = pketa(N)
        for i in range(k, 0, -2):
            j = int((i+1)/2)
            if abs((sigma4jou(j) - N) // (2 ** (i-1))) % 2 == 0:
                result += "1"
            else:
                result += "0"
            if i > 1:
                if abs(((sigma4jou(j) - N)) // (2 ** (i-2))) % 2 == 1:
                    result += "1"
                else:
                    result += "0"
    elif N < 0:
        k = mketa(N)
        for i in range(k, 0, -2):
            j = int(i/2)
            if abs((N + 2 * sigma4jou(j)) // (2 ** (i-1))) % 2 == 0:
                result += "1"
            else:
                result += "0"
            if i > 1:
                if abs(((N + 2 * sigma4jou(j))) // (2 ** (i-2))) % 2 == 1:
                    result += "1"
                else:
                    result += "0"
    return(result)

N = int(input())
print(getResult(N))

Solution (Python):
import sys
n = int(input())
if n == 0:
  print('0')
  sys.exit()
t = []
while n != 0:
  r = n % 2
  t.append(str(r))
  n = (n - r) // -2
print(''.join(t[::-1]))

Solution (Python):
import sys
n = int(input())
if n == 0:
  print('0')
  sys.exit()
t = []
while n != 0:
  r = n % 2
  t.append(str(r))
  n = (n - r) // -2
print(''.join(reversed(t)))

Solution (Python):
N = int(input())
ans = []

if N == 0:
    print(0)
    exit()

while N != 0:
    r = N % 2
    r = abs(r)
    N = (N - r) // -2
    ans.append(str(r))
ans.reverse()
print(''.join(ans))

Solution (Python):

import sys


def solve(N: int):
    ans = []
    
    while(N != 0):
        r = N % 2
        if(r < 0):
            r += 2
        ans.append(r)
        N = int((N-r)/(-2))
    if(not ans):
        print(0)
    else:
        print(''.join(map(str, reversed(ans))))
        
    return



def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  
    solve(N)

if __name__ == '__main__':
    main()

Solution (Python):
n = int(input())
digit = 1
ex = ""
while(n):
    if n%2==0:
        ex='0'+ex
    else:
        ex='1'+ex
        n-=-1+2*(digit%2)
    n=n//2
    digit+=1
print(ex if ex else "0")

Solution (Python):
n = int(input())
ans = []
if n == 0:
  ans.append('0')
while n != 0:
  r = n % 2
  r = r if r >= 0 else 1 
  n = (n-r)//-2
  ans.append(str(r))
ans = reversed(ans)
print(''.join(ans))

Solution (Python):
n=int(input())

s=''
while n!=0:
    s=str(n%2)+s
    n=-(n//2)

print(s if len(s)!=0 else 0)

Solution (Python):
def resolve():
    big_num = 1000
    n = int(input())
    if n == 0:
        print(0)
    else:
        s = ""
        while n != 0:
            if n % 2 != 0:
                n -= 1
                s = "1" + s
            else:
                s = "0" + s
            n //= -2
        print(s)
        
resolve()

Solution (Python):
import os, sys, re, math

def doit(N):
    if N == 0:
        return ''
    if N % 2 == 0:
        return doit(N // -2) + '0'
    else:
        return doit((N-1) // -2) + '1'

N = int(input())
if N == 0:
    print('0')
else:
    print(doit(N))

Solution (Python):
N = int(input())
ans = []

if N == 0:
    print (0)
    exit()

num = 1
while N:
    if N % (num * (-2)):
        ans.append(1)
        N -= num
    else:
        ans.append(0)
    num *= -2

print (*ans[::-1], sep = '')

Solution (Python):

a = int(input())
seed = ''
num = 1
while a:
    if a % (num * -2): 
        seed += '1'
        a -= num
    else:
        seed += '0'
    num *= -2

print(seed[::-1] or '0')

Solution (Python):
line = raw_input()
n = int(line)
ret = []
while n != 0:
    a = n % 2
    ret.insert(0, a)
    n = (n - a) / -2
ret = ret if ret else [0]
print ''.join(str(i) for i in ret)

Solution (Python):
n=int(input())
if n == 0:
    print(0)
k=-2
bi=''
while n!=0:
    bi+=str(n%abs(k))
    if k<0:n=-(-n//k)
    else:n=n//k
print(bi[::-1])

Solution (Python):
n = int(input())
s = ""
while n!=0:
  s = str(n%2)+s
  n = -(n//2)
  
print(0 if s=="" else s)

Solution (Python):
import sys

stdin = sys.stdin

ni = lambda: int(ns())
na = lambda: list(map(int, stdin.readline().split()))
ns = lambda: stdin.readline().rstrip()  

n = ni()

if n == 0:
    print(0)
else:
    s = ""
    while n != 0:
        if n % 2 != 0:
            n -= 1
            s = "1" + s
        else:
            s = "0" + s
        n //= -2
    print(s)

Solution (Python):
n = int(input())
ans = ""
while n != 0:
    if n % (-2) == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans
        n -= 1
    n /= -2
if ans == "":
    ans = "0"
print(ans)

Solution (Python):
import numpy as np

n = int(input())
ans = ""

ind = 0
while (True):
    if n == 0:
        break
    else:
        if n % (-2)**(ind+1) == 0:
            ans += "0"
        else:
            ans += "1"
            n -= (-2)**(ind)
    
    
    ind += 1


ans = ans[::-1]
if not ans :
    ans = "0"
print(ans)

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N = I()

def n_base(n,k):
    if n==0:
        return 0
    else:
        bi=''
        if k<0:
            while n!=0:
                bi+=str(n%abs(k))
                n=-(-n//k)
        else:
            while n!=0:
                bi+=str(n%abs(k))
                n=n//k
        return bi[::-1]

print(n_base(N,-2))

Solution (Python):

import sys
import math
from collections import defaultdict


sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]


mod = 10**9 + 7


def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
    read_all = [tuple(map(int, input().split())) for _ in range(N)]
    return map(list,zip(*read_all))



N = I()

def n_base(n,k):
    if n==0:
        return 0
    else:
        bi=''
        while n!=0:
            bi+=str(n%abs(k))
            if k<0:n=-(-n//k)
            else:n=n//k
        return bi[::-1]

print(n_base(N,-2))

Solution (Python):
n=int(input())
if n==0:
	print(0)
	exit()
x=""
while n!=0:
	y=n%(-2)
	if y==-1:
		y+=2
		x+=str(y)
		n=n//(-2)+1
	else:
		x+=str(y)
		n//=(-2)
print(x[::-1])

Solution (Python):
n=int(input())
x=""
while n!=0:
    x=str(n%2)+x
    n=-(n//2)
print(0 if x=="" else x)

Solution (Python):
n=int(input());a=""
while n:a=str(n%2)+a;n=(n-n%2)//-2
print(a or 0)

Solution (Python):
N=int(input())
S=""
if N==0:
  print(0)
  exit(0)    
while N!=0:
  r=N%(-2)
  N=N//(-2)
  if r<0:
    r+=2
    N+=1
  S+=str(r)
print(S[::-1])

Solution (Python):
def main():
    N = int(input())
    if N == 0: return "0"
    s = ""
    i = 0
    while N != 0:
        if i % 2 == 0:
            s += str(N % 2)
            N = N // 2
        else:
            N = - N
            s += str(N % 2)
            N = N // 2
            N = - N
        i += 1

    return s[::-1]



if __name__ == '__main__':
    print(main())

Solution (Python):
import math
import sys
import queue
from collections import Counter
from itertools import accumulate
from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a * b // gcd(a, b)

def combination_count(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))

def permutations_count(n, r):
    return math.factorial(n) // math.factorial(n - r)

mod = 1000000007

"""


    = sys.stdin.readline().rstrip()
    = list(sys.stdin.readline().rstrip())


    = int(sys.stdin.readline())
    = map(int, sys.stdin.readline().split())
    = list(map(int, sys.stdin.readline().split()))
    = [list(map(int,list(sys.stdin.readline().split()))) for i in range(N)]
"""









if __name__ == "__main__":
    N = int(sys.stdin.readline())
    ls = []
    if N == 0:
        print(0)
    else:
        while True:
            if N == 0:
                break
            if N % 2 == 0:
                ls.append("0")
            else:
                ls.append("1")
                
                
                N -= 1
            N = N // -2
        ls.reverse()
        print("".join(ls))

Solution (Python):
n=int(input())
ans=[]
memo=1
if n==0:
  print(0)
else:
  while n!=0:
    if abs(n)%2==1:
      ans.append("1")
      n-=memo
    else:
      ans.append("0")
    n//=2
    memo*=-1
  print("".join(ans[::-1]))

Solution (Python):
N = int(input())

ans = ""

if N == 0:
    print(0)
    exit()

while N != 0:
    
    if N % -2 == 0:
        ans = "0" + ans
    else:
        ans = "1" + ans
    tmp = abs(N % -2)
    
    N = (N-tmp) // -2

print(ans)

Solution (Python):
import math
 
N = int(input())
 
def calc_power(num):
    if num > 1:
        m = 5
        power = 2
        while True:
            if num <= m:
                return_num = power
                break
            else:
                m = m * 4 + 1
                power += 2 
    elif num == 1:
        return_num = 0
    elif num == 0:
        print('0')
        exit()
    else:
        m = -2
        power = 1
        while True:
            if num >= m:
                return_num = power
                break
            else:
                m = m * 4 - 2
                power += 2
 
    return return_num
 
num = N
pre_power = calc_power(N) + 1
ans = ''
while num != 0:
    power = calc_power(num)
    num -= (-2) ** power
    if power == pre_power - 1:
        ans += '1'
    else:
        for _ in range(pre_power - 1 - power):
            ans += '0'
        ans += '1'
    if num == 0:
        for _ in range(power):
            ans += '0'
    pre_power = power
 
print(ans)

Solution (Python):
import math

N = int(input())

def calc_power(num):
    if num > 1:
        m = 5
        power = 2
        while True:
            if num <= m:
                return_num = power
                break
            else:
                m = m * 4 + 1
                power += 2 
    elif num == 1:
        return_num = 0
    elif num == 0:
        print('0')
        exit()
    else:
        m = -2
        power = 1
        while True:
            if num >= m:
                return_num = power
                break
            else:
                m = m * 4 - 2
                power += 2

    return return_num

num = N
pre_power = calc_power(N) + 1
ans = ''
while num != 0:
    power = calc_power(num)
    num -= (-2) ** power
    if power == pre_power - 1:
        ans += '1'
    else:
        for _ in range(pre_power - 1 - power):
            ans += '0'
        ans += '1'
    if num == 0:
        for _ in range(power):
            ans += '0'
    pre_power = power

print(ans)