<p>Given an integer <code>n</code>, return <em>a binary string representing its representation in base</em> <code>-2</code>.</p>

<p><strong>Note</strong> that the returned string should not have leading zeros unless the string is <code>&quot;0&quot;</code>.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> n = 2
<strong>Output:</strong> &quot;110&quot;
<strong>Explantion:</strong> (-2)<sup>2</sup> + (-2)<sup>1</sup> = 2
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> n = 3
<strong>Output:</strong> &quot;111&quot;
<strong>Explantion:</strong> (-2)<sup>2</sup> + (-2)<sup>1</sup> + (-2)<sup>0</sup> = 3
</pre>

<p><strong class="example">Example 3:</strong></p>

<pre>
<strong>Input:</strong> n = 4
<strong>Output:</strong> &quot;100&quot;
<strong>Explantion:</strong> (-2)<sup>2</sup> = 4
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>0 &lt;= n &lt;= 10<sup>9</sup></code></li>
</ul>

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

/* string base2(int n) {
    string ans = "";
    while(n) {
        ans = to_string(n & 1) + ans;
        n = n >> 1;
    }
    return ans == "" ? "0" : ans;
} */
// Intuition
// Maybe write a base2 function first?
// How about add minus -?
// Done.
// Explanation
// base2 function is quite basis of basis.

// check last digit by N%2 or N&1.
// If it's 1, you get 1.
// If it's 0, you get 0.

// shift to right N >> 1.
// This actually do two things:
// 2.1 Minus 1 if last digit is 1.
// 2.2 Divide N by 2.

// base -2 is no difference,
// except that we need divide N by -2.

// So we do the same thing,
// just add a sign - after division.

// The explanation seems not enough.
// But if you really understand how we do the base2,
// you will find just literally the same process.


// More about N = -(N >> 1)
// Explained by @yren2:
// It's mostly implementation defined. and most compilers choose to preserve the sign by setting the most significant bits after the shift.
// for example, -3 in 8-bit is 11111101 and -3>>1 is 11111110, which is -2. (round towards -inf)

// this is different from -3/2, which is -1. (round towards 0)
// same goes -3>>2 == -1 and -3/4 == 0.


// Complexity
// Time O(logN)
// Space O(logN)

// Note that I didn't deal with string concatenation,
// and just take this part as O(1).

// Instead of create a new string each time,
// we can improve this process using some operations join/reverse or data structure list/vector .
// Like Java we may need StringBuilder,
// but those are not what I want to discuss deeply here.

8900