文档章节

C/C++高精度运算(大整数运算)详解(含压位)

o
 osc_mervd488
发布于 2018/04/22 22:50
字数 1205
阅读 0
收藏 0
c++

精选30+云产品,助力企业轻松上云!>>>

1.高精度加法

1.1 高精度加法

        高精度运算的基本运算就是加和减。和算数的加减规则一样, 模拟竖式计算,考虑错位运算与进位处理。下面是我老师给的代码,目前比网上其他的代码要精简和巧妙。

#include <cstdio>
#include <cstring>
int main()
{
	char a[202]={0}, b[202]={0};
	scanf("%s%s", a, b);
	int alen = strlen(a), blen = strlen(b), t = 0, i;
	int a1[202]={0}, b1[202]={0};
	for (i = 0; i < alen; i++)	a1[i] = a[alen-1-i]-'0';
	for (i = 0; i < blen; i++)	b1[i] = b[blen-1-i]-'0';
	alen = (alen > blen) ? alen : blen;
	for (i = 0; i <= alen; i++)
	t = a1[i]+b1[i], a1[i] = t%10, a1[i+1] += t/10;
	while (!a1[i] && i) i--;
	for(; i >= 0; i--) printf("%d", a1[i]);
    return 0;
}

1.2高精度加法(压位)

        int型可以存9位数字,而上述代码在数组的每个元素中只存了0-9中的一位数,可以说浪费了很多空间,而且计算机计算4+5和3333+4444用的时间是相同的,所以我们有时候用压位来节省空间和时间。其原理如下:

  • 从键盘读入大整数并存放在字符数组
  • 从后向前每八位数字存放在一个int型数组的一个元素
  • 对俩个数组的对应元素进行加减运算,有进位要进位,最后输出

以下是我老师给的代码:

#include <iostream>
#include <cstring>
#include <cstdio> 
using namespace std;
const int INF = 1E8;
struct Data{
	int u[50], l;
	Data(){
		memset(u, 0, sizeof(u)), l = 0;
	}
	void change(string a){
		int len = a.size(), k = len / 8, i = 0;
		l = k + (len%8 > 0);
		for (len; len > 8; len -= 8)
			sscanf(a.substr(len-8, 8).c_str(), "%d", &u[i++]);//注释一
		if (len > 0) sscanf(a.substr(0, len).c_str(), "%d", &u[i]);
	}
	void print(){
		int k = l-1;
		printf("%d", u[k--]);
		while (k >= 0) printf("%8.8d", u[k--]);//注释二
		printf("\n");
	}
}a, b;
int main(){
	string aa, bb, ac;
	cin >> aa >> bb;
	int ka = 0, kb = 0, i;
	a.change(aa), b.change(bb);
	for (i = 0; i < 50; i++)
		a.u[i] += b.u[i], a.u[i+1] += a.u[i] / INF, a.u[i] %= INF;
	for (i = 49; a.u[i]==0 && i>0; i--);
	a.l = i + 1;
	a.print();
	return 0;
}

2.高精度减法

2.1 高精度减法

        原理和加法一样,需要不过考虑的不是进位,而是借位

代码如下:

#include <cstdio>
#include <cstring>
int main()
{
	char a[202]={0}, b[202]={0};
	scanf("%s%s", a, b);
	int alen = strlen(a), blen = strlen(b), t = 0, i;
	int a1[202]={0}, b1[202]={0};
	for (i = 0; i < alen; i++)	a1[i] = a[alen-1-i]-'0';
	for (i = 0; i < blen; i++)	b1[i] = b[blen-1-i]-'0';
	alen = (alen > blen) ? alen : blen;
	for (i = 0; i <= alen; i++)
	t = a1[i]-b1[i], t<0?(t+=10,a1[i+1]--):t, a1[i] = t;
	while (!a1[i] && i) i--;
	for(; i >= 0; i--) printf("%d", a1[i]);
    return 0;
}

2.2 高精度减法(压位)

        减法和加法大同小异,如果你会了加法,那么减法也不足为惧。以下代码是我自己写的,和我老师写的有一定差距,如有不足请指出。

#include <iostream>
#include <cstring>
#include <cstdio> 
using namespace std;
const int INF = 1E8;
struct Data{
	int u[50], l;
	Data(){
		memset(u, 0, sizeof(u)), l = 0;
	}
	void change(string a){
		int len = a.size(), k = len / 8, i = 0;
		l = k + (len%8 > 0);
		for (len; len > 8; len -= 8)
			sscanf(a.substr(len-8, 8).c_str(), "%d", &u[i++]);
		if (len > 0) sscanf(a.substr(0, len).c_str(), "%d", &u[i]);
	}
	void print(){
		int k = l-1;
		printf("%d", u[k--]);
		while (k >= 0) printf("%8.8d", u[k--]);
		printf("\n");
	}
}a, b;
int main(){
	string aa, bb, ac;
	cin >> aa >> bb;
	int ka = 0, kb = 0, i,t;
	a.change(aa), b.change(bb);
	for (i = 0; i < 50; i++)
		t = a.u[i] - b.u[i],(t < 0)?(t+=INF,a.u[i+1]--):t,a.u[i] = t; 
	for (i = 49; a.u[i]==0 && i>0; i--);
	a.l = i + 1;
	a.print();
	return 0;
}
以上的俩个代码都只能当且仅当a>=b时才能正常工作,望注意。

3.高精度乘法

3.1 高精度乘法

        这个方法出自吴永辉老师。此代码简直让我拍手叫绝。

原理如下:

                        3    2    1    0                    ——>数组a、b的下标

                        3    4    5    6       i            ——>数组a[]

                    *  1    2    7    8       j            ——>数组b[]

               ————————————

                 2    7    6    4    8 

            2    4    1    9    2

            6    9    1    2

      3    4    5    6

——————————————————

      4    4    1    6    7    6    8                ——>数组c[]

      6    5    4    3    2    1    0        i+j    ——>数组c的下标

以上是俩个四位数相乘的竖式计算方法。可以看出,数的右面对齐,从低位向高位计算,计算结束后将一列结果相加即为答案。那么把俩个数从右向左依次标记为0、1、2...n,那么每一列的结果就是第一个数的下标为i的数与第二个数的下标为j的数相乘的结果,其存放在第i+j列。最终结果是每一列相加,就是i+j这一列所有数相加。所以可以用c[i+j] += a[i]*b[j]。

for(int i = 0;i < LA-1;i++)
for(int j = 0;j < LB-1;j++)
	c[i+j] += a[i]*b[j];
for(int i = 0;i < LA+LB;i++)
if(c[i] >= 10){
	c[i+1] += c[i]/10;
	c[i] %= 10; 
}

3.2 高精度乘法(压位)

o
粉丝 0
博文 500
码字总数 0
作品 0
私信 提问
加载中
请先登录后再评论。

暂无文章

linux下java环境搭建

1、jdk下载: 官方地址:https://www.oracle.com/java/technologies/javase/javase-jdk8-downloads.html 如下图所示,我这边选择的是红框中的版本 2、压缩包上传至服务器 将下载的压缩包上传...

wc_飞豆
32分钟前
17
0
面试题:Java对象不再使用时,为什么要赋值为null?

前言 许多Java开发者都曾听说过“不使用的对象应手动赋值为null“这句话,而且好多开发者一直信奉着这句话;问其原因,大都是回答“有利于GC更早回收内存,减少内存占用”,但再往深入问就回...

码农突围
34分钟前
22
0
设计模式(5) 原型模式

原型模式 原型模式的适用场景 浅拷贝 深拷贝 用Initialize方法修改初始化状态 原型模式与之前学习的各种工厂方法、单例模式、建造者模式最大、最直观的区别在于,它是从一个既有的对象“克隆...

zhixin9001
34分钟前
7
0
获取免费的pycharm激活码网站

http://www.lookdiv.com/

云烟成雨forever
34分钟前
27
0
用Helm部署Kubernetes应用,支持多环境部署与版本回滚

1 前言 Helm是优秀的基于Kubernetes的包管理器。利用Helm,可以快速安装常用的Kubernetes应用,可以针对同一个应用快速部署多套环境,还可以实现运维人员与开发人员的职责分离。现在让我们安...

南瓜慢说
36分钟前
12
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部