AtCoder Beginner Contest 105 - Base -2 Number

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-----
-9

-----Sample Output-----
1011

As (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, 1011 is the base -2 representation of -9.

Source: atcoder | Difficulty: EASY


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


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


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])


N = int(input())
tmp = ''
while N:
	if N % 2 == 0:
		tmp += '0'
	else:
		tmp += '1'
	N -= 1
	N //= -2
if tmp == '':
	tmp = '0'
print(tmp[::-1])


N = int(input())
if N == 0:
	s = '0'
else:
	s = ''
while N != 0:
	m = N % 2
	s += str(m)
	N = (N - m) * -1 // 2
print(s[::-1])


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


def f(n):
	n = int(n)
	if n in [0, 1]:
		return str(n)
	return f((n - abs(n) % 2) / -2) + str(abs(n) % 2)
print(f(int(input())))


N = int(input())
ans = ''
if N == 0:
	print(0)
	exit()
while N != 0:
	r = N % 2
	N = (N - r) // -2
	ans += '1' if r else '0'
print(ans[::-1])


N = int(input())
max_digit = 34
bits = [0] * max_digit
sign = N > 0
if N < 0:
	N = -N
for i in range(N.bit_length()):
	if N >> i & 1:
		if i & 1 == sign:
			bits[i] += 1
			bits[i + 1] += 1
		else:
			bits[i] += 1
for i in range(max_digit):
	if bits[i] == 2:
		if bits[i + 1] == 1:
			bits[i] = 0
			bits[i + 1] = 0
		else:
			bits[i] = 0
			bits[i + 1] += 1
			bits[i + 2] += 1
res = ''
flg = False
for i in reversed(range(max_digit)):
	if not flg and bits[i] == 1:
		flg = True
		res += '1'
	elif flg:
		res += str(bits[i])
if res == '':
	res = '0'
print(res)


(n, i, a) = (int(input()), 0, 0)
while n:
	r = (-2) ** i
	if (n - r) % (-2 * r) == 0:
		a += 10 ** i
		n -= r
	i += 1
print(a)


import math
N = int(input())
if N == 0:
	print(0)
	return
p = int(math.log2(abs(N))) + 1
ans = [0] * (p + 10)
now = 0
for i in range(p + 10):
	x = N % 2 ** (i + 1)
	y = (now + (-1) ** i * 2 ** i) % 2 ** (i + 1)
	if y == x or y + 2 ** (i + 1) == x:
		now += (-1) ** i * 2 ** i
		ans[i] = 1
	if now == N:
		break
p = 0
for i in range(1, len(ans) + 1):
	if p == 0:
		if ans[-i] != 0:
			p = 1
			print(ans[-i], end='')
	else:
		print(ans[-i], end='')
print('')


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


s = int(input())
x = ''
while s != 0:
	x = str(s % 2) + x
	s = -(s // 2)
print(0 if x == '' else x)


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


import sys
sys.setrecursionlimit(10 ** 8)

def ii():
	return int(sys.stdin.readline())

def mi():
	return map(int, sys.stdin.readline().split())

def li():
	return list(map(int, sys.stdin.readline().split()))

def li2(N):
	return [list(map(int, sys.stdin.readline().split())) for _ in range(N)]

def dp2(ini, i, j):
	return [[ini] * i for _ in range(j)]
N = ii()
ans = ''

def div(a, b=-2):
	if a >= 0:
		return (-(a // -b), a % -b)
	elif -a % -b == 0:
		return (-a // -b, 0)
	else:
		return (-a // -b + 1, 1)
while True:
	(N, m) = div(N)
	ans += str(m)
	if abs(N) < 2:
		break
if N == -1:
	ans += '11'
elif N == 1:
	ans += '1'
print(ans[::-1])


n = int(input())
ans = ''
if n == 0:
	print(0)
	exit()
while n != 0:
	tmp = n % 2
	ans += str(tmp)
	n = (n - tmp) // -2
ans = ans[::-1]
print(ans)


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


N = int(input())
if N == 0:
	print(0)
ans = ''
while N != 0:
	r = N % 2
	N = (N - r) // -2
	ans += str(r)
ans = ans[::-1]
print(ans)


N = int(input())

def base(x, n):
	ret = []
	while x != 0:
		ret.append(x % abs(n))
		if n < 0:
			x = -(-x // n)
		else:
			x //= n
	return ret
if N == 0:
	print(0)
else:
	print(''.join(map(str, reversed(base(N, -2)))))


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


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


N = int(input())
if N == 0:
	print(0)
	return
ans = ''
while N != 1:
	d = N % 2
	ans += str(d)
	N -= d
	N //= -2
ans += '1'
print(ans[::-1])


n = int(input())
if n == 0:
	print(0)
	return
ans = []
while n != 0:
	n -= 1
	ans.append(n % -2)
	n //= -2
tmp = [1 * (i == 0) for i in ans][::-1]
print(''.join(map(str, tmp)))


n = int(input())
if n == 0:
	print(0)
else:
	ans = ''
	while n != 0:
		d = -n % 2
		ans += str(d)
		n -= d
		n //= -2
	print(ans[::-1])


N = int(input())
ans = ''
for i in range(33):
	if N % pow(2, i + 1):
		ans += '1'
		N -= pow(-2, i)
	else:
		ans += '0'
print(int(ans[::-1]))


N = int(input())
res = ''
while N != 0:
	if N % 2 == 0:
		res += '0'
	else:
		N -= 1
		res += '1'
	N //= -2
if len(res) == 0:
	res = '0'
print(res[::-1])


N = int(input())
ls = []
while True:
	ls.append(N % 2)
	N = -(N // 2)
	if N == 0:
		break
print(*reversed(ls), sep='')


n = int(input())
t = 1
b = ''
for i in range(len(bin(n))):
	if n % (2 * t):
		b = '1' + b
		n -= t
	else:
		b = '0' + b
	t *= -2
print(int(b))


N = int(input())
S = ''
while 1:
	if N * N == N:
		S += str(N)
		break
	S += str(N % 2)
	N = (N - N % 2) // -2
print(S[::-1])


import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, radians, log2
from itertools import accumulate, permutations, combinations, product
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(map(int, input().split()))

def ZIP(n):
	return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7
N = INT()
if N == 0:
	print(0)
	return
lim = 32
top = [0] * (lim + 1)
bottom = [0] * (lim + 1)
for i in range(1, lim + 1):
	if i % 2:
		t = (i + 1) // 2
		top[i] = (4 ** t - 1) // 3
		bottom[i] = bottom[i - 1]
	else:
		b = i // 2
		bottom[i] = (4 ** b - 1) * 2 // 3
		top[i] = top[i - 1]
digit = [0] * (lim + 1)
for i in range(1, lim + 1):
	digit[i] = (-2) ** (i - 1)
if 0 <= N:
	idx = bisect_left(top, N)
else:
	idx = bisect_left(bottom, -N)
ans = ''
for i in range(idx, 0, -1):
	if -bottom[i - 1] <= N <= top[i - 1]:
		ans += '0'
	else:
		ans += '1'
		N -= digit[i]
print(ans)


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


n = int(input())
ans = ''
while n != 0:
	if n % 2 != 0:
		n -= 1
		ans = '1' + ans
	else:
		ans = '0' + ans
	n = -n >> 1
print(ans if ans != '' else 0)


n = int(input())
ans = 0
base = 1
n = -n
while n != 0:
	p = abs(n % -2)
	n = (n + p) // -2
	ans += p * base
	base *= 10
print(ans)


N = int(input())

def max_pos_number(n):
	val = 0
	for i in range(n):
		if i % 2 == 0:
			val += 2 ** i
	return val

def min_pos_number(n):
	val = 0
	for i in range(n):
		if i % 2 == 1:
			val -= 2 ** i
	return val
n = 1
while True:
	if min_pos_number(n) <= N <= max_pos_number(n):
		break
	n += 1
result = []
for i in range(n - 1, -1, -1):
	if i % 2 == 0:
		if N > max_pos_number(i):
			result.append(1)
			N -= (-2) ** i
		else:
			result.append(0)
	elif N < min_pos_number(i):
		result.append(1)
		N -= (-2) ** i
	else:
		result.append(0)
print(''.join([str(x) for x in result]))


n = int(input())
if n == 0:
	print(0)
	return
if n == 1:
	print(1)
	return
l = []
while n != 1:
	if n % 2 == 0:
		n //= -2
		l.append(0)
	else:
		n = (n - 1) // -2
		l.append(1)
l.append(1)
l = l[::-1]
print(*l, sep='')


N = int(input())
a = ''
if N == 0:
	a = 0
while N != 0:
	if N % 2 != 0:
		N -= 1
		a = '1' + a
	else:
		a = '0' + a
	N = N // -2
print(a)


N = int(input())
A = []
if N == 0:
	A = [0]
i = 0
while N != 0:
	A = [N % 2] + A[:]
	N //= 2
	N = -N
for i in range(len(A)):
	print(A[i], end='')


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)


import math
import sys
pin = sys.stdin.readline

def main():
	N = int(pin())
	ansl = []
	if N == 0:
		print(0)
		return
	while True:
		if N == 0:
			break
		ansl.append(N % 2)
		N = -(N // 2)
	ans = ''.join(map(str, ansl))
	ans = ans[::-1]
	print(ans)
	return
main()


n = int(input())
if n == 0:
	print(0)
	return
a = [1]
p = [1]
m = [0]
hi = [1]
lo = [1]
i = 0
while True:
	if n >= lo[i] and n <= hi[i]:
		break
	i += 1
	a.append(a[i - 1] * -2)
	if i % 2 == 0:
		p.append(p[i - 1] + a[i])
		m.append(m[i - 1])
	else:
		p.append(p[i - 1])
		m.append(m[i - 1] + a[i])
	hi.append(a[i] + p[i - 1])
	lo.append(a[i] + m[i - 1])
ans = []
for j in range(i + 1)[::-1]:
	if n >= lo[j] and n <= hi[j]:
		ans.append(1)
		n -= a[j]
	else:
		ans.append(0)
print(*ans, sep='')


N = int(input())
ans = ''
while 1:
	ans += str(N % 2)
	if N in [0, 1]:
		break
	N = 0 - N // 2
print(ans[::-1])


N = int(input())
if N == 0:
	print(0)
	return
if N > 0:
	S = bin(N)[2:]
	S = list(S[::-1])
	S = list(map(int, S))
	S += [0] * 1000
	i = 0
	while True:
		S[i + 1] += S[i] // 2
		S[i] = S[i] % 2
		if i % 2 == 1:
			S[i + 1] = S[i + 1] + S[i]
		i += 1
		if i == len(S) - 1:
			break
	S = list(map(str, S))
	S = list(reversed(S))
	S = ''.join(S)
	print(int(S))
else:
	N = abs(N)
	S = bin(N)[2:]
	S = list(S[::-1])
	S = list(map(int, S))
	S += [0] * 1000
	i = 0
	while True:
		S[i + 1] += S[i] // 2
		S[i] = S[i] % 2
		if i % 2 == 0:
			S[i + 1] = S[i + 1] + S[i]
		i += 1
		if i == len(S) - 1:
			break
	S = list(map(str, S))
	S = list(reversed(S))
	S = ''.join(S)
	print(int(S))


n = int(input())
if n == 0:
	print(0)
	return
ans = ''
while abs(n) > 0:
	r = n % 2
	ans += str(r)
	n //= 2
	n = -n
if abs(n) % 2 == 1:
	print(ans)
else:
	print(ans[::-1])


n = int(input())
s = ''
while True:
	r = n % -2
	n //= -2
	if r < 0:
		r += 2
		n += 1
	s += str(r)
	if n == 0:
		break
print(s[::-1])


N = int(input())

def solve(N):
	if N == 0:
		return '0'
	ans = ''
	while N != 0:
		ans += str(N & 1)
		N >>= 1
		N *= -1
	return ans[::-1]
print(solve(N))


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])


n = int(input())
b = ''
while n:
	b = str(n % 2) + b
	n = -(n // 2)
print(b if b else 0)


n = int(input())
tmp = int('1010101010101010101010101010101010', 2)
print(format(tmp ^ tmp + n, 'b'))


import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 8)
from itertools import accumulate
from itertools import permutations
from itertools import combinations
from collections import defaultdict
from collections import Counter
import fractions
import math
from collections import deque
from bisect import bisect_left
from bisect import bisect_right
from bisect import insort_left
import itertools
from heapq import heapify
from heapq import heappop
from heapq import heappush
import heapq
from copy import deepcopy
from decimal import Decimal
alf = list('abcdefghijklmnopqrstuvwxyz')
ALF = list('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
INF = float('inf')
s = ''
N = int(input())
if N == 0:
	print(0)
else:
	while N != 0:
		x = N % -2
		if x == 0:
			s = '0' + s
			N = N // -2
		else:
			N = N // -2 + 1
			s = '1' + s
	print(s)


N = int(input())
ans = ''
while N != 0:
	bit = N % 2
	ans = str(bit) + ans
	N -= bit
	N //= -2
if not ans:
	ans = 0
print(ans)


n = int(input())
ans = ''
k = 0
while n != 0:
	ans = str(n % 2) + ans
	n = n - n % 2 * (-1) ** k
	n = n // 2
	k += 1
if ans == '':
	ans = 0
print(ans)


import sys
stdin = sys.stdin
sys.setrecursionlimit(10 ** 6)
ni = lambda : int(ns())
na = lambda : list(map(int, stdin.readline().split()))
nn = lambda : list(stdin.readline().split())
ns = lambda : stdin.readline().rstrip()
n = ni()
a = 2
ans = ''
if n == 0:
	print(0)
	return
while n != 0:
	if n % a == 0:
		ans = '0' + ans
	else:
		ans = '1' + ans
		n -= a // 2
	a *= -2
print(ans)


N = int(input())
ans = ''
while N:
	ans = str(abs(N % 2)) + ans
	N = -(N // 2)
print(ans or 0)


n = int(input())
amari = []
while True:
	if n > 1 or n < 0:
		amari.append(-(n % -2))
		n = (n - -(n % -2)) // -2
	else:
		amari.append(n)
		break
gyaku = amari[::-1]
print(*gyaku, sep='')


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


a = int(input())
s = ''
while a != 0:
	s += str(a % 2)
	a = -(a // 2)
print(int(s[::-1]) if s != '' else 0)


N = int(input())
if N == 0:
	print(0)
	exit()
S = ''
while N:
	S = str(N % 2) + S
	N = -(N - N % 2) // 2
print(S)


n = int(input())

def F2(n):
	if n // 2 == 0:
		return str(n % 2)
	return F2(-(n // 2)) + str(n % 2)
print(F2(n))


from math import ceil, floor, factorial, gcd, sqrt, log2, cos, sin, tan, acos, asin, atan, degrees, radians, pi, inf, comb
from itertools import accumulate, groupby, permutations, combinations, product, combinations_with_replacement
from collections import deque, defaultdict, Counter
from bisect import bisect_left, bisect_right
from operator import itemgetter
from heapq import heapify, heappop, heappush
from queue import Queue, LifoQueue, PriorityQueue
from copy import deepcopy
from time import time
import string
import sys
sys.setrecursionlimit(10 ** 7)

def input():
	return sys.stdin.readline().strip()

def INT():
	return int(input())

def MAP():
	return map(int, input().split())

def LIST():
	return list(MAP())
n = INT()
if n == 0:
	print(0)
	return
ans = deque()
i = 0
while n != 0:
	tmp = n % 2 ** (i + 1) // 2 ** i
	ans.appendleft(tmp)
	n -= tmp * (-2) ** i
	i += 1
print(*list(ans), sep='')


n = int(input())
res = ''
while n:
	res += '1' if n % 2 else '0'
	n = -(n - 1) // 2
print(res[::-1] or '0')


import math
N = int(input())
ans = ''
if N == 1:
	print('1')
elif N == 0:
	print('0')
elif N == -1:
	print('10')
else:
	while True:
		r = N % 2
		N = (N - r) / -2
		ans = str(int(r)) + ans
		if N == 0 or N == 1:
			ans = str(int(N)) + ans
			break
	print(ans)


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)


N = int(input())

def alg(N):
	if N == 0 or N == 1:
		return str(N)
	else:
		return alg(N // 2 * -1) + str(N % 2)
print(alg(N))


N = int(input())
ans = []
while N != 0:
	r = N % 2
	N = (N - r) // -2
	ans += [r]
print(''.join(map(str, ans[::-1])) if ans else 0)


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


(n, ans) = (int(input()), [])
while n:
	ans.append(str(abs(n) % 2))
	n = (n - abs(n) % 2) // -2
print(''.join(reversed(ans)) if ans else '0')


n = int(input())
mb = []
n = -n
while True:
	mb.insert(0, str(n % 2))
	n = -n // 2
	if n == 0:
		break
ans = ''.join(mb)
print(ans)


import math

def solve(N):
	if N == 0:
		print('0')
		return
	ans = ''
	while N != 0:
		m = N % 2
		ans = str(m) + ans
		N = (N - m) * -1 >> 1
	print(ans)

def __starting_point():
	N = int(input())
	solve(N)
__starting_point()


N = int(input())
t = N
ans = ''
while t != 0:
	(q, r) = divmod(t, 2)
	ans = str(r) + ans
	t = -q
print(ans if ans else '0')


N = int(input())
ans = []
if N == 0:
	ans.append('0')
while N != 0:
	ans.append(str(N % 2))
	N = -(N // 2)
ans.reverse()
print(''.join(ans))


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


(N, S, p) = (int(input()), [], 1)
if N == 0:
	print(0)
while N != 0:
	R = N % 2
	S.append(R)
	N = (N - p * R) // 2
	p *= -1
print(*reversed(S), sep='')


import sys
import bisect
SUM_P = [2 ** x for x in range(0, 31, 2)]
SUM_M = [2 ** x for x in range(1, 31, 2)]
for i in range(len(SUM_P) - 1):
	SUM_P[i + 1] += SUM_P[i]
for i in range(len(SUM_M) - 1):
	SUM_M[i + 1] += SUM_M[i]
N = int(input())
ret = 0
while N != 0:
	if N > 0:
		idx = bisect.bisect_left(SUM_P, N)
		idx = idx * 2
		N -= 2 ** idx
		ret += 2 ** idx
	else:
		idx = bisect.bisect_left(SUM_M, abs(N))
		idx = idx * 2 + 1
		N += 2 ** idx
		ret += 2 ** idx
print(format(ret, 'b'))


n = int(input())
ans = abs(n)
for i in range(n > 0, 50, 2):
	if ans & 1 << i == 1 << i:
		ans += 1 << i + 1
print(f'{ans:b}')


n = int(input())
s = ''
while n != 0:
	s = str(n % 2) + s
	n = -(n // 2)
print(s * (s != '') or 0)


def f(n):
	if n == 0 or n == 1:
		return str(int(n))
	res = n % 2
	return f((n - res) / -2) + str(int(res))
N = int(input())
print(f(N))


n = int(input())
s = ''
while n != 0:
	r = abs(n % 2)
	n = (n - r) // -2
	s = str(r) + s
if s == '':
	s = '0'
print(s)


n = int(input())
dp = [0] * 40
if n == 0:
	print(0)
elif n > 0:
	x = bin(n)
	bx = x[2:]
	lx = len(bx)
	for i in range(lx - 1, -1, -1):
		dp[i] = int(bx[lx - 1 - i])
	for i in range(40):
		if i % 2 == 1 and dp[i] == 1:
			dp[i + 1] += 1
	while max(dp) > 1:
		for i in range(40):
			if dp[i] >= 2:
				dp[i] -= 2
				if dp[i + 1] > 0:
					dp[i + 1] -= 1
				else:
					dp[i + 1] += 1
					dp[i + 2] += 1
	dpr = list(reversed(dp))
	dprs = list(map(lambda x: str(x), dpr))
	dprj = ''.join(dprs)
	print(int(dprj))
else:
	x = bin(-n)
	bx = x[2:]
	lx = len(bx)
	for i in range(lx - 1, -1, -1):
		dp[i] = int(bx[lx - 1 - i])
	for i in range(40):
		if i % 2 == 0 and dp[i] == 1:
			dp[i + 1] += 1
	while max(dp) > 1:
		for i in range(40):
			if dp[i] >= 2:
				dp[i] -= 2
				if dp[i + 1] > 0:
					dp[i + 1] -= 1
				else:
					dp[i + 1] += 1
					dp[i + 2] += 1
	dpr = list(reversed(dp))
	dprs = list(map(lambda x: str(x), dpr))
	dprj = ''.join(dprs)
	print(int(dprj))


m = 2 ** 33 // 3
print(bin(int(input()) + m ^ m)[2:])


n = int(input())
if n == 0:
	print(0)
	exit(0)
s = ''
while n != 0:
	m = abs(n % -2)
	s = str(m) + s
	n = (n - m) // -2
print(s)


n = int(input())
c = 0
while 1:
	c += 1
	if n == 0:
		break
	if n > 0:
		if c % 2 == 1:
			if (4 ** (c // 2 + 1) - 1) // 3 >= n:
				break
	elif n < 0:
		if c % 2 == 0:
			if abs(2 * (4 ** (c // 2) - 1)) // 3 >= abs(n):
				break
if n == 0:
	ans = ['0']
else:
	k = 0
	ans = []
	while k < c:
		ans.append(str(n % 2))
		n = -1 * (n // 2)
		k += 1
print(''.join(ans[::-1]))


N = int(input())
ans = ''
a = -2
r = abs(N % a)
q = (N - r) // a
while q != 0:
	ans = str(r) + ans
	N = q
	r = abs(N % a)
	q = (N - r) // a
ans = str(r) + ans
print(ans)


import sys
input = sys.stdin.readline
n = int(input())
x = ''
while n != 0:
	x = str(n % 2) + x
	n = -(n // 2)
print(x if x else 0)


n = int(input())
b = 2
c = 0
ans = 0
while n != 0:
	if n % b != 0:
		ans += 10 ** c
		n -= (-2) ** c
	c += 1
	b *= 2
print(ans)


N = int(input())
i = 0
s = ''
while N != 1 and N != 0:
	a = (N + 1) // -2 + 1
	m = N - -2 * a
	s += str(m)
	N = a
s += str(N)
print(s[::-1])


def IntBaseConvert(N, K):
	if type(N) is int and type(K) is int:
		if K >= 2 and N >= 0:
			if N == 0:
				return [0]
			else:
				ConvertNum = []
				while N > 0:
					ConvertNum.append(N % K)
					N = N // K
				return ConvertNum[::-1]
		elif K <= -2:
			if N == 0:
				return [0]
			else:
				ConvertNum = []
				while abs(N) > 0:
					ConvertNum.append(N % abs(K))
					N = (N - N % abs(K)) // K
				return ConvertNum[::-1]
		else:
			return []
	else:
		return []
ConvertNum = IntBaseConvert(int(input()), -2)
print(''.join((str(T) for T in ConvertNum)))


import math
from math import gcd, pi, sqrt
INF = float('inf')
import sys
sys.setrecursionlimit(10 ** 6)
import itertools
from collections import Counter, deque

def i_input():
	return int(input())

def i_map():
	return list(map(int, input().split()))

def i_list():
	return list(i_map())

def i_row(N):
	return [i_input() for _ in range(N)]

def i_row_list(N):
	return [i_list() for _ in range(N)]

def s_input():
	return input()

def s_map():
	return input().split()

def s_list():
	return list(s_map())

def s_row(N):
	return [s_input for _ in range(N)]

def s_row_str(N):
	return [s_list() for _ in range(N)]

def s_row_list(N):
	return [list(s_input()) for _ in range(N)]

def main():
	n = i_input()
	l = []
	cnt = 0
	while True:
		if cnt % 2 == 0:
			l.append(n % 2)
			n = -(n // 2)
			cnt += 1
		else:
			l.append(n % 2)
			n = -(n // 2)
			cnt += 1
		if n == 0:
			break
	l.reverse()
	print(''.join(map(str, l)))

def __starting_point():
	main()
__starting_point()


def m(K):
	return '1' if K == 1 else '0' if K == 0 else m(-(K - K % 2) // 2) + ('1' if K % 2 else '0')
print(m(int(input())))


import sys
from collections import deque, defaultdict
from math import sqrt, factorial, gcd, ceil, atan, pi
import string
from bisect import bisect_left
MOD = int(1000000000.0) + 7
INF = float('inf')

def solve():
	n = -int(input())
	if n == 0:
		print(0)
		return
	ans = []
	while n != 0:
		(n, m) = divmod(n, -2)
		ans.append(-m)
	ans.reverse()
	print(''.join([str(x) for x in ans]))
t = 1
for case in range(1, t + 1):
	ans = solve()


n = int(input())
ans = []
a = n
while a != 0:
	ans.append(a % 2)
	a = (a - a % 2) // -2
if ans == []:
	ans = [0]
print(''.join(map(str, reversed(ans))))


N = int(input())
if N >= 0:
	n = N
	i = 0
	while 1:
		b = bin(n)[2:]
		if i >= len(b):
			break
		if i % 2 == 1 and b[-i - 1] == '1':
			n += 2 ** (i + 1)
		i += 1
	print(bin(n)[2:])
else:
	n = -N
	i = 0
	while 1:
		b = bin(n)[2:]
		if i >= len(b):
			break
		if i % 2 == 0 and b[-i - 1] == '1':
			n += 2 ** (i + 1)
		i += 1
	print(bin(n)[2:])


N = int(input())
s = ''
while N != 0:
	s = str(N % 2) + s
	N = -(N // 2)
print(s * (s != '') or 0)


N = int(input())

def minus_binary(n, S: str):
	if n == 0:
		if S == '':
			S = '0'
		return S
	if n == 1:
		S = '1' + S
		return minus_binary(0, S)
	else:
		if n % 2 == 1:
			n -= 1
			S = '1' + S
		else:
			S = '0' + S
		return minus_binary(n / -2, S)
S = ''
print(minus_binary(N, S))


N = int(input())

def X(N):
	x = N % 2
	N_new = (N - x) // -2
	if N_new == 0:
		return x
	return X(N_new) * 10 + x
print(X(N))


N = int(input())
s = ''
while N != 0:
	r = int(N % 2)
	N = (N - r) / -2
	s += str(int(r))
if s == '':
	print(0)
	return
else:
	print(s[::-1])


n = int(input())
r = 0
while n:
	(p, a, k) = [(1, 1, 1), (-2, -2, 2)][n < 0]
	while abs(n) > abs(a):
		p *= 4
		a += p
		k <<= 2
	r |= k
	n -= p
print(bin(r)[2:])


N = int(input())
t = 1
k = 1
a = 0
while N != 0:
	if N % 2 ** t != 0:
		a += 10 ** (t - 1)
		N -= k
	t += 1
	k *= -2
print(a)


N = int(input())
res = []
sign = 1
while N:
	if N % 2 == 0:
		res.append(0)
	else:
		N -= sign
		res.append(1)
	N //= 2
	sign *= -1
if not res:
	res = [0]
print(*reversed(res), sep='')


def mod(i, j):
	if i % j == 0:
		return [str(0), i // j]
	else:
		return [str(-(i % j)), i // j + 1]
n = int(input())
w = ''
if n == 0:
	w = 0
else:
	while n != 0:
		(i, j) = mod(n, -2)
		w = i + w
		n = j
print(w)


import itertools
N = int(input())
if N == 0:
	print(0)
	return
ans = []
while N != 0:
	ans.append(N % 2)
	N = -(N - N % 2) // 2
ans.reverse()
print(''.join(list(map(str, ans))))


N = int(input())
if N == 0:
	print(0)
	return
ans = []
while N:
	ans.append(N % 2)
	N = N // 2
	N *= -1
print(''.join(map(str, ans[::-1])))


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


m = 2863311530
print(bin(int(input()) + m ^ m)[2:])


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


import math

def solve(N):
	if N == 0:
		print('0')
		return
	x = math.ceil(math.log2(abs(N))) + 1
	minus = [(-2) ** i for i in range(1, x + 1, 2)]
	plus = [(-2) ** i for i in range(0, x + 1, 2)]
	minus.sort()
	plus.sort(reverse=True)
	minus_sum = [0]
	for m in minus:
		minus_sum.append(minus_sum[-1] + m)
	plus_sum = [0]
	for p in plus:
		plus_sum.append(plus_sum[-1] + p)
	ans = ''
	n = 0
	flg = True if len(plus) > len(minus) else False
	m = 0
	p = 0
	while True:
		if flg:
			tg = plus[p]
			p += 1
		else:
			tg = minus[m]
			m += 1
		if n + tg >= N:
			if n + tg != N and n + tg + (minus_sum[-1] - minus_sum[m]) > N:
				ans += '0'
			else:
				ans += '1'
				n += tg
		elif n + tg + (plus_sum[-1] - plus_sum[p]) < N:
			ans += '0'
		else:
			ans += '1'
			n += tg
		flg = not flg
		if p >= len(plus) and m >= len(minus):
			break
	print(str(int(ans)))

def __starting_point():
	N = int(input())
	solve(N)
__starting_point()


n = int(input())
if n == 0:
	print('0')
else:
	sum = 0
	i = 0
	S = []
	while n != 0:
		x = n % 2 ** (i + 1)
		if x != 0:
			S.append('1')
			n -= (-2) ** i
		else:
			S.append('0')
		i += 1
	S = S[::-1]
	strS = ''.join(S)
	print(strS)


N = int(input())
a = []
if N == 0:
	a.append('0')
while N != 0:
	a.append(str(N % 2))
	N = -(N // 2)
print(''.join(reversed(a)))


import sys
input = sys.stdin.readline

def main():
	N = int(input())
	if N == 0:
		ans = '0'
	else:
		ans = ''
		while N != 0:
			(q, r) = divmod(N, -2)
			if r == 0:
				ans = ''.join(['0', ans])
			else:
				ans = ''.join(['1', ans])
			r = r + 2 if r < 0 else r
			N = (N - r) // -2
	print(ans)

def __starting_point():
	main()
__starting_point()


N = int(input())

def po(n, k):
	if k <= 0:
		return 0 <= n <= 1
	if k % 2 == 0 and -2 * (2 ** k - 1) // 3 <= n <= (2 ** (k + 2) - 1) // 3:
		return True
	elif k % 2 == 1 and -2 * (2 ** (k + 1) - 1) // 3 <= n <= (2 ** (k + 1) - 1) // 3:
		return True
	return False

def f(n):
	k = 0
	while True:
		if po(n, k):
			break
		k += 1
	ls = []
	while k >= 0:
		if po(n - (-2) ** k, k - 1):
			n -= (-2) ** k
			ls.append('1')
		else:
			ls.append('0')
		k -= 1
	return ''.join(ls)
print(f(N))


def main():
	n = int(input())
	ans = [] if n != 0 else [0]
	while n:
		ans.append(-(n % -2))
		n = -(n // 2)
	print(''.join(list(map(str, ans[::-1]))))

def __starting_point():
	main()
__starting_point()


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


n = int(input())
s = abs(n)
c = ''
if n == 0:
	print('0')
else:
	while n:
		c += str(n % 2)
		n -= 1
		n //= -2
print(c[::-1])


import sys
import math
from collections import defaultdict, deque, Counter
from copy import deepcopy
from bisect import bisect, bisect_right, bisect_left
from heapq import heapify, heappop, heappush
input = sys.stdin.readline

def RD():
	return input().rstrip()

def F():
	return float(input().rstrip())

def I():
	return int(input().rstrip())

def MI():
	return map(int, input().split())

def MF():
	return map(float, input().split())

def LI():
	return list(map(int, input().split()))

def TI():
	return tuple(map(int, input().split()))

def LF():
	return list(map(float, input().split()))

def Init(H, W, num):
	return [[num for i in range(W)] for j in range(H)]

def main():
	N = I()
	if N == 0:
		print(0)
		return
	if N < 0:
		N = -N
		D = defaultdict(int)
		index = 0
		while N >= 1:
			if N & 1 == 1:
				if index % 2 == 0:
					D[index] += 1
					D[index + 1] += 1
				else:
					D[index] += 1
			else:
				D[index] = D[index]
			N = N >> 1
			index += 1
	else:
		D = defaultdict(int)
		if N & 1 == 1:
			D[0] = 1
		else:
			D[0] = 0
		index = 1
		N = N >> 1
		while N >= 1:
			if N & 1 == 1:
				if index % 2 == 1:
					D[index] += 1
					D[index + 1] += 1
				else:
					D[index] += 1
			else:
				D[index] = D[index]
			N = N >> 1
			index += 1
	index = 0
	while True:
		if not index in D.keys():
			break
		if D[index] <= 1:
			pass
		else:
			temp = D[index]
			D[index] = temp % 2
			D[index + 1] += temp // 2
			D[index + 2] += temp // 2
			if D[index + 1] >= D[index + 2] * 2:
				temp = D[index + 2]
				D[index + 2] -= temp
				D[index + 1] -= temp * 2
		index += 1
	res = True
	for i in reversed(D.values()):
		if res and i == 1:
			res = False
		if not res:
			print(i, end='')
	print()

def __starting_point():
	main()
__starting_point()


def m(K):
	return str(K) if K * K == K else m(-(K - K % 2) // 2) + str(K % 2)
print(m(int(input())))


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


N = int(input())
A = []
if N == 0:
	print(0)
else:
	while abs(N) != 0:
		a = N % 2
		A.append(a)
		N = (N - a) // -2
B = A[::-1]
print(*B, sep='')


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


import bisect, collections, copy, heapq, itertools, math, string, sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(10 ** 7)
INF = float('inf')

def I():
	return int(input())

def F():
	return float(input())

def SS():
	return input()

def LI():
	return [int(x) for x in input().split()]

def LI_():
	return [int(x) - 1 for x in input().split()]

def LF():
	return [float(x) for x in input().split()]

def LSS():
	return input().split()

def resolve():
	N = I()
	if N == 0:
		print(0)
	else:
		ans = []
		while abs(N) > 0:
			r = N % 2
			ans.append(r)
			if r == 1:
				N -= 1
			N //= -2
		print(''.join([str(i) for i in reversed(ans)]))

def __starting_point():
	resolve()
__starting_point()


N = int(input())
res = ''
if N == 0:
	print(0)
	exit()
while N != 0:
	tmp = N % -2
	N = N // -2 - tmp
	res = str(abs(tmp)) + res
print(res)


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


n = int(input())
s = ''
if n == 0:
	s = '0'
while n != 0:
	bit = abs(n) % 2
	s = str(bit) + s
	n -= bit
	n //= -2
print(s)


def BaseM2Num(N):
	if N == 0:
		return [0]
	else:
		List = []
		while abs(N) > 0:
			if N % 2 == 0:
				N //= -2
				List.append(0)
			else:
				N = (N - 1) // -2
				List.append(1)
		return List[::-1]
List = BaseM2Num(int(input()))
print(''.join((str(T) for T in List)))


a = int(input())
b = ''
while a:
	b = str(a & 1) + b
	a = -(a >> 1)
print(b if b else 0)


N = int(input())
S = list()
if N == 0:
	print(0)
	return
elif N > 0:
	while N > 0:
		S.append(N % 2)
		N //= 2
	S.append(0)
	S.append(0)
	for i in range(len(S) - 1):
		if i % 2 == 1 and S[i] == 1:
			S[i + 1] += 1
		if S[i] == 2:
			S[i] = 0
			S[i + 1] += 1
else:
	N *= -1
	while N > 0:
		S.append(N % 2)
		N //= 2
	S.append(0)
	S.append(0)
	for i in range(len(S) - 1):
		if i % 2 == 0 and S[i] == 1:
			S[i + 1] += 1
		if S[i] == 2:
			S[i] = 0
			S[i + 1] += 1
S.reverse()
while S[0] == 0:
	S = S[1:]
ans = ''
for s in S:
	ans += str(s)
print(ans)


def main():
	import math
	N = int(input())
	n = math.ceil(math.log(100000000000, 4))
	M = int('10' * n, 2)
	B = format(N + M, 'b')
	print(even_toggle(B))

def even_toggle(b):
	r = []
	for i in range(len(b)):
		if i % 2 == 0:
			r.insert(0, b[-i - 1])
		else:
			r.insert(0, str(1 - int(b[-i - 1])))
	head_zeroes = 0
	for i in range(len(r)):
		if r[i] == '0':
			head_zeroes += 1
		else:
			break
	return ''.join(r[head_zeroes:]) or '0'
main()


n = -int(input())
a = ''
while n:
	a += str(n % 2)
	n //= -2
print(a[::-1] if a else 0)


n = int(input())
cnt = 0
ans = 0
while n != 0:
	now = n % 2
	n = -(n // 2)
	ans += now * 10 ** cnt
	cnt += 1
print(ans)


N = int(input())

def calc(x):
	ans = ''
	while True:
		if x % 2 == 0:
			ans = '0' + ans
		else:
			ans = '1' + ans
			x -= 1
		if x == 0:
			break
		x = x // -2
	return ans
a = calc(N)
print(a)


N = int(input())
a = 2
ans = ''
for i in range(1000):
	if N % a == 0:
		ans = '0' + ans
	else:
		ans = '1' + ans
		if i % 2 == 0:
			N -= 2 ** i
		else:
			N += 2 ** i
	a *= 2
	if N == 0:
		break
print(ans)


n = int(input())
if n == 0:
	print(0)
	return
ans = []
while n > 0 or n < 0:
	if n == 0:
		break
	elif n % 2 == 0:
		ans.append(0)
		n = n // -2
	else:
		ans.append(1)
		n = (n - 1) // -2
print(*ans[::-1], sep='')


import os
import sys
from collections import defaultdict, Counter
from itertools import product, permutations, combinations, accumulate
from operator import itemgetter
from bisect import bisect_left, bisect
from heapq import heappop, heappush, heapify
from math import ceil, floor, sqrt
from copy import deepcopy

def main():
	n = int(input())
	if n == 0:
		print(0)
		return
	ans = ''
	while n:
		if n % 2:
			n -= 1
			ans += '1'
		else:
			ans += '0'
		n //= -2
	print(ans[::-1])

def __starting_point():
	main()
__starting_point()


n = int(input())
ans = ''
res = -n
if n == 0:
	print(0)
	exit()
while res:
	ans = str(abs(res % -2)) + ans
	res //= -2
print(ans)


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])


n = int(input())
ans = []
if n == 0:
	print(0)
	return
while True:
	if n == 0:
		break
	if n >= 0:
		ans.append(n % 2)
		n = -1 * (n // 2)
	else:
		ans.append(n * -1 % 2)
		if n * -1 % 2 == 1:
			n = n * -1 // 2 + 1
		else:
			n = n * -1 // 2
for i in range(len(ans)):
	ans[i] = str(ans[i])
print(''.join(list(ans[::-1])))


N = int(input())
b = -2
temp = N
ans = ''
while True:
	if temp % b != 0:
		ans = '1' + ans
		temp = temp - b // -2
	else:
		ans = '0' + ans
	b = b * -2
	if temp == 0:
		break
print(ans)


x = [0] * 32
x[0] = 1
x[1] = -2
for i in range(2, 32):
	x[i] = x[i - 2] + (-2) ** i
n = int(input())
if n == 0:
	print(0)
	return
ans = ''
for i in range(2, 33)[::-1]:
	if i % 2:
		l = x[i - 2]
		r = x[i - 1]
	else:
		l = x[i - 1]
		r = x[i - 2]
	t = n - (-2) ** i
	if l <= t and t <= r:
		n = t
		ans = ans + '1'
	else:
		ans = ans + '0'
ls = ['10', '11', '00', '01']
ans = ans + ls[n + 2]
for i in range(len(ans)):
	if ans[i] == '1':
		re = i
		break
print(ans[re:])


n = int(input())
if n == 0:
	print(0)
	return
ans = []
while n != 0:
	rem = n % 2
	n = (n - rem) // -2
	ans.append(rem)
ans.reverse()
print(''.join(map(str, ans)))


N = int(input())
ans = ''
if N == 0:
	print(0)
	return
while N != 0:
	(a, b) = divmod(N, 2)
	ans = str(b) + ans
	N = -a
print(ans)


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


N = int(input())
Ans = ''
while N != 0:
	Ans = str(N % 2) + Ans
	N = (N - N % 2) // 2
	N *= -1
print(Ans if Ans != '' else 0)


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


import math
n = int(input())
ans = 0
i = 0
while n is not 0:
	if n % (-2) ** (i + 1):
		ans += 10 ** i
		n -= (-2) ** i
	i += 1
print(ans)


a = int(input())
b = []
if a == 0:
	print(0)
while a:
	b.append(a & 1)
	a -= a & 1
	a = int(a / -2)
print(''.join(map(str, b[::-1])))


n = int(input())
s = '1' if n % 2 == 1 else '0'
n = -n // -2
while n:
	mod = (n % 2) ** 2
	s = '{}'.format(mod) + s
	n = n // -2
print(s)


n = int(input())
ansl = []
if n != 0:
	while abs(n) > 0:
		if n % 2 == 0:
			ansl.append('0')
			n = n // -2
		else:
			ansl.append('1')
			n = (n - 1) // -2
	print(''.join(ansl[::-1]))
else:
	print(0)


n = -int(input())
ans = ''
for i in range(1000):
	ans += str(n % 2)
	n //= -2
	if n == 0:
		break
print(ans[::-1])


def main():
	n = int(input())
	s = []
	if n == 0:
		print(0)
		return
	while n != 1:
		if n % -2 == -1:
			n = n // -2 + 1
			s.append(1)
		else:
			s.append(0)
			n = n // -2
	s.append(n)
	s.reverse()
	print(''.join([str(x) for x in s]))

def __starting_point():
	main()
__starting_point()


N = int(input())
ans = ''
for _ in range(1000):
	r = N % 2
	if r < 0:
		r += 2
	N = (N - r) // -2
	ans = str(r) + ans
print(int(ans))


N = int(input())
if N == 0:
	print('0')
	return
ans = ''
while abs(N) > 0:
	if abs(N) % 2 == 0:
		ans += '0'
		N //= 2
	else:
		N -= 1
		N //= 2
		ans += '1'
	N *= -1
print(ans[::-1])


N = int(input())
S = ''
for i in range(50):
	if N % -2 == 0:
		S = '0' + S
	else:
		S = '1' + S
		N -= 1
	N = N // -2
print(int(S))


import sys
N = int(input())
if not N:
	print(0)
	sys.exit()
S = ''
while N:
	r = N % 2
	N = N // -2 + r
	S += str(r)
print(S[::-1])


import sys
N = int(sys.stdin.readline())
if N == 0:
	print(0)
	return
binN = ''
pN = abs(N)
while N != 0:
	if abs(N % -2) == 1:
		binN += '1'
	else:
		binN += '0'
	N += N % -2
	N //= -2
print(binN[::-1])


n = int(input())
(s, i) = (0, 0)
while n != 0:
	i += 1
	if n & 2 ** i - 1 != 0:
		s += 2 ** (i - 1)
		n -= (-2) ** (i - 1)
print(bin(s)[2:])


n = int(input())
s = ''
while n:
	s = str(n & 1) + s
	n = -(n >> 1)
print(s if s else 0)


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


n = int(input())
ans = str(n % 2)
n //= 2
while n:
	ans += str(n % 2)
	n //= -2
print(ans[::-1])


N = int(input())
r = []
x = 0
while N != 0:
	d = abs(N) % 2
	r.append(d)
	N = (N - d * (-1) ** x) // 2
	x += 1
print(*([0] if r == [] else r[::-1]), sep='')


N = int(input())
basis = [(-2) ** d for d in range(64)]
cs = [1, -2]
for i in range(2, len(basis)):
	cs.append(cs[i - 2] + basis[i])
S = ['0'] * len(basis)
n = N
max_i = 0
while n != 0:
	if n > 0:
		for i in range(0, len(basis), 2):
			if cs[i] >= n:
				S[i] = '1'
				n -= basis[i]
				max_i = max(max_i, i)
				break
	else:
		for i in range(1, len(basis), 2):
			if cs[i] <= n:
				S[i] = '1'
				n -= basis[i]
				max_i = max(max_i, i)
				break
print(''.join(S[:max_i + 1])[::-1])


n = int(input())
ans = ''
while abs(n) > 0:
	ans = str(n % 2) + ans
	n = -(n // 2)
print(ans or 0)


from math import ceil
n = int(input())
if n == 0:
	print(0)
	exit()
ans = ''
while n != 0:
	ans += str(abs(n) % 2)
	n = ceil(n / -2)
print(ans[::-1])


def mod(n):
	if n > 0:
		return (-(n // 2), n % 2)
	elif n < 0:
		return ((-n + 1) // 2, -n % 2)
	else:
		return (0, 0)

def main():
	N = int(input())
	if N == 0:
		print(0)
		return
	ANS = []
	while N != 0:
		(N, b) = mod(N)
		ANS.append(b)
	print(''.join(map(str, ANS[::-1])))

def __starting_point():
	main()
__starting_point()


n = int(input())
a = ''
while n:
	a = str(n % 2) + a
	n = (n - n % 2) // -2
print(a or 0)


import sys, math, collections, itertools
input = sys.stdin.readline
N = int(input())
s = []
if N == 0:
	print(0)
	return
while N:
	r = N % -2
	if r < 0:
		r += 2
	N = (N - r) // -2
	s.append(str(r))
print(''.join(s)[::-1])


import sys
read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007

def main():
	N = int(readline())
	ans = []
	while abs(N) > 0:
		ans.append(N % 2)
		N //= 2
		N *= -1
	if ans:
		ans = ''.join(map(str, reversed(ans)))
	else:
		ans = 0
	print(ans)
	return

def __starting_point():
	main()
__starting_point()


n = int(input())
if n == 0:
	print(0)
	return
d = []
while n != 0:
	p = n % 2
	d.append(p)
	n = (n - p) * -1 // 2
for u in reversed(d):
	print(u, end='')
print()