[Java/C++/Python] 2 lines, Exactly Same as Base 2
Please follow more detailed explanation in my channel on youtube.\n\n# Intuition\n1. Maybe write a base2 function first?\n2. How about add minus -?\n3. Done.\n\
Please follow more detailed explanation in my channel on youtube.\n\n# **Intuition**\n1. Maybe write a base2 function first?\n2. How about add minus `-`?\n3. Done.\n<br>\n\n# **Explanation**\nbase2 function is quite basis of basis.\n1. check last digit by `N%2` or `N&1`.\nIf it\'s 1, you get 1.\nIf it\'s 0, you get 0.\n\n2. shift to right `N >> 1`.\nThis actually do two things:\n2.1 Minus 1 if last digit is 1.\n2.2 Divide `N` by 2.\n\nbase -2 is no difference,\nexcept that we need divide `N` by -2.\n\nSo we do the same thing,\njust add a sign `-` after division.\n\nThe explanation seems not enough.\nBut if you **really understand** how we do the base2,\nyou will find just literally the same process.\n<br>\n\n# More about `N = -(N >> 1)` \nExplained by @yren2:\nIt\'s mostly implementation defined. and most compilers choose to preserve the sign by setting the most significant bits after the shift.\nfor example, -3 in 8-bit is 11111101 and -3>>1 is 11111110, which is -2. (round towards -inf)\n\nthis is **different** from -3/2, which is -1. (round towards 0)\nsame goes -3>>2 == -1 and -3/4 == 0.\n<br>\n\n# **Complexity**\nTime `O(logN)`\nSpace `O(logN)`\n\nNote that I didn\'t deal with string concatenation,\nand just take this part as `O(1)`.\n\nInstead of create a new string each time,\nwe can improve this process using some operations join/reverse or data structure list/vector .\nLike Java we may need `StringBuilder`,\nbut those are not what I want to discuss deeply here.\n<br>\n\n\n# **Solution 1: Iterative Solution**\n**Java**\n```java\n    public String base2(int N) {\n        StringBuilder res = new StringBuilder();\n        while (N != 0) {\n            res.append(N & 1);\n            N = N >> 1;\n        }\n        return res.length() > 0 ? res.reverse().toString() : "0";\n    }\n\n    public String baseNeg2(int N) {\n        StringBuilder res = new StringBuilder();\n        while (N != 0) {\n            res.append(N & 1);\n            N = -(N >> 1);\n        }\n        return res.length() > 0 ? res.reverse().toString() : "0";\n    }\n```\n**C++**\n```cpp\n    string base2(int N) {\n        string res = "";\n        while (N) {\n            res = to_string(N & 1) + res;\n            N = N >> 1;\n        }\n        return res == ""  ? "0" : res;\n    }\n\n    string baseNeg2(int N) {\n        string res = "";\n        while (N) {\n            res = to_string(N & 1) + res;\n            N = -(N >> 1);\n        }\n        return res == "" ? "0" : res;\n    }\n```\n**Python**\n```python\n    def base2(self, x):\n        res = []\n        while x:\n            res.append(x & 1)\n            x = x >> 1\n        return "".join(map(str, res[::-1] or [0]))\n\n    def baseNeg2(self, x):\n        res = []\n        while x:\n            res.append(x & 1)\n            x = -(x >> 1)\n        return "".join(map(str, res[::-1] or [0]))\n```\n\n<br>\n\n# **Solution 2: Recursive Solution**\n**Java:**\n```java\n    public String base2(int N) {\n        if (N == 0 || N == 1) return Integer.toString(N);\n        return base2(N >> 1) + Integer.toString(N & 1);\n    }\n\n    public String baseNeg2(int N) {\n        if (N == 0 || N == 1) return Integer.toString(N);\n        return baseNeg2(-(N >> 1)) + Integer.toString(N & 1);\n    }\n```\n**C++:**\n```cpp\n    string base2(int N) {\n        if (N == 0 || N == 1) return to_string(N);\n        return base2(N >> 1) + to_string(N & 1);\n    }\n\n    string baseNeg2(int N) {\n        if (N == 0 || N == 1) return to_string(N);\n        return baseNeg2(-(N >> 1)) + to_string(N & 1);\n    }\n```\n\n**Python:**\n```py\n    def base2(self, N):\n        if N == 0 or N == 1: return str(N)\n        return self.base2(N >> 1) + str(N & 1)\n\n    def baseNeg2(self, N):\n        if N == 0 or N == 1: return str(N)\n        return self.baseNeg2(-(N >> 1)) + str(N & 1)\n```\n<br>\n\n# More Solutions\n[Easy One Line](https://leetcode.com/problems/convert-to-base-2/discuss/287017/JavaPython-Easy-One-Line)
[]