[LeetCode] 1017. Convert to Base -2

[grandyang]

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，让转为以负二进制的数。我们对于十进制数转二进制的数字应该比较熟悉，就是每次 N%2 或者 N&1，然后再将N右移一位，即相当于除以2，直到N为0为止。对于转为负二进制的数字，也是同样的做法，唯一不同的是，每次要除以 -2，即将N右移一位之后，要变为相反数，参见代码如下：

解法一：

class Solution {
public:
    string baseNeg2(int N) {
        string res;
        while (N != 0) {
            res = to_string(N & 1) + res;
            N = -(N >> 1);
        }
        return res == "" ? "0" : res;
    }
};

由于转二进制数是要对2取余，则转负二进制就要对 -2 取余，然后N要除以 -2，但是有个问题是，取余操作可能会得到负数，但我们希望只得到0或1，这样就需要做些小调整，使其变为正数，变化方法是，余数加2，N加1，证明方法如下所示：

-1 = (-2) * 0 + (-1)
-1 = (-2) * 0 + (-2) + (-1) - (-2)
-1 = (-2) * (0 + 1) + (-1) - (-2)

先加上一个 -2，再减去一个 -2，合并后就是N加1，余数加2，这样就可以把余数加到结果字符串中了，参见代码如下：

解法二：

class Solution {
public:
    string baseNeg2(int N) {
        string res;
        while (N != 0) {
            int rem = N % (-2);
            N /= -2;
            if (rem < 0) {
                rem += 2;
                N += 1;
            }
            res = to_string(rem) + res;
        }
        return res == "" ? "0" : res;
    }
};

讨论：我们都知道对于一个正数来说，右移一位就相当于除以2，但是对于负数来说，右移一位却不等于除以2。比如 -3 除以2，等于 -1，但是右移一位却不等于 -1，-3 的八位的表示为 11111101，右移一位是 11111110，是 -2。

Github 同步地址:

#1017

类似题目：

Encode Number

参考资料：

https://leetcode.com/problems/convert-to-base-2/

https://leetcode.com/problems/convert-to-base-2/discuss/265544/C%2B%2B-Geeks4Geeks

https://leetcode.com/problems/convert-to-base-2/discuss/265507/JavaC%2B%2BPython-2-lines-Exactly-Same-as-Base-2

LeetCode All in One 题目讲解汇总(持续更新中...)