题目链接：1017. 负二进制转换
方法一：进制转换
解题思路
除基取余法，当基数 \(x\) 为负数时，注意将余数 \(c\) 取绝对值。重复操作，\(c = abs(n % x), n = (n - c) / x\)，直到 \(n = 0\)。
代码
class Solution {
public:
string baseNeg2(int n) {
if (n == 0) return "0";
string ans;
while (n) {
int c = abs(n % (-2));
ans = (c == 0 ? '0' : '1') + ans;
n = (n - c) / (-2);
}
return ans;
}
};
复杂度分析
时间复杂度：\(O(logn)\)；
空间复杂度：\(O(1)\)。
方法二：模拟进位
解题思路
先转为\(2\)进制数，再模拟进位的过程。
代码
class Solution {
public:
string baseNeg2(int n) {
if (n == 0) return "0";
string ans;
int cnt = 0;
while (n) { // 转为2进制
if (n & (1 << cnt)) {
ans = "1" + ans;
n ^= 1 << cnt;
} else {
ans = "0" + ans;
}
cnt ++ ;
}
n = ans.length();
int idx = 0, carry = 0; // 初始进位为0
while (idx < n) {
int cur = n - idx - 1;
if (ans[cur] == '1' && idx % 2 != 0 && !carry) { // 设置进位
carry = 1;
idx ++ ;
continue;
}
if (carry) { // 有进位时才进行更新
if (ans[cur] == '1') ans[cur] = '0';
else {
ans[cur] = '1';
if (idx % 2 == 0) carry = 0;
}
}
idx ++ ;
}
if (carry) { // 将结束时的进位加上
if (idx % 2 == 0) ans = '1' + ans;
else ans = "11" + ans;
}
return ans;
}
};
复杂度分析
时间复杂度：\(O(logn)\)；
空间复杂度：\(O(1)\)。