高精度算法 (加减乘除-四则)

前言

int b = 2 + 3;
这样的常规操作谁都会,你竟然单独写一篇博客教我这个,哈哈哈,笑死我了

😃😃😃 其实不然,我让你算一下这个试试:

1
int c = 99999999999999999999999999999999999999 + 99999999999999999999999999999999999999;

这时,你就会发现,这个运算量已经超过 int 类型 -2,147,483,648 到 2,147,483,647 的范围了,怎么办呢?
别急,往下看 😁

前期准备

自然我们需要做一些防错措施
例如:判断拿到的数据是否满足要求,所以下面的代码是接下来每个算法(加减乘除…)必须的

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
41
42
43
44
45
46
47
48
49
50
/// <summary>
/// 检查字符串是否每一个字符都是数字
/// </summary>
public static bool Check_IsAllNum(string p)
{
char[] arr = p.ToCharArray();
for (int i = 0; i < arr.Length; i++)
{
int unmatchNum = 0;
for (int q = 0; q < TextHelper.Text.Numbers.Length; q++)
{
if (arr[i] != TextHelper.Text.Numbers[q])
{
unmatchNum++;
}
}
if (unmatchNum == 10)
{
return false;
}
}
return true;
}

/// <summary>
/// Char 数组 转 Int 数组
/// </summary>
public static int[] CharArrayToIntArray(char[] u)
{
int[] rst = new int[u.Length];
for (int i = 0; i < rst.Length; i++)
{
rst[i] = Convert.ToInt32(u[i]);
}
return rst;
}

/// <summary>
/// 字符串转 Int 数组
/// </summary>
public static int[] StringToIntArray(string p)
{
char[] t = p.ToCharArray();
int[] rst = new int[t.Length];
for (int i = 0; i < rst.Length; i++)
{
rst[i] = Convert.ToInt32(t[i].ToString());
}
return rst;
}

高精度加法

自写,不支持小数点

思路

啊,首先我们要先思考一个问题: 既然 int 类型(包括其他大部分能直接运算的类型)装不下这么大的数,选用类型来装呢?
嘿,这么长的数字其实对于字符串而言就是一句话的事情,所以 string 类型不正好吗

那么拿到要运算的 string 类型的数据,接下来怎么办呢?

你可能会理所当然地想到小学学过的竖式
就像这样

1
2
3
4
   67
+ 3
------
= 70

那么如果我们把两个加数像竖式那样逐位相加,那么问题就被转化成了每上下两位之间10之内的加法,再把最后计算的结果当作一个 string 返回
这样就解决了前言中所说的问题。

再来理一遍思路:

  1. 拿到string类型的两个加数
  2. 逐位拆解两个加数
  3. 逐位相加两个加数,并把计算结果存到一个临时数组里
  4. 把临时数组装回一个string并返回

好,现在理清了思路,接下来就是实现这个算法

注:在实际的编写中,得到的两个加数的位数不一定相等,于是你要把两个加数补成长度相等的再进行运算,对应下面代码的 FillPosition() 方法

代码

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
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
/// <summary>
/// 将两个 字符数组 互相补位
/// </summary>
public static string[] FillPosition(char[] m, char[] n)
{
char[][] rst = new char[2][];

int big_length = ((m.Length - n.Length) >= 0) ? m.Length : n.Length;
char[] m1 = new char[big_length];
char[] n1 = new char[big_length];
if (big_length == m.Length)
{
for (int i = 0; i < m.Length; i++)
{
m1[i] = m[i];
}
int delta = m.Length - n.Length;
for (int i = 0; i < big_length; i++)
{
if (i < delta)
{
n1[i] = '0';
}
else
{
n1[i] = n[i - delta];
}
}
}
else
{
for (int i = 0; i < n.Length; i++)
{
n1[i] = n[i];
}
int delta = n.Length - m.Length;
for (int i = 0; i < big_length; i++)
{
if (i < delta)
{
m1[i] = '0';
}
else
{
m1[i] = m[i - delta];
}
}
}
rst[0] = m1; rst[1] = n1;

string[] result = new string[2];
string r1 = "";
for (int i = 0; i < rst[0].Length; i++)
{
r1 += rst[0][i];
}
string r2 = "";
for (int i = 0; i < rst[1].Length; i++)
{
r2 += rst[1][i];
}
result[0] = r1; result[1] = r2;
return result;
}

/// <summary>
/// 补位
/// </summary>
public static string[] FillPosition(string m, string n) => FillPosition(m.ToCharArray(), n.ToCharArray());

/// <summary>
/// 获取个位
/// </summary>
public static int GetUnit(int num) => Convert.ToInt32(num.ToString().ToCharArray()[num.ToString().ToCharArray().Length - 1].ToString());

/// <summary>
/// 高精度加法 不支持小数点
/// </summary>
public static string Sum(string a, string b)
{
if (Check_IsAllNum(a) && Check_IsAllNum(b))
{
string result = "";
string[] coverd = FillPosition(a, b);

int[] a1 = StringToIntArray(coverd[0]), b1 = StringToIntArray(coverd[1]);

int[] tmp = new int[a1.Length + 1];

bool cb = false; // carry-bit 进位
for (int i = a1.Length - 1; i >= 0; i--)
{
int l = a1[i], r = b1[i];
tmp[i + 1] = cb ? GetUnit(l + r) + 1 : GetUnit(l + r);
cb = l + r > 9;
}
if (cb)
{
tmp[0] = 1;
}

for (int i = 0; i < tmp.Length; i++)
{
result += tmp[i].ToString();
}

return result;
}
else
{
return null;
}
}

支持小数点的算法

因为这个不是我自己写的,所以没有思路
52342534 - MSDN 转载

代码

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
41
42
43
44
45
46
47
48
49
50
static void Main(string[] args)
{
string change;
string num1 = Console.ReadLine();
string num2 = Console.ReadLine();
int[] n1 = new int[num1.Length];
int[] n2 = new int[num2.Length];
for (int i = 0; i < num1.Length; i++) {
change = num1[i].ToString();
n1[i] = int.Parse(change);
}
for (int i = 0; i < num2.Length; i++)
{
change = num2[i].ToString();
n2[i] = int.Parse(change);
}
if (num1.Length > num2.Length)
{
for (int i = 0; i < num2.Length; i++)
{
n1[num1.Length - i-1] += n2[num2.Length - i-1];
}
for (int i = n1.Length-1; i > 0; i--) {
if (n1[i] >= 10) {
n1[i - 1]++;
n1[i] %= 10;
}
}
foreach (int x in n1)
{
Console.Write(x);
}
}
else {
for (int i = 0; i < num1.Length; i++) {
n2[num2.Length - i - 1] += n1[num1.Length - i - 1];
}
for (int i = n2.Length-1; i > 0; i--) {
if (n2[i] >= 10) {
n2[i - 1]++;
n2[i] %= 10;
}
}
foreach (int x in n2) {
Console.Write(x);
}
}

Console.Read();
}

高精度减法

思路

暂时没有,等更新吧

高精度乘法

思路

所谓乘法,例如 a × b 其实就是 a 个 b 相加
那么问题就明确了,我们只需循环 a 次 并利用上面已经写好的高精度加法来累加 b
但是这样就有一个问题,循环该怎么处理呢,毕竟如果 a 也是一个极大的数,for 循环就不可用了,那么我们只能回归基础的 while 循环

代码

还没写好 QAQ 😂

高精度除法

觉得写的好的,打个赏呗 😘