负进制数与模负数

  |  

摘要: 负进制数与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