题目描述

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

题意：给出数字 N，返回由若干 “0” 和 “1”组成的字符串，该字符串为 N 的负二进制（base -2）表示。

除非字符串就是 “0”，否则返回的字符串中不能含有前导零

算法1

题解：我们依然采用与正数进制一样的方法，只不过这里的余数必须为正数。但是当基数为负数的时候，我们的余数会出现负数的情况，因此我们可以将余数加上一个基数的绝对值保证其为正数，同时更新商为：（被除数-余数）/除数。

//适用于正负十以内的基数    
string baseK(int N,int k)
    {
        if(N == 0) return "0";
        vector<int> res;
        while(N != 0)
        {
            int r = ((N % k) + abs(k)) % abs(k);
            N = (N - r) / k;
            res.push_back(r);
        }
        string ans = "";
        for(int i = res.size() - 1 ; i >= 0 ; i --)
            ans += to_string(res[i]);
        return ans;        
    }
    string baseNeg2(int N) {
        return baseK(N,-2);
    }