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:

0 <= N <= 10^9

解题思路

与转二进制类似

实现代码

// Runtime: 1 ms, faster than 97.49% of Java online submissions for Convert to Base -2.
// Memory Usage: 36.9 MB, less than 100.00% of Java online submissions for Convert to Base -2.
class Solution {
    public String baseNeg2(int N) {
        String res = "";
        while (N != 0) {
            //res = Integer.toString(N & 1) + res;
            res = (N & 1) + res;
            N = - (N >> 1);
        }
        
        return res == "" ? "0" : res;
    }
}