【1017. 负二进制转换】

来源：力扣（LeetCode）

描述：

给你一个整数 n ，以二进制字符串的形式返回该整数的 负二进制（base -2）表示。

注意， 除非字符串就是 "0"，否则返回的字符串中不能含有前导零。

示例 1：

输入：n = 2
输出："110"
解释：(-2)2 + (-2)1 = 2

示例 2：

输入：n = 3
输出："111"
解释：(-2)2 + (-2)1 + (-2)0 = 3

示例 3：

输入：n = 4
输出："100"
解释：(-2)2 = 4

提示：

• 0 <= n <= 10⁹

方法一：模拟进位

思路与算法

对于「二进制数」我们可以很直观地得到以下结论：

• 对于 2ⁱ，如果 i 为偶数时，此时 2ⁱ = (−2)ⁱ；
• 对于 2ⁱ，如果 i 为奇数时，此时 2ⁱ = (−2)ⁱ⁺¹ + (−2)ⁱ；

因此自然可以想到将 n 转换为 −2 的幂数和，即此时 n= ${\sum }_{i=0}^m$ C×(−2)ⁱ，由于 −2 进制的每一位只能为 0 或 1，需要对每一位进行加法「进位」运算即可得到完整的「负二进制」数。对于「负二进制」数，此时需要思考一下进位规则。对于 C×(−2)ⁱ，期望得到如下变换规则：

• 如果 C 为奇数则需要将等式变为 C × (−2)ⁱ = a × (−2)ⁱ⁺¹ + (−2)ⁱ，此时第 i 位为 1，第 i + 1 位需要加上 a；

• 如果 C 为偶数则需要将等式变为 C × (−2)ⁱ = a × (−2)ⁱ⁺¹ ，此时第 i 位为 0，第 i + 1 位需要加上 a；

根据以上的变换规则，只需要求出 a 即可。假设当前数位上的数字为 val，当前的位上保留的余数为 r，在 x 进制下的进位为 a，根据「进位」的运算规则可知 val = a × x + r，此时可以得到进位 a = $\frac{val-r}{x}$。根据题意可知，「负二进制」数的每一位上保留的余数为 0 或 1，因此可以计算出当前的余数 r，由于在有符号整数的均采用补码表示，最低位的奇偶性保持不变，因此可以直接取 val 的最低位即可，此时可以得到 r = val & 1。根据上述等式可以知道，当前数位上的数字为 val 时，此时在「负二进制」下向高位的进位为 a = $\frac{val-(val\&1)}{-2}$ 。
基于以上进位规则，将变换出来的数列进行进位运算即可得到完整的「负二进制」数。整个转换过程如下：

• 将 n 转换为二进制数，并将二进制数中的每一位转换为「负二进制」中的每一位，变换后的数列为 bits；
• 将 bits 从低位向高位进行「进位」运算，即将 bits 中的每一位都变为 0 或者 1；
• 去掉前导 0 以后，将 bits 转换为字符串返回即可。

代码：

class Solution {
public:string baseNeg2(int n) {if (n == 0) {return "0";}vector<int> bits(32);for (int i = 0; i < 32 && n != 0; i++) {if (n & 1) {bits[i]++;if (i & 1) {bits[i + 1]++;}}n >>= 1;}int carry = 0;for (int i = 0; i < 32; i++) {int val = carry + bits[i];bits[i] = val & 1;carry = (val - bits[i]) / (-2);}int pos = 31;string res;while (pos >= 0 && bits[pos] == 0) {pos--;}while (pos >= 0) {res.push_back(bits[pos] + '0');pos--;}return res;}
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.9 MB, 在所有 C++ 提交中击败了33.33%的用户
复杂度分析
时间复杂度：O( C )，其中 C = 32。需要对 n 转换为二进制位，需要的时间复杂度为 O(logn)，然后需要对其进行二进制位的中每一位进行「负二进制进位」运算，由于整数有 32 位，因此需要「负二进制进位」运算 32 次即可。
空间复杂度：O( C )，其中 C = 32。需要对 n 转换为二进制位，由于整数最多只有 32 位，在此每次采取固定的存储空间为 O(32)。

方法二：进制转换

思路与算法

当基数 x > 1 时，将整数 n 转换成 x 进制的原理是：令 n₀ = n，计算过程如下:

• 当计算第 0 位上的数字时，此时 n₁ = ⌊ $\frac{n_0}{x}$⌋，n₀ = n₁ × x + r，其中 0 ≤ r < x；
• 当计算第 i 位上的数字时，此时 n_i+1 = ⌊ $\frac{n_i}{x}$ ⌋，n_i = n_i+1 × x + r，其中 0 ≤ r < x；

按照上述计算方式进行计算，直到满足 nⁱ = 0 结束。

如果基数 x 为负数，只要能确定余数的可能取值，上述做法同样适用。由于「负二进制」表示中的每一位都是 0 或 1，因此余数的可能取值是 0 和 1，可以使用上述做法将整数 n 转换成「负二进制」。具体转换过程如下：

• ​如果 n = 0 则返回 “0"，n = 1 则直接返回 “1"；
• 如果 n > 1 则使用一个字符串记录余数，将整数 n 转换成「负二进制」，重复执行如下操作，直到 n = 0；
  • 计算当前 n 的余数，由于当前的余数只能为 0 或 1，由于有符号整数均采用补码表示，最低位的奇偶性保持不变，因此可以直接取 C 的最低位即可，此时直接用 n&1 即可得到最低位的余数，将余数拼接到字符串的末尾。
  • 将 n 的值减去余数，然后将 n 的值除以 −2。

上述操作结束之后，将字符串翻转之后得到「负二进制」数。

代码：

class Solution {
public:string baseNeg2(int n) {if (n == 0 || n == 1) {return to_string(n);}string res;while (n != 0) {int remainder = n & 1;res.push_back('0' + remainder);n -= remainder;n /= -2;}reverse(res.begin(), res.end());return res;}
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.8 MB, 在所有 C++ 提交中击败了75.00%的用户
复杂度分析
时间复杂度：O(logn)，其中 n 是给定的整数。整数 n 对应的「负二进制」表示的长度是 logn，需要生成「负二进制」表示的每一位。
空间复杂度：O(1)。除返回值外，不需要额外的空间。

方法三：数学计算

思路与算法

根据题意可知，32 位「负二进制」数中第 i 位则表示(−2)ⁱ，当 i 为偶数时，则 (−2)ⁱ = 2ⁱ，当 i 为奇数时，则 (−2)ⁱ = −2ⁱ ，因此可以得到其最大值与最小值分别为如下：

• 最大值即所有的偶数位全部都为 1，奇数位全为 0，最大值即为 0x55555555 = 1,431,655,765；
• 最小值即所有的偶数位全部都为 0，奇数位全为 1，最小值即为 0xAAAAAAAA = −2,863,311,530；
• 0x55555555, 0xAAAAAAAA 均为「十六进制」进制原码表示；

令 maxVal = 0x55555555，由于题目中 n 给定的范围为 0 ≤ n ≤ 10⁹，因此一定满足 maxVal > n。设 maxVal 与 n 的差为 diff，则此时 diff = maxVal − n，如果我们将 maxVal 在「负二进制」表示下减去 diff，那么得到的「负二进制」一定为 n 的「负二进制」。已知 maxVal 中的偶数位全为 1，奇数位全为 0，此时的减法操作可以用异或来实现:

• 对于 diff 中偶数位为 1 的位，在 maxVal 中需要将其置为 0，此时 maxVal 中偶数位全部为 1，1 ⊕ 1 = 0，偶数位异或操作即可将需要的位置为 0；
• 对于 diff 中奇数位为 1 的位，在 maxVal 中需要将其置为 1，此时 maxVal 中奇数位全部为 0，0 ⊕ 1 = 1，奇数位异或操作将需要的位置为 1，
  根据以上推论可以知道，「负二进制」减法等同于 maxVal ⊕ diff。按照上述方法可以知道 n 的「负二进制」数等于 ma x Val ⊕ (maxVal − n)，我们求出 n 的「负二进制」数，然后将其转换为二进制的字符串即可。

代码：

class Solution {
public:string baseNeg2(int n) {int val = 0x55555555 ^ (0x55555555 - n);if (val == 0) {return "0";}string res;while (val) {res.push_back('0' + (val & 1));val >>= 1;}reverse(res.begin(), res.end());return res;}
};

执行用时：0 ms, 在所有 C++ 提交中击败了100.00%的用户
内存消耗：5.7 MB, 在所有 C++ 提交中击败了98.15%的用户
复杂度分析
时间复杂度：O(logn)，其中 n 是给定的整数。整数 n 对应的「负二进制」表示的长度是 logn，需要生成「负二进制」表示的每一位。
空间复杂度：O(1)。除返回值外，不需要额外的空间。
author：LeetCode-Solution