首页 > 其他分享 >大整数运算

大整数运算

时间：2024-09-09 11:13:20浏览次数：12  
标签：BigInteger 运算 int digit 整数 length answer remainder

首先是遇到了1017 A除以B，稀里糊涂地复制了别人的答案就将其抛在脑后（偶然事件），紧接着就遇到了1022 D进制的A+B，这时突然记起学习要有打破砂锅问到底的精神，根本不是因为发现这个问题逃避不了，开始了对这个知识点的研究学习。

  • 取余运算

    取余就是取模，可以将其转换为对字符串中的最低数位进行取模运算。

  • 整除运算

    对于整除运算，需要重新写一个函数来完成字符串的除法功能。
    实现字符串除法函数的做法和日常在纸上实现除法的做法是一样的，即把字符中从商到低逐位除以除数。如界某位不能整除，那么就保留它除以除数的余数，余数乘以 10 后和低一位一起进行处理。这样，就能模拟出除法的效果，但这种做法可能会前置多余的 0，这时只需取首个非0位之后的字符串，便可得到想要的结果。

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>
using namespace std;

int toBinary(unsigned int n) {//被转换十进制数在int范围内
	vector<int> binary;//用vector装，跟用数组装都一样
	while (n != 0) {//一直除，直到等于零
		binary.push_back(n % 2);//将取模的值压进vector
		n /= 2;//数字也除进制数
	}
	for (int i = binary.size() - 1; i >= 0; i--)
		cout << binary[i];//由于采用头插法，数字是倒着的，需逆序输出
	cout << endl;
}

/*
* 当被转换数字只能用长字符串表示时，同样地，对此字符串不断进行对2取模和对2整除运算。不同的是，
* 1. 对于取模运算，可以将其转换为对字符串中的最低数位进行取模运算。
* 2. 对于整除运算，需要重新写一个函数来完成字符串的除法功能。实现字符串除法函数的做法和日常在纸上实现除法的做法是一样的，即把字符中从商到低逐位除以除数。
*    如界某位不能整除，那么就保留它除以除数的余数，余数乘以 10 后和低一位一起进行处理。这样，就能模拟出除法的效果，但这种做法可能会前置多余的 0，这时只需取首个
*	 非0位之后的字符串，便可得到想要的结果。
*/

string Divide(string s, int x) {//整除运算函数
	int remainder = 0;
	for (int i = 0; i < s.size(); ++i) {
		int current = remainder * 10 + s[i] - '0';
		s[i] = current / x + '0';
		remainder = current % x;
	}
	int pos = 0;
	while (s[pos] == '0')
		pos++;
	return s.substr(pos);
}

int main() {
	

	return 0;
}

上面也就看一乐，接下来是书上的代码，书上成为高精度整数，Java中有BigInteger类可以直接用，这里给出一系列模板。注意这个模板只适用于运算数和运算结果均为正整数的运算，否则会出错。

const int MAXN = 10000;//定义常量MAXN表示最大位数，即最多能表示的数字位数

struct BigInteger {
	int digit[MAXN];//用于存储大整数的每一位数字
	int length;//表示大整数的位数
	BigInteger();//⭐
	BigInteger(int x);//构造函数，接受一个整数 x 并将其转换为大整数类型
	BigInteger(string str);//⭐构造函数，接受一个字符串 str，并将其转换为大整数类型
	BigInteger(const BigInteger& b);//构造函数，接受另外一个大整数类型的对象 b，并将其复制为新的大整数类型
	BigInteger operator=(int x);//重载赋值运算符，将一个整数类型的值赋值给大整数类型对象
	BigInteger operator=(string str);//重载赋值运算符，将一个字符串类型的值赋值给大整数类型对象
	BigInteger operator=(const BigInteger& b);//重载赋值运算符，将另外一个大整数类型的对象赋值给当前对象
	bool operator <= (const BigInteger& b);//判断当前大整数类型对象是否小于等于另外一个大整数类型对象
	bool operator == (const BigInteger& b);//判断当前大整数类型对象是否等于另外一个大整数类型对象
	BigInteger operator+(const BigInteger& b);//重载加法运算符，实现大整数的 + 法
	BigInteger operator-(const BigInteger& b);//重载减法运算符，实现大整数的 - 法
	BigInteger operator*(const BigInteger& b);//重载乘法运算符，实现大整数的 * 法
	BigInteger operator/(const BigInteger& b);//重载除法运算符，实现大整数的 / 法
	BigInteger operator%(const BigInteger& b);//重载取模运算符，实现大整数取模
	friend istream& operator>>(istream& in, BigInteger& x);//⭐重载输入运算符，用于将用户输入的字符串或整数转换为大整数类型
	friend ostream& operator<<(ostream& out, const BigInteger& x);//⭐重载输出运算符，用于输出大整数类型对象
};//该结构体的作用是用于实现大整数的基本运算，方便用户直接进行大整数的计算

istream& operator>>(istream& in, BigInteger& x) {//
	string str;
	in >> str;
	x = str;
	return in;
}

ostream& operator<<(ostream& out, const BigInteger& x) {
	for (int i = x.length - 1; i >= 0; --i)
		out << x.digit[i];
	return out;
}

BigInteger::BigInteger() {
	memset(digit, 0, sizeof(digit));
	length = 0;
}

BigInteger::BigInteger(int x) {
	memset(digit, 0, sizeof(digit));
	length = 0;
	if (x == 0) digit[length++] = x;
	while (x != 0) {
		digit[length++] = x % 10;
		x /= 10;
	}
}

BigInteger::BigInteger(string str){
	memset(digit, 0, sizeof(digit));
	length = str.size();
	for (int i = 0; i < length; ++i)
		digit[i] = str[length - i - 1] - '0';
}

BigInteger::BigInteger(const BigInteger& b){
	memset(digit, 0, sizeof(digit));
	length = b.length;
	for (int i = 0; i < length; ++i)
		digit[i] = b.digit[i];
}

BigInteger BigInteger::operator=(int x)
{	memset(digit, 0, sizeof(digit));
	length = 0;
	if (x == 0) digit[length++] = x;
	while (x) {
		digit[length++] = x % 10;
		x /= 10;
	}
	return *this;
}

BigInteger BigInteger::operator=(string str){
	memset(digit, 0, sizeof(digit));
	length = str.size();
	for (int i = 0; i < length; ++i)
		digit[i] = str[length - i - 1] - '0';
	return *this;
}

BigInteger BigInteger::operator=(const BigInteger& b){
	memset(digit, 0, sizeof(digit));
	length = b.length;
	for (int i = 0; i < length; ++i)
		digit[i] = b.digit[i];
	return *this;
}

bool BigInteger::operator<=(const BigInteger& b){
	if (length < b.length) return true;
	else if (length > b.length) return false;
	else
		for (int i = length - 1; i >= 0; --i) {
			if (digit[i] == b.digit[i]) continue;
			else return digit[i] < b.digit[i];
		}
	return true;
}

bool BigInteger::operator==(const BigInteger& b){
	if (length != b.length) return false;
	else
		for (int i = length - 1; i >= 0; --i)
			if (digit[i] != b.digit[i]) return false;
	return true;
}

BigInteger BigInteger::operator+(const BigInteger& b){
	BigInteger answer;
	int carry = 0;
	for (int i = 0; i < length || i < b.length; ++i) {
		int current = carry + digit[i] + b.digit[i];
		carry = current / 10;
		answer.digit[answer.length++] = current % 10;
	}
	if (carry != 0) answer.digit[answer.length++] = carry;
	return answer;
}

BigInteger BigInteger::operator-(const BigInteger& b){
	BigInteger answer;
	int carry = 0;
	for (int i = 0; i < length; ++i) {
		int current = digit[i] - b.digit[i] - carry;
		if (current < 0) {
			current += 10;
			carry = 1;
		}
		else {
			carry = 0;
		}
		answer.digit[answer.length++] = current;
	}
	while (answer.digit[answer.length] == 0 && answer.length > 1)
		answer.length--;
	return answer;
}

BigInteger BigInteger::operator*(const BigInteger& b){
	BigInteger answer;
	answer.length = length + b.length;
	for (int i = 0; i < length; ++i)
		for (int j = 0; j < b.length; ++j)
			answer.digit[i + j] += digit[i] * b.digit[j];
	for (int i = 0; i < answer.length; ++i) {
		answer.digit[i + 1] += answer.digit[i] / 10;
		answer.digit[i] %= 10;
	}
	while (answer.digit[answer.length] == 0 && answer.length > 1)
		answer.length--;
	return answer;
}

BigInteger BigInteger::operator/(const BigInteger& b){
	BigInteger answer;
	answer.length = length;
	BigInteger remainder = 0, temp = b;
	for (int i = length - 1; i >= 0; --i) {
		if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
			for (int j = remainder.length - 1; j >= 0; --j)
				remainder.digit[j + 1] = remainder.digit[j];
			remainder.length++;
		}
		remainder.digit[0] = digit[i];
		while (temp <= remainder) {
			remainder = remainder - temp;
			answer.digit[i]++;
		}
	}
	while (answer.digit[answer.length] == 0 && answer.length > 1)
		answer.length--;
	return answer;
}

BigInteger BigInteger::operator%(const BigInteger& b){
	BigInteger remainder = 0;
	BigInteger temp = b;
	for (int i = length - 1; i >= 0; --i) {
		if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
			for (int j = remainder.length - 1; j >= 0; --j)
				remainder.digit[j + 1] = remainder.digit[j];
			remainder.length++;
		}
		remainder.digit[0] = digit[i];
		while (temp <= remainder)
			remainder = remainder - temp;
	}
	return remainder;
}

画⭐的是必写的模板，其他的需要用到才写。

真不知道怎么错的，但是A+B的D进制这一题就是没对。跟书写的一样了，但是不理解代码，只能机械地对比，可能书上也有小错误，但是我没发现了。

#include<iostream>
#include<algorithm>
#include<string.h>
#include<string>
#include<math.h>
#include<vector>

using namespace std;

const int MAXN = 10000;//定义常量MAXN表示最大位数，即最多能表示的数字位数

struct BigInteger {
	int digit[MAXN];//用于存储大整数的每一位数字
	int length;//表示大整数的位数
	BigInteger();
	BigInteger(int x);//构造函数，接受一个整数 x 并将其转换为大整数类型
	BigInteger(string str);//构造函数，接受一个字符串 str，并将其转换为大整数类型
	BigInteger(const BigInteger& b);//构造函数，接受另外一个大整数类型的对象 b，并将其复制为新的大整数类型
	BigInteger operator=(int x);//重载赋值运算符，将一个整数类型的值赋值给大整数类型对象
	BigInteger operator=(string str);//重载赋值运算符，将一个字符串类型的值赋值给大整数类型对象
	BigInteger operator=(const BigInteger& b);//重载赋值运算符，将另外一个大整数类型的对象赋值给当前对象
	bool operator <= (const BigInteger& b);//判断当前大整数类型对象是否小于等于另外一个大整数类型对象
	bool operator == (const BigInteger& b);//判断当前大整数类型对象是否等于另外一个大整数类型对象
	bool operator != (const BigInteger& b);
	BigInteger operator+(const BigInteger& b);//重载加法运算符，实现大整数的 + 法
	BigInteger operator-(const BigInteger& b);//重载减法运算符，实现大整数的 - 法
	BigInteger operator*(const BigInteger& b);//重载乘法运算符，实现大整数的 * 法
	BigInteger operator/(const BigInteger& b);//重载除法运算符，实现大整数的 / 法
	BigInteger operator%(const BigInteger& b);//重载取模运算符，实现大整数取模
	friend istream& operator>>(istream& in, BigInteger& x);//重载输入运算符，用于将用户输入的字符串或整数转换为大整数类型
	friend ostream& operator<<(ostream& out, const BigInteger& x);//重载输出运算符，用于输出大整数类型对象
};//该结构体的作用是用于实现大整数的基本运算，方便用户直接进行大整数的计算

istream& operator>>(istream& in, BigInteger& x) {//
	string str;
	in >> str;
	x = str;
	return in;
}

ostream& operator<<(ostream& out, const BigInteger& x) {
	for (int i = x.length - 1; i >= 0; --i)
		out << x.digit[i];
	return out;
}

BigInteger::BigInteger() {
	memset(digit, 0, sizeof(digit));
	length = 0;
}

BigInteger::BigInteger(int x) {
	memset(digit, 0, sizeof(digit));
	length = 0;
	if (x == 0) digit[length++] = x;
	while (x != 0) {
		digit[length++] = x % 10;
		x /= 10;
	}
}

BigInteger::BigInteger(string str){
	memset(digit, 0, sizeof(digit));
	length = str.size();
	for (int i = 0; i < length; ++i)
		digit[i] = str[length - i - 1] - '0';
}

BigInteger::BigInteger(const BigInteger& b){
	memset(digit, 0, sizeof(digit));
	length = b.length;
	for (int i = 0; i < length; ++i)
		digit[i] = b.digit[i];
}

BigInteger BigInteger::operator=(int x)
{	memset(digit, 0, sizeof(digit));
	length = 0;
	if (x == 0) digit[length++] = x;
	while (x != 0) {
		digit[length++] = x % 10;
		x /= 10;
	}
	return *this;
}

BigInteger BigInteger::operator=(string str){
	memset(digit, 0, sizeof(digit));
	length = str.size();
	for (int i = 0; i < length; ++i)
		digit[i] = str[length - i - 1] - '0';
	return *this;
}

BigInteger BigInteger::operator=(const BigInteger& b){
	memset(digit, 0, sizeof(digit));
	length = b.length;
	for (int i = 0; i < length; ++i)
		digit[i] = b.digit[i];
	return *this;
}

bool BigInteger::operator<=(const BigInteger& b){
	if (length < b.length) return true;
	else if (length > b.length) return false;
	else
		for (int i = length - 1; i >= 0; --i) {
			if (digit[i] == b.digit[i]) continue;
			else return digit[i] < b.digit[i];
		}
	return true;
}

bool BigInteger::operator==(const BigInteger& b){
	if (length != b.length) return false;
	else
		for (int i = length - 1; i >= 0; --i)
			if (digit[i] != b.digit[i]) return false;
	return true;
}

bool BigInteger::operator!=(const BigInteger& b){
	if (length != b.length) return true;
	else
		for (int i = length - 1; i >= 0; --i)
			if (digit[i] != b.digit[i]) return true;
	return false;
}

BigInteger BigInteger::operator+(const BigInteger& b){
	BigInteger answer;
	int carry = 0;
	for (int i = 0; i < length || i < b.length; ++i) {
		int current = carry + digit[i] + b.digit[i];
		carry = current / 10;
		answer.digit[answer.length++] = current % 10;
	}
	if (carry != 0) answer.digit[answer.length++] = carry;
	return answer;
}

BigInteger BigInteger::operator-(const BigInteger& b){
	BigInteger answer;
	int carry = 0;
	for (int i = 0; i < length; ++i) {
		int current = digit[i] - b.digit[i] - carry;
		if (current < 0) {
			current += 10;
			carry = 1;
		}
		else {
			carry = 0;
		}
		answer.digit[answer.length++] = current;
	}
	while (answer.digit[answer.length] == 0 && answer.length > 1)
		answer.length--;
	return answer;
}

BigInteger BigInteger::operator*(const BigInteger& b){
	BigInteger answer;
	answer.length = length + b.length;
	for (int i = 0; i < length; ++i)
		for (int j = 0; j < b.length; ++j)
			answer.digit[i + j] += digit[i] * b.digit[j];
	for (int i = 0; i < answer.length; ++i) {
		answer.digit[i + 1] += answer.digit[i] / 10;
		answer.digit[i] %= 10;
	}
	while (answer.digit[answer.length] == 0 && answer.length > 1)
		answer.length--;
	return answer;
}

BigInteger BigInteger::operator/(const BigInteger& b){
	BigInteger answer;
	answer.length = length;
	BigInteger remainder = 0, temp = b;
	for (int i = length - 1; i >= 0; --i) {
		if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
			for (int j = remainder.length - 1; j >= 0; --j)
				remainder.digit[j + 1] = remainder.digit[j];
			remainder.length++;
		}
		remainder.digit[0] = digit[i];
		while (temp <= remainder) {
			remainder = remainder - temp;
			answer.digit[i]++;
		}
	}
	while (answer.digit[answer.length] == 0 && answer.length > 1)
		answer.length--;
	return answer;
}

BigInteger BigInteger::operator%(const BigInteger& b){
	BigInteger remainder = 0;
	BigInteger temp = b;
	for (int i = length - 1; i >= 0; --i) {
		if (!(remainder.length == 1 && remainder.digit[0] == 0)) {
			for (int j = remainder.length - 1; j >= 0; --j)
				remainder.digit[j + 1] = remainder.digit[j];
			remainder.length++;
		}
		remainder.digit[0] = digit[i];
		while (temp <= remainder)
			remainder = remainder - temp;
	}
	return remainder;
}

int main() {
	BigInteger a, b, d;
	cin >> a >> b >> d;
	BigInteger n = a + b;
	vector<BigInteger> jieguo;
	if (d == 10) {
		cout << n << endl; return 0;
	}
	while (n != 0) {
		cout << n % d << "这是取余\n";
		jieguo.push_back(n % d);
		cout << n << "这是n\n";
		cout << d << "这是d\n";
		n = n / d;
		cout << n << "这是除法\n";
	}
	for (int i = jieguo.size() - 1; i >= 0; --i) {
		cout << jieguo[i];
	}
	cout << endl;
	return 0;
}

标签：BigInteger,运算,int,digit,整数,length,answer,remainder
From： https://www.cnblogs.com/themoonforget/p/17973409

相关文章

  • Java基础—运算符篇（从0到1完整详解，附有代码+案例）
    文章目录运算符分类：2.1.算术运算符2.1.1基本算数运算2.1.2复合算数运算2.1.3类型转换2.1.4“+”的三种情况2.2自增自减运算符2.3赋值运算符2.4关系运算符2.5逻辑运算符2.6短路逻辑运算符2.7三元运算符2.8运算的优先级运算符分类：赋值运算符：=算术运算符：+-......
  • 南沙信奥赛C++陈老师解一本通题: 1326：【例7.5】 取余运算（mod）
    ​【题目描述】【输入】输入b，p，k的值。【输出】【输入样例】2109【输出样例】2^10mod9=7 #include<iostream>#include<stdlib.h>usingnamespacestd;longlongb,p,k,ans=1;intmain(){ cin>>b>>p>>k; for(inti=1;i<=p;i++) { ans*=b;......
  • 南沙信奥赛C++陈老师解一本通题: 1171：大整数的因子
    ​ 【题目描述】已知正整数k满足2≤k≤9，现给出长度最大为30位的十进制非负整数c，求所有能整除c的k。【输入】一个非负整数c，c的位数≤30。【输出】若存在满足 c%k==0的k，从小到大输出所有这样的k，相邻两个数之间用单个空格隔开；若没有这样的k，则输出"none"。【输入样......
  • 【算法笔记】位运算详解
    0.前言突然想到位运算是个好东西，就来水一波文章了……注意：我把能想到的有关位运算的所有内容都放进来了，所以篇幅较长，请谅解！若有写的不清楚或者不够详细的地方欢迎在评论区补充，谢谢支持！本文中参考代码均使用C++编写。废话不多说，下面步入正题。1.基本运算有一定基础的可以......
  • Scala的基本运算
    Scala是一种多范式的编程语言，它支持多种类型的运算，包括算术运算、关系运算、逻辑运算、位运算以及赋值运算。以下是这些基本运算的简要概述： 算术运算：基本的算术运算符包括加法（+）、减法（-）、乘法（*）、除法（/）和取模（%）。这些运算符可以对数值类型进行操作。例如，3+2结果为5，3-2......
  • 二,PyCharm软件的使用,Python运算符,变量的介绍与运用,以及本章综合测试
    学习：知识的初次邂逅复习：知识的温故知新练习：知识的实践应用目录一,本章知识简介二,PyCharm软件的使用1,修改背景颜色和字体大小2,软件界面的使用3,PyCharm的常用快捷键三,Python运算符1,Python中常见的运算符有哪些？2,算术运算符如何运用?3,赋值运算符如何运用?4,......
  • Java中的整数移位运算符
    对于<<,>>两种运算符，可以这样说：\(a<<b=a*2^b\)\(a>>b=a/2^b\)但是对于>>>...不好说了。这些位运算在计算机中怎样运算的？大家都知道，整数在计算机中是以二进制存储的：\(0=(0)_2\)\(4=(100)_2\)\(8=(1000)_2\)\(20=(10100)_2\)\(666=(1010011010)_2\)左移（<<......
  • 1-5java运算符
    Java运算符计算机的最基本用途之一就是执行数学运算，作为一门计算机语言，java也提供了一套的运算符来操纵变量。我们可以把运算符分成以下几组：算术运算符关系运算符位运算符逻辑运算符赋值运算符其他运算符算术运算符算术运算符用在数学表达式中，它们的作用和数学中的作......
  • 整数在内存中的存储（含整型提升的详解）
    整数在内存中的存储整数的2进制表示法有三种，即：原码、反码和补码有符号的整数，三种表示方法均有符号位和数值位两部分，符号位都是用0表示“正”，用1表示“负”，最高位的⼀位是被当做符号位，剩余的都是数值位。           正整数的原、反、补码都相同。      ......
  • 【重学 MySQL】十七、比较运算符的使用
    【重学MySQL】十七、比较运算符的使用**等于（`=`）**基本用法示例注意事项结论**安全等于运算符（`<=>`）****不等于（`<>`或`!=`）**示例注意事项**大于（`>`）、大于等于（`>=`）、小于（`<`）、小于等于（`<=`）**大于（`>`）示例大于等于（`>=`）示例小于（`<`）示例小于等于（`<=`）示例**`......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99