C++ simple solution | Defining base (-2) addition
\nclass Solution {\npublic:\n    string baseNeg2(int n) {\n        if(n == 0) return "0";\n        if(n == 1) return "1";\n        \n\t\tstring n_by_2 = baseNeg
```\nclass Solution {\npublic:\n    string baseNeg2(int n) {\n        if(n == 0) return "0";\n        if(n == 1) return "1";\n        \n\t\tstring n_by_2 = baseNeg2(n/2);\n        \n        // n is even => n = n/2 + n/2;\n        // n is odd => n = n/2 + n/2 + 1;\n        // now, we can solve the problem recursively, if we somehow manage to do the addition of two numbers in base (-2).\n       \n        // sum is the function defined below to do addition in base (-2).\n        string ans = sum(n_by_2, n_by_2);\n\t\t\n\t\t// if n is odd, add 1 to the result\n        if(n % 2) ans = sum(ans, "1");\n        \n        return ans;\n    }\n    \n    string sum(string &a, string b){\n        // reverse the number and append zero at the end of shorter one if needed.\n        reverse(a.begin(), a.end());\n        reverse(b.begin(), b.end());\n        \n        // Now, consider every single bit. Every single bit is 0 or 1. But both 0 and 1 means same in the base 2 and base -2 both. \n\t\t// So, bitwise we can do addition of number as like base 2.\n\t\t// But since base is changing the for every consecutive places, we need to flip the carry every time.\n        \n        int carry = 0, sum;\n        for(int i = 0; i < a.size(); i++){\n            sum = a[i]-\'0\' + b[i]-\'0\' + carry;\n            a[i] = (sum & 1) + \'0\';\n            carry = (sum >> 1);\n            carry = -carry;\n        }\n        \n        reverse(a.begin(), a.end());\n        \n        // if final carry is 1 => add 1 at the beggining of the result bcz in base (-2), 1 can be represented by 1.\n        // if final carry is -1 => add 11 at the beginning of the result, bcz in base (-2), -1 can be represented by 11.\n\t\t\n        if(carry == 1) a = "1"+a;\n        if(carry == -1) a = "11"+a;\n        \n        return a;\n    }\n};\n```\n
['Recursion']