负二进制转换与负M进制转换

LeetCode原题“1017. 负二进制转换”：https://leetcode.cn/problems/convert-to-base-2/

给你一个整数 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

本题给出了负二进制的转换

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

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

即，a_0*(-2)^0 + a_1*(-2)^1 +... = n，其中ai在负二进制下为0或1，求a_i序列

答案：

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;
    }
};

// 作者：LeetCode-Solution

那么现在提问，进行扩展：

1. 如果需要转换为任意负M进制呢？
2. 如何同时支持正进制和负进制？

即，a_0*M^0 + a_1*M^1 +... = n，其中ai在负M进制下为0到-N-1，在正M进制下为0到N-1，求a_i序列

答案：

class Solution {
public:
    const int M = -2;
    string baseNeg2(int n) {
        if(n==0) return "0"s;
        string ans;
        while(n) {
            int remainder = n % toM;
            if(remainder<0) {
                // n=M*quotient+remainder
                // 当n为正数而M是负数时，n%M的结果remainder在大多数编程语言（c/c++/java）也是负数，remainder调回正数只需要-M（加上M的绝对值）
                // 同时为了保持n不变，商需要+1（M*quotient为更大的负）来抵消掉多出来的部分
                remainder-=M;
                n = n/M+1;
            } else {
                // 当余数恰好为0 或者 n和M同号（此时remainder为正），不需要任何处理
                n /= M;
            }
            ans.push_back('0' + remainder);
        }
        reverse(ans.begin(),ans.end());
        return ans;
    }
};

参考资料：

• C语言中四种取整方式,取余/取模运算以及负数取模问题详解
• 2020字节跳动面试算法题—十进制转负3进制

Donate