output_description: Print the base -2 representation of N.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
attempt: #! /usr/bin/env python3
  
  n = int(input())
  
  v = []
  
  tmp_n = n
  plus = 0
  
  if tmp_n < 0:
      plus = 1
      tmp_n *= -1
  
  while tmp_n > 0:
      v.append(tmp_n & 1)
      tmp_n = tmp_n >> 1
  
  r = [0 for _ in range(len(v) + 10)]
  for i in range(len(v)):
      if i % 2 == plus:
          r[i] += v[i]
      else:
          r[i] += v[i]
          r[i + 1] += v[i]
  
  for i in range(len(r)):
      while r[i] >= 2 and r[i + 1] >= 1:
          r[i] -= 2
          r[i + 1] -= 1
      while r[i] >= 2:
          r[i + 1] += 1
          r[i + 2] += 1
          r[i] -= 2
  
  started = False
  res = ""
  for i in range(len(r)):
      idx = len(r) - 1 - i
      if r[idx] == 1:
          res = res + "1"
          started = True
      elif started == True:
          res = res + "0"
  
  if res == "":
      res = "0"
  print(res)
  
problem_description: 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.
samples: [{"input": "-9", "output": "1011\n    \n\nAs (-2)^0 + (-2)^1 + (-2)^3 = 1 + (-2) + (-8) = -9, `1011` is the base -2\nrepresentation of -9.\n\n* * *"}, {"input": "123456789", "output": "11000101011001101110100010101\n    \n\n* * *"}, {"input": "0", "output": "0"}]