> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/math/1017.-convert-to-base-2.md).

# 1017. Convert to Base -2

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`

```cpp
string baseNeg2(int N) {
    string res;
    while (N) {
        cout << "N: " << N << endl;
        res = to_string(N & 1) + res;
        // -x = ~x + 1
        N = -(N >> 1);
    }
    return res.empty() ? "0" : res;
}
```

```cpp
string baseNeg2(int N) {
    string res;
    int rem = 0;
    while (N) {
        rem = N % -2;
        N /= -2;
        if (rem < 0) {
            rem -= (-2);
            N += 1;
        }
        res = to_string(rem) + res;
    }
    return res.empty() ? "0" : res;
}
```