算法算术

负进制数与模负数

字数统计: 2.2k字   |   阅读时长: 9分
, ,

摘要: 负进制数与10进制的转换，模负数

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

在文章 进制转换 中，我们系统整理了 k 进制(k > 0)与十进制的互相转化，包括整数部分、小数部分。并且解决了一些力扣上的题目。

本文我们看一下当 k 为负数时，k 进制与十进制的互相转换问题。并解决力扣 1017、1073。

模负数

由于十进制转k (k < 0) 进制的算法流程中涉及到模负数的问题，因此这里简要看一下模负数怎么处理，

在 C++ 和 Python 中，对模负数 (a % p, 其中 p 不为零) 的处理是不一样的。以 $a = \pm 56236$，$p = \pm 371$ 为例，在 C++ 和 Python 中 a % p 的结果如下：

a = 56236 a = -56236
p = 371 c++: 215; python3: 215
56236=151*371+215		 c++: -215
(-56236)=(-151)*371+(-215) ;
python3: 156
(-56236)=(-152)*371+156
p = -371 c++: 215
56236=(-151)*(-371)+215;
python3: -156
56236=(-152)*(-371)+(-156)		 c++: -215; python3: -215
(-56236)=151*(-371)+(-215)

如果算法中涉及到模负数的计算，需要注意 C++ 和 Python 的区别，比如 10 进制转换为负进制的算法就会有模负数的问题。

十进制转k进制(k < 0)

题目

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

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

提示：

1
0 <= n <= 1e9

示例 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

题解

算法：短除法

回顾10进制转k进制，其中 $k > 0$ 为整数的算法，也就是短除法，可以参考：进制转换，下面是一个示意图：

短除法

1
2
3
4
5
6
while(N > 0)
{
    int r = N % base;
    result += '0' + r;
    N /= base;
}

但这里这里 base 为负数，涉及到两个问题：

  1. r = N % base，需要模负数
  2. N /= base，N 在迭代过程中会正负交替

第一个问题，通过查看前面的表格，可以看到 C++ 中，不论 N 的正负，模上互为相反数的两个数，结果是一样的，因此 N % K 可以直接写成 N % abs(K)。

但这里还涉及 N 的正负，因此需要按照 C++ 中对负数取模的处理方法：先将 N % MOD 加上 MOD 再对 MOD 取模，其中 MOD = abs(K)。

最终使得求出的 r，即加到答案里的那一位，为正数。

1
r = (N % abs(K) + abs(K)) % abs(K);

第二个问题：K < 0, N 在迭代过程中会正负交替。

回顾 K 为整数的时候的算法流程，按照公式 $N = \sum\limits_{p} a_{p}K^{p}$ 在迭代过程中，N /= K 这一步，实际隐含着两步，先把本轮加到答案里的数字，即 N / K 的余数减掉 N -= r，再除以 K(相当于 K 进制序列右移一位)。

比如 N = 13, K = 10，当前轮的余数 r = N % K = 3 为本轮放入答案的位，将这个 3 减掉 ，再将 N 右移一位，相当于原始 N 的 $rK^{p}$ 被减掉。这两步的结果在 N /= K 这一个运算中就直接得到了。

当 K < 0，如果当前迭代轮次对应的 N 是负数的话，本轮的 $rK^{p}$ 就会漏减掉(N -= r 没有隐含在 N /= K 中)，例如 N = -3, K = -2 时, r = 1, N / K = 1, (N - r) / K = 2。r 需要手动减掉。

代码(C++)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    string baseNeg2(int N) {
        if(N == 0) return "0";
        string result = "";
        int base = -2;
        while(N)
        {
            int r = abs(N) % abs(base);
            result += '0' + r;
            N -= r;
            N /= base;
        }
        reverse(result.begin(), result.end());
        return result;
    }
};

代码(Python3)

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def baseNeg2(self, N: int) -> str:
        if N == 0:
            return "0"
        result = ""
        base = -2
        while N != 0:
            r = abs(N) % abs(base)
            result += str(r)
            N -= r
            N //= base
        return result[::-1]

k进制转十进制(k < 0)

题目

1073. 负二进制数相加

给出基数为 -2 的两个数 arr1 和 arr2，返回两数相加的结果。

数字以 数组形式 给出：数组由若干 0 和 1 组成，按最高有效位到最低有效位的顺序排列。例如，arr = [1,1,0,1] 表示数字 (-2)^3 + (-2)^2 + (-2)^0 = -3。数组形式 中的数字 arr 也同样不含前导零：即 arr == [0] 或 arr[0] == 1。

返回相同表示形式的 arr1 和 arr2 相加的结果。两数的表示形式为：不含前导零、由若干 0 和 1 组成的数组。

示例 1：
输入：arr1 = [1,1,1,1,1], arr2 = [1,0,1]
输出：[1,0,0,0,0]
解释：arr1 表示 11，arr2 表示 5，输出表示 16 。

示例 2：
输入：arr1 = [0], arr2 = [0]
输出：[0]

示例 3：
输入：arr1 = [0], arr2 = [1]
输出：[1]

提示：

1
2
3
1 <= arr1.length, arr2.length <= 1000
arr1[i] 和 arr2[i] 都是 0 或 1
arr1 和 arr2 都没有前导0

题解

算法1：进制转换

将 arr1, arr2 转成十进制，再相加，再十进制转k进制(k=-2): python3 可以这么做, C++ 这么做需要实现大数类，太麻烦。

代码(python3)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
def baseNeg2(N: int) -> str:
    if N == 0:
        return "0"
    result = ""
    base = -2
    while N != 0:
        r = abs(N) % abs(base)
        result += str(r)
        N -= r
        N //= base
    return result[::-1]

class Solution:

    def addNegabinary(self, arr1: List[int], arr2: List[int]) -> List[int]:
        """
        :type arr1: List[int]
        :type arr2: List[int]
        :rtype: List[int]
        """
        base = -2

        num1 = 0
        for i, num in enumerate(arr1[::-1]):
            num1 += num * base ** i

        num2 = 0
        for i, num in enumerate(arr2[::-1]):
            num2 += num * base ** i

        S = num1 + num2
        result = baseNeg2(S)

        return [int(i) for i in result]

算法2: 负二进制按位加法

在文章 高精度运算组件 中，我们解决过一个正二进制加法的问题 67. 二进制求和。解决过程就是正确地读出两个数的每位二进制数字，然后一位一位地处理按位加法，记录相加后的结果，同事维护进位。

对于负二进制下的按位加法也一样，如果用 C++ 不想实现大整数类的话，需要就按 base = -2 情况下一位一位地处理每位数，记录相加后该位的结果放进答案，同时维护进位。

负二进制下按位加法，没有进位的情况是以下三种：

比较难的是进位部分 $1 \times (-2)^{n} + 1 \times (-2)^{n}$。关于进位的结论如下：

当累加项超过 1 时，进位项为 -1：

  • n 为偶数时，当前位是正的，1 + 1 的进位为 1，但进位到的 n + 1 是负的，与当前位相反，因此在 n + 1 这一位的进位反转一下变为 -1
  • n 为奇数时，当前位是负的，1 + 1 的进位为 1，但进位到的 n + 1 是正的，与当前位相反，因此在 n + 1 这一位的进位反转一下变为 -1

因为 carry 可能为负，因此 a + b + carry 可能为负的，此时进位项为 1：

  • n 为偶数时，当前位是正的，0 + (-1) 的进位为 -1，但进位到的 n + 1 是负的，与当前位相反，因此在 n + 1 这一位的进位反转一下变为 -1
  • n 为奇数时，当前位是负的，0 + (-1) 的进位为 -1，但进位到的 n + 1 是正的，与当前位相反，因此在 n + 1 这一位的进位反转一下变为 -1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
while(i1 < N1 || i2 < N2 || carry != 0)
{
    int c = carry;
    int a = 0, b = 0;
    if(i1 < N1) a = arr1[i1++];
    if(i2 < N2) b = arr2[i2++];
    int v = a + b - c;
    carry = 0;
    if(v > 1)
    {
        v -= 2;
        carry = 1;
    }
    else if(v < 0)
    {
        v += 2;
        carry = -1;
    }
    res.push_back(v);
}

代码 (C++)

  • a, b 取值范围均为 0, 1
  • carry 取值范围为 -1, 0, 1
  • a + b + carry 的范围： -1, 0, 1, 2, 3
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    vector<int> addNegabinary(vector<int>& arr1, vector<int>& arr2) {
        int N1 = arr1.size();
        int N2 = arr2.size();
        reverse(arr1.begin(), arr1.end());
        reverse(arr2.begin(), arr2.end());
        vector<int> res;
        int i1 = 0, i2 = 0;
        int carry = 0;
        while(i1 < N1 || i2 < N2 || carry != 0)
        {
            int c = carry;
            int a = 0, b = 0;
            if(i1 < N1) a = arr1[i1++];
            if(i2 < N2) b = arr2[i2++];
            int v = a + b - c;
            carry = 0;
            if(v > 1)
            {
                v -= 2;
                carry = 1;
            }
            else if(v < 0)
            {
                v += 2;
                carry = -1;
            }
            res.push_back(v);
        }
        auto it = res.end() - 1;
        while(it != res.begin() && *it == 0)
        {
            res.pop_back();
            --it;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
Share