# ---
# title: 1017. Convert to Base -2
# id: problem1017
# author: Tian Jun
# date: 2020-10-31
# difficulty: Medium
# categories: Math
# link: <https://leetcode.com/problems/convert-to-base-2/description/>
# hidden: true
# ---
# 
# 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:**
# 
#   1. `0 <= N <= 10^9`
# 
# 
## @lc code=start
using LeetCode

function base_neg2(N::Int)
    cnt = 0
    res = ""
    while N > 0
        bit = (N & 1)
        N -= bit * (-1) ^ cnt
        N >>= 1
        cnt += 1
        res = string(bit) * res
    end
    res
end
## @lc code=end
