? ? ? ?文章位操作实现加减乘除四则运算
? ? ? ?当整数很大，在计算机可以表示的范围内无法通过常规的加减等运算计算时，这里介绍的大数运算是一种有效的计算方法。
??????? 这里介绍一种方式：将大数表示为一个n进制的数组（分别将大数表示成十进制和N进制），介绍大数的加减乘三种运算。这里仅考虑了非负整数
一、将大数表示为10进制
使用C++
string AddLongInteger(string addend,string augend)
{
if(addend.size() < augend.size())
return AddLongInteger(augend,addend);
int i,j,temp,flag = 0;
for(i = addend.size() - 1,j = augend.size() - 1; i >= 0;i--,j--)
{
if(j >= 0)
temp = addend[i] - '0' + augend[j] - '0' + flag ;
else
temp = addend[i] - '0' + flag;
if(temp > 9)
{
flag = 1;
temp %= 10;
}
else flag = 0;
addend[i] = temp + '0';
}
if(flag)
addend = "1" + addend;
return addend;
}
int main()
{
string str1,str2;
cin >> str1 >> str2;
cout << AddLongInteger(str1,str2) << endl;
return 0;
}
单独的实现函数
大数加法
const int maxn = 1001;
void BigdataAdd() {
char data1_str[maxn],data2_str[maxn];
int data1[maxn] = {0},data2[maxn] = {0},data_sum[maxn] = {0}; //这里初始化为0很重要，之后计算依赖于初始值
int len_data1,len_data2,i;
scanf("%s",data1_str); //由控制台读入第一个char数组形式的大数
len_data1 = strlen(data1_str);
for (i = 0; i < len_data1; ++i) //将这个大数存入到int数组中，注意将char数组高位存入int数组地位，方便计算时对齐
data1[i] = data1_str[len_data1 - i - 1] - '0';
scanf("%s",data2_str);
len_data2 = strlen(data2_str);
for (i = 0; i < len_data2; i++)
data2[i] = data2_str[len_data2 - i - 1] - '0';
int max_len = len_data1 > len_data2 ? len_data1 : len_data2; //计算两个数中较大的长度值
int flag = 0; // flag：需要进位的值
for (i = 0; i < max_len; ++i) { //加法运算
data_sum[i] = (data1[i] + data2[i] + flag) % 10; //本位的数值
flag = (data1[i] + data2[i] + flag) / 10; //需要进位的数值
}
printf("Sum: ");
if (flag != 0) { //考虑最高位是否进位
data_sum[max_len] = 1;
printf("%d",data_sum[max_len]); //输出计算结果最高位
}
for (i = max_len - 1; i >= 0; --i) //输出计算结果其他位
printf("%d",data_sum[i]);
printf("n");
}
int main() {
BigdataAdd();
return 0;
}
输出结果（一）：
1
2
Sum: 3
请按任意键继续. . .
输出结果（二）：
大数减法：
void BigdataSubtraction() {
char data1_str[maxn],data2[maxn] = {0},data_sub[maxn] = {0}; //这里初始化为0很重要，之后计算依赖于初始值
int len_data1,len_data2;
scanf("%s",data1_str);
scanf("%s",data2_str);
len_data1 = strlen(data1_str);
len_data2 = strlen(data2_str);
int bigdata;
if (len_data1 > len_data2) //判断哪个数大，将该数作为被减数
bigdata = 1;
else if (len_data1 < len_data2)
bigdata = -1;
else
bigdata = strcmp(data1_str,data2_str);
int i;
if (bigdata >= 0) {
for (i = 0; i < len_data1; ++i)
data1[i] = data1_str[len_data1 - i - 1] - '0';
for (i = 0; i < len_data2; i++)
data2[i] = data2_str[len_data2 - i - 1] - '0';
}
else {
for (i = 0; i < len_data2; ++i)
data1[i] = data2_str[len_data2 - i - 1] - '0';
for (i = 0; i < len_data1; i++)
data2[i] = data1_str[len_data1 - i - 1] - '0';
}
int flag = 0; //flag表示借位
int max_len = len_data1 >= len_data2 ? len_data1 : len_data2;
for (i = 0; i < max_len; ++i) {
int this_sub = data1[i] - flag;
data_sub[i] = this_sub - data2[i];
if (data_sub[i] >= 0) {
flag = 0;
}
else {
flag = 1;
data_sub[i] += 10;
}
}
printf("Subtraction: ");
if (bigdata < 0) //如果输入的第一个数小，则为结果添加负号
printf("-");
while (max_len > 1 && !data_sub[max_len - 1])
max_len--;
for (i = max_len - 1; i >= 0; --i)
printf("%d",data_sub[i]);
printf("n");
}
输出结果（一）：
12
45
Subtraction: -33
请按任意键继续. . .
输出结果（二）：
大数乘法：
这里的乘法操作是比较完善的，考虑了数据输入非法、乘数为负数、乘数为0时的输出形式等情况。
string Mutiplication(const string data1,const string data2) {
if (data1 == "" || data2 == "") //非法输入
return "";
string result;
int length_data1 = data1.size();
int length_data2 = data2.size();
vector<int> result_number(length_data1 + length_data2 - 1,0);
//处理有负数的情况，data1为负数则data1_end等于1，data2为负数则data2_end等于1
int data1_end = 0,data2_end = 0;
if (data1[0] - '-' == 0 && data2[0] - '-' == 0) {
data1_end = 1;
data2_end = 1;
}
else if (data1[0] - '-' == 0)
data1_end = 1;
else if (data2[0] - '-' == 0)
data2_end = 1;
else {}
for (int i = length_data2 - 1; i >= data2_end; --i) {
for (int j = length_data1 - 1; j >= data1_end; --j) {
if (!isdigit(data1[j]) || !isdigit(data2[i])) {
cerr << "invalid number";
return "";
}
//result_number记录乘法过程中每一位
result_number[i + j] += (data2[i] - '0') * (data1[j] - '0');
}
}
//处理进位并将结果存到字符串result
int carry = 0;
for (int i = result_number.size() - 1; i >= 0; --i) {
result_number[i] += carry;
carry = result_number[i] / 10;
result = string(1,result_number[i] % 10 + '0') + result;
}
if (carry > 0) //最高位的进位
result = string(1,carry + '0') + result;
//下面几行处理有乘数为0的情况，如果不处理，会出现：
//1234 * 0 = 0000的情况
string::iterator iter = result.begin();
//如果乘法结果的前n - 1位为0，则将其删除，只保留最后一位
while (*iter - '0' == 0 && iter < result.end() - 1) {
iter = result.erase(iter);
}
//如果结果为负数则在结果字符串中添加负号
if (data1_end ^ data2_end)
result = "-" + result;
return result;
}
int main() {
string a;
string b;
while (cin >> a >> b)
cout << "result: " << Mutiplication(a,b) << endl;
}
以上C语言的实现方式只是做了几个单独的测试，各个函数间代码的重复率很高，没有整合，这里仅是给出了大整数运算的实现方法。本文第三部分给出了这部分代码的C++类实现方式。
二、将大数表示为N进制数组
??????? N的取值越大，数组大小越小，这样可以缩短运算时间以及空间复杂度，提高运算效率。在32位系统中，N可以取2的32次方，此时一位的大小为0~0xffffffff.
?????? 当进行加法和乘法运算会进位，则可能要判断溢出，因此，选用long long型(64位)。这里的运算思想和第一部分十进制的运算思想是一致的。
1. 加法运算：
??????? 运用”竖式计算“的思想，首先将两个操作数的低位对齐，如果本位所加的结果大于0xffffffff - 1才做进位（flag）处理，否则不进位。
计算0x12 0x2 + 0xffffffff 0xfffffff：
???? （1）个位：0x2 + 0xffffffff 大于0xfffffff，所以进位，本位结果为1，进位标志flag = 1；
???? （2）十位：0x12 + 0xffffffff + flag大于0xfffffff，所以进位，本位结果为12，flag = 1；
???? （3）计算第三位，两个加数均为0，进位为1，所以本位结果为1；
??????? 最终计算结果为1 12 1。
2.减法运算：
计算0x1 0x1 0x1 - 0xffffff：
????? （1）0x1 - 0xfffffff 小于0， 需要借位，本位为2；
????? （2）十位被个位借了1，因此本位结果为0；
????? （3）百位结果为1；
??????? 最终结果为102。
3. 乘法运算：
计算0x1 0x1 0x1 * 0xffffff 0xfffffff：
??????? （1）个位：0x1 0x1 0x1 * 0xffffffff = 0xffffffff0xffffffff0xffffffff；
??????? （2）十位：0x1 0x1 0x1 * 0xffffffff =0xffffffff0xffffffff0xffffffff，因为这是十位，所以结果为0xffffff0xffffff 0xffffff 0x0；
????????? 最终结果：0xffffffff0xffffffff0xffffffff 0x0 + 0xffffffff0xffffffff0xffffffff = 1 0 0xffffffff?0xfffffffe0xffffffff。
三、第一部分的C++实现：
const int maxn = 1001;
class BigData {
?? ?int len;
?? ?int data[maxn];
?? ?BigData Sub(const BigData& a,const BigData& b) {
?? ??? ?int i;
?? ??? ?BigData result;
?? ??? ?int flag = 0;
?? ??? ?for (i = 0; i < a.len; ++i) {
?? ??? ??? ?int this_sub = a.data[i] - flag;
?? ??? ??? ?result.data[i] = this_sub - b.data[i];
?? ??? ??? ?if (result.data[i] >= 0)
?? ??? ??? ??? ?flag = 0;
?? ??? ??? ?else {
?? ??? ??? ??? ?flag = 1;
?? ??? ??? ??? ?result.data[i] += 10;
?? ??? ??? ?}
?? ??? ??? ?result.len = a.len;
?? ??? ?}
?? ??? ?result.clean();
?? ??? ?return result;
?? ?}
?? ?void clean() {
?? ??? ?while (len > 1 && !data[len - 1])
?? ??? ??? ?len--;
?? ?}
?? ?string str() const {
?? ??? ?string res = "";
?? ??? ?int i;
?? ??? ?for (i = 0; i < len; i++)
?? ??? ??? ?res = (char)(data[i] + '0') + res;
?? ??? ?if (res.empty())
?? ??? ??? ?res = "0";
?? ??? ?return res;
?? ?}
public:
?? ?BigData() {
?? ??? ?memset(data,sizeof(data));
?? ??? ?len = 1;
?? ?}
?? ?BigData(int num) {
?? ??? ?*this = num;
?? ?}
?? ?BigData(const char* num) {
?? ??? ?*this = num;
?? ?}
?? ?BigData& operator=(int num) {
?? ??? ?char data[maxn];
?? ??? ?sprintf(data,"%d",num);
?? ??? ?*this = data;
?? ??? ?return *this;
?? ?}
?? ?BigData& operator=(const char *num) {
?? ??? ?len = strlen(num);
?? ??? ?int i;
?? ??? ?for (i = 0; i < len; ++i)
?? ??? ??? ?data[i] = num[len - i - 1] - '0';
?? ??? ?return *this;
?? ?}
?? ?BigData operator+(const BigData& b) const {
?? ??? ?BigData c;
?? ??? ?c.len = 0;
?? ??? ?int i,flag = 0;
?? ??? ?int max_len = len > b.len ? len : b.len;
?? ??? ?for (i = 0; i < max_len; ++i) {
?? ??? ??? ?int sum = (flag + data[i] + b.data[i]);
?? ??? ??? ?c.data[c.len++] = sum % 10;
?? ??? ??? ?flag = sum / 10;
?? ??? ?}
?? ??? ?if (flag != 0)
?? ??? ??? ?c.data[c.len++] = 1;
?? ??? ?c.clean();
?? ??? ?return c;
?? ?}
?? ?BigData& operator+=(const BigData& b) {
?? ??? ?*this = *this + b;
?? ??? ?return *this;
?? ?}
?? ?
?? ?BigData& operator-=(const BigData& b) {
?? ??? ?*this = *this - b;
?? ??? ?return *this;
?? ?}
?? ?bool operator<(const BigData& b) const {
?? ??? ?if (len != b.len)
?? ??? ??? ?return len < b.len;
?? ??? ?int i;
?? ??? ?for (i = len - 1; i >= 0; --i) {
?? ??? ??? ?if (data[i] != b.data[i])
?? ??? ??? ??? ?return data[i] < b.data[i];
?? ??? ?}
?? ??? ?return false;
?? ?}
?? ?bool operator>(const BigData& b) const {
?? ??? ?return b < *this;
?? ?}
?? ?bool operator<=(const BigData& b) const {
?? ??? ?return !(*this > b);
?? ?}
?? ?bool operator>=(const BigData& b) const {
?? ??? ?return !(*this < b);
?? ?}
?? ?bool operator==(const BigData& b) const {
?? ??? ?return !(*this > b) && !(*this < b);
?? ?}
?? ?BigData operator-(const BigData& b) {
?? ??? ?BigData c;
?? ??? ?c.len = 0;
?? ??? ?if (*this == b) {
?? ??? ??? ?c.data[++c.len] = 0;
?? ??? ??? ?return c;
?? ??? ?}
?? ??? ?else if (*this > b) {
?? ??? ??? ?c = Sub(*this,b);
?? ??? ?}
?? ??? ?else {
?? ??? ??? ?c = Sub(b,*this);
?? ??? ??? ?c.data[c.len++] = '-' - '0';
?? ??? ?}
?? ??? ?return c;
?? ?}
?? ?BigData operator*(const BigData& b) {
?? ??? ?int i,flag;
?? ??? ?BigData result;
?? ??? ?for (i = 0; i < len; ++i) {
?? ??? ??? ?for (j = 0; j < b.len; ++j) {
?? ??? ??? ??? ?result.data[i + j] = data[i] * b.data[j];
?? ??? ??? ?}
?? ??? ?}
?? ??? ?result.len = len + b.len;
?? ??? ?for (i = 0; i <result.len; ++i) {
?? ??? ??? ?result.data[i + 1] += result.data[i] / 10;
?? ??? ??? ?result.data[i] %= 10;
?? ??? ?}
?? ??? ?result.clean();
?? ??? ?return result;
?? ?}
?? ?friend ostream& operator<<(ostream& out,const BigData& bd) {
?? ??? ?out << bd.str();
?? ??? ?return out;
?? ?}
?? ?friend istream& operator>>(istream& in,BigData& bd) {
?? ??? ?string s;
?? ??? ?in >> s;
?? ??? ?bd = s.c_str();
?? ??? ?return in;
?? ?}
};
int main() {
?? ?BigData a,b;
?? ?cin >> a >> b;
?? ?cout << "a: " << a << endl;
?? ?cout << "b: " << b << endl;
?? ?cout << "a+b: " << a + b<< endl;
?? ?cout << "a-b: " << a - b << endl;
?? ?cout << "a*b: " << a * b << endl;
?? ?a += b;
?? ?cout << "a += b: " << a << endl;
?? ?a -= b;
?? ?cout << "a -= b: " << a << endl;
?? ?return 0;
}
输出结果：
