【Leetcode】1017. Convert to Base -2

题目地址：

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

给定一个非负整数$n$，将其转为$-2$进制的数，以字符串形式输出。

如果$n=0$则直接返回"0"。设$n=a_k(-2{)}^k+...+a_0(-2{)}^0$，那么当$n$是奇数的时候$a_0=1$，否则$a_0=0$，算出$a_0$之后，则$$(n-a_0)/(-2)=a_k(-2{)}^{k-1}+...+a_1(-2{)}^0$$依次再继续求$a_1,...,a_k$即可。可以证明这个过程一定会终止。代码如下：

class Solution {
 public:
  string baseNeg2(int n) {
    if (!n) return "0";
    string s;
    while (n) {
      s += to_string(n & 1);
      n -= n & 1;
      n /= -2;
    }
    reverse(s.begin(), s.end());
    return s;
  }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

时间复杂度$O(\log n)$，空间$O(1)$。