C 语言实现大整数加减乘除运算
/**
- @file biginteger.c
- @brief 大整数的加减乘除等基本运算
- @author AI
- @date 2020年7月21日 */
#include <stdio.h> #include <stdlib.h> #include <string.h>
#define MAX_LEN 1000 // 最大位数
/**
- @brief 大整数结构体，包括符号和二进制字符数组表示 */ typedef struct { char sign; // 符号，'+'或'-' int len; // 二进制字符数组表示的长度 char bits[MAX_LEN]; // 二进制字符数组表示 } BigInteger;
/**
- @brief 将十进制字符串转换为二进制字符数组表示的大整数
- @param str 十进制字符串
- @return 二进制字符数组表示的大整数 */ BigInteger strToBigInt(char *str) { BigInteger num; memset(num.bits, '0', sizeof(num.bits)); // 初始化为全0 num.len = strlen(str); if (str[0] == '-') { // 处理负数 num.sign = '-'; for (int i = 1; i < num.len; i++) { num.bits[MAX_LEN - num.len + i] = str[i] - '0'; // 转为二进制字符数组表示 } } else { // 处理正数 num.sign = '+'; for (int i = 0; i < num.len; i++) { num.bits[MAX_LEN - num.len + i] = str[i] - '0'; // 转为二进制字符数组表示 } } return num; }
/**
- @brief 将二进制字符数组表示的大整数转换为十进制字符串
- @param num 二进制字符数组表示的大整数
- @return 十进制字符串 */ char *bigIntToStr(BigInteger num) { char *str = (char *)malloc(sizeof(char) * (MAX_LEN + 2)); // 最长为MAX_LEN，加上符号位和结束符 int i; for (i = 0; i < MAX_LEN - 1 && num.bits[i] == '0'; i++); // 去掉前导0 if (i == MAX_LEN - 1) { // 全0 str[0] = '0'; str[1] = '\0'; return str; } if (num.sign == '-') { // 处理负数 str[0] = '-'; for (int j = i; j < MAX_LEN; j++) { str[j - i + 1] = num.bits[j] + '0'; // 转为十进制字符 } } else { // 处理正数 for (int j = i; j < MAX_LEN; j++) { str[j - i] = num.bits[j] + '0'; // 转为十进制字符 } } str[MAX_LEN - i] = '\0'; // 结束符 return str; }
/**
- @brief 比较两个大整数的大小
- @param num1 二进制字符数组表示的大整数1
- @param num2 二进制字符数组表示的大整数2
- @return 1表示num1>num2，0表示num1=num2，-1表示num1<num2 */ int cmpBigInt(BigInteger num1, BigInteger num2) { if (num1.sign == '+' && num2.sign == '-') { // 正数>负数 return 1; } if (num1.sign == '-' && num2.sign == '+') { // 负数<正数 return -1; } // 同号 int i; for (i = 0; i < MAX_LEN && num1.bits[i] == num2.bits[i]; i++); if (i == MAX_LEN) { // 两数相等 return 0; } if (num1.sign == '+') { // 正数 if (num1.bits[i] > num2.bits[i]) { return 1; } else { return -1; } } else { // 负数 if (num1.bits[i] < num2.bits[i]) { return 1; } else { return -1; } } }
/**
- @brief 取绝对值
- @param num 二进制字符数组表示的大整数
- @return 绝对值 */ BigInteger absBigInt(BigInteger num) { BigInteger absNum = num; absNum.sign = '+'; return absNum; }
/**
- @brief 将二进制字符数组表示的大整数左移n位
- @param num 二进制字符数组表示的大整数
- @param n 左移位数 */ void leftShift(BigInteger *num, int n) { for (int i = MAX_LEN - 1; i >= n; i--) { num->bits[i] = num->bits[i - n]; } for (int i = n - 1; i >= 0; i--) { num->bits[i] = '0'; } }
/**
- @brief 将二进制字符数组表示的大整数右移n位
- @param num 二进制字符数组表示的大整数
- @param n 右移位数 */ void rightShift(BigInteger *num, int n) { for (int i = 0; i < MAX_LEN - n; i++) { num->bits[i] = num->bits[i + n]; } for (int i = MAX_LEN - n; i < MAX_LEN; i++) { num->bits[i] = '0'; } }
/**
- @brief 对二进制字符数组表示的大整数进行加法运算
- @param num1 二进制字符数组表示的大整数1
- @param num2 二进制字符数组表示的大整数2
- @return 二进制字符数组表示的和 */ BigInteger addBigInt(BigInteger num1, BigInteger num2) { BigInteger sum; memset(sum.bits, '0', sizeof(sum.bits)); // 初始化为全0 if (num1.sign == '+') { // 处理正数 if (num2.sign == '-') { // 正数+负数=正数-绝对值 num2.sign = '+'; return subBigInt(num1, num2); } } else { // 处理负数 if (num2.sign == '+') { // 负数+正数=正数-绝对值 num1.sign = '+'; return subBigInt(num2, num1); } else { // 负数+负数=负数+绝对值 num1.sign = '+'; num2.sign = '+'; sum.sign = '-'; } } int carry = 0; // 进位 for (int i = MAX_LEN - 1; i >= 0; i--) { int bitSum = num1.bits[i] + num2.bits[i] + carry - '0' - '0'; sum.bits[i] = bitSum % 2 + '0'; // 二进制位相加 carry = bitSum / 2; // 计算进位 } sum.len = MAX_LEN; return sum; }
/**
- @brief 对二进制字符数组表示的大整数进行减法运算
- @param num1 二进制字符数组表示的大整数1
- @param num2 二进制字符数组表示的大整数2
- @return 二进制字符数组表示的差 */ BigInteger subBigInt(BigInteger num1, BigInteger num2) { BigInteger diff; memset(diff.bits, '0', sizeof(diff.bits)); // 初始化为全0 if (num1.sign == '+') { // 处理正数 if (num2.sign == '-') { // 正数-负数=正数+绝对值 num2.sign = '+'; return addBigInt(num1, num2); } if (cmpBigInt(num1, num2) < 0) { // num1<num2 diff = subBigInt(num2, num1); diff.sign = '-'; return diff; } } else { // 处理负数 if (num2.sign == '+') { // 负数-正数=-(正数-绝对值) num1.sign = '+'; diff = subBigInt(num1, num2); diff.sign = '-'; return diff; } if (cmpBigInt(num1, num2) > 0) { // num1>num2 diff = subBigInt(num2, num1); diff.sign = '-'; return diff; } } int borrow = 0; // 借位 for (int i = MAX_LEN - 1; i >= 0; i--) { int bitDiff = num1.bits[i] - num2.bits[i] - borrow; if (bitDiff < 0) { // 需要借位 bitDiff += 2; // 借1变成10 borrow = 1; } else { borrow = 0; } diff.bits[i] = bitDiff + '0'; // 二进制位相减 } diff.len = MAX_LEN; return diff; }
/**
- @brief 对二进制字符数组表示的大整数进行乘法运算
- @param num1 二进制字符数组表示的大整数1
- @param num2 二进制字符数组表示的大整数2
- @return 二进制字符数组表示的积 */ BigInteger mulBigInt(BigInteger num1, BigInteger num2) { BigInteger prod; memset(prod.bits, '0', sizeof(prod.bits)); // 初始化为全0 if (num1.sign != num2.sign) { // 处理符号 prod.sign = '-'; } for (int i = MAX_LEN - 1; i >= 0 && num1.bits[i] != '0'; i--) { int carry = 0; // 进位 for (int j = MAX_LEN - 1; j >= 0 && num2.bits[j] != '0'; j--) { int bitProd = (num1.bits[i] - '0') * (num2.bits[j] - '0') + carry; bitProd += prod.bits[i + j + 1] - '0'; // 累加当前位 prod.bits[i + j + 1] = bitProd % 2 + '0'; // 二进制位相加 carry = bitProd / 2; // 计算进位 } prod.bits[i] += carry; // 处理最高位的进位 } prod.len = MAX_LEN; return prod; }
/**
- @brief 对二进制字符数组表示的大整数进行除法运算
- @param num1 二进制字符数组表示的大整数1
- @param num2 二进制字符数组表示的大整数2
- @return 二进制字符数组表示的商 */ BigInteger divBigInt(BigInteger num1, BigInteger num2) { BigInteger quo; memset(quo.bits, '0', sizeof(quo.bits)); // 初始化为全0 if (num2.sign == '+') { // 处理正数 if (num1.sign == '-') { // 处理负数 num1.sign = '+'; quo = divBigInt(num1, num2); quo.sign = '-'; return quo; } } else { // 处理负数 if (num1.sign == '+') { // 处理正数 num2.sign = '+'; quo = divBigInt(num1, num2); quo.sign = '-'; return quo; } } BigInteger remainder = absBigInt(num1); // 余数 BigInteger divisor = absBigInt(num2); // 除数 int shift = 0; // 左移位数 while (cmpBigInt(remainder, divisor) >= 0) { // 被除数大于等于除数 leftShift(&divisor, 1); // 除数左移1位 shift++; } while (shift >= 0) { rightShift(&divisor, 1); // 除数右移1位 shift--; if (cmpBigInt(remainder, divisor) >= 0) { // 被除数大于等于除数 quo.bits[MAX_LEN - 1 - shift] = '1'; // 商的当前位为1 remainder = subBigInt(remainder, divisor); // 更新余数 } } quo.len = MAX_LEN; return quo; }
int main() { char str1[MAX_LEN + 2], str2[MAX_LEN + 2]; scanf("%s %s", str1, str2); BigInteger num1 = strToBigInt(str1); BigInteger num2 = strToBigInt(str2); BigInteger sum = addBigInt(num1, num2); char *sumStr = bigIntToStr(sum); printf("%s + %s = %s\n", str1, str2, sumStr); free(sumStr); BigInteger diff = subBigInt(num1, num2); char *diffStr = bigIntToStr(diff); printf("%s - %s = %s\n", str1, str2, diffStr); free(diffStr); BigInteger prod = mulBigInt(num1, num2); char *prodStr = bigIntToStr(prod); printf("%s * %s = %s\n", str1, str2, prodStr); free(prodStr); BigInteger quo = divBigInt(num1, num2); char *quoStr = bigIntToStr(quo); printf("%s / %s = %s\n", str1, str2, quoStr); free(quoStr); return 0; }
原文地址: https://www.cveoy.top/t/topic/nKqF 著作权归作者所有。请勿转载和采集!