本文涉及知识点

数学

LeetCode1017. 负二进制转换

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。
注意，除非字符串就是 “0”，否则返回的字符串中不能含有前导零。
示例 1：
输入：n = 2
输出：“110”
解释：(-2)² + (-2)1 = 2
示例 2：
输入：n = 3
输出：“111”
解释：(-2)² + (-2)¹ + (-2)⁰ = 3
示例 3：
输入：n = 4
输出：“100”
解释：(-2)² = 4

提示：
0 <= n <= 10⁹

数学

函数f(n)的返回n的-2进制的字符串形式。
{ " " n 是 0 f ( n / − 2 ) + " 0 " n 是偶数 f ( ( n − 1 ) / 2 ） + “ 1 ” n 是奇数 \begin{cases} "" && n是0\\ f(n/-2)+"0" && n是偶数 \\ f((n-1)/2）+“1” && n是奇数\\ \end{cases} ⎩ ⎨ ⎧​""f(n/−2)+"0"f((n−1)/2）+“1”​​n是0n是偶数n是奇数​
如： f(4) = f(-2)0 = f(1)00 = f(0)100=100
f(3) = f(-1)1 = f(1)11 = f(0)111=111
f(2) = f(-1)0 = f(1)10 = f(0)110=110

原理

除最低位外，其它都是-2的倍数，故如果n偶数，最低位为0；否则为1。余下的部分为: n或n-1。由于各位都是-2的倍数，故除以-2就是，除掉最低位后剩余的部分。
如果本题的n是0，直接返回"0"，而不是空。

代码

核心代码

class Solution {
		public:
			string baseNeg2(int n) {
				if (0 == n) { return "0"; }
				return F(n);
			}
			string F(int n) {
				if (0 == n) { return ""; }
				if (1 & n) { return F((n - 1) / -2) + "1"; }
				return F(n / -2) + "0";
			}
		};

单元测试

TEST_METHOD(TestMethod1)
		{
			auto res = Solution().baseNeg2(2);
			AssertEx(string("110"), res);
		}
		TEST_METHOD(TestMethod2)
		{
			auto res = Solution().baseNeg2(3);
			AssertEx(string("111"), res);
		}
		TEST_METHOD(TestMethod3)
		{
			auto res = Solution().baseNeg2(4);
			AssertEx(string("100"), res);
		}
		TEST_METHOD(TestMethod4)
		{
			auto res = Solution().baseNeg2(0);
			AssertEx(string("0"), res);
		}