大数运算

青旅半醒 2023-06-13 06:07 6阅读 0赞

大数指number无法存储的数字，一般用字符串来表示。  
以下分别讲述大数的加减乘除运算，运算之间可能有所交叉，例如正数减负数就变成两个正数相加，除法里也用到了减法，所以代码就放在了一起。

function checkIsNumber(numStr) {
      const isNumber = /^-?\d+$/.test(numStr)
      if (!isNumber) {
        throw new Error('param must be a number');
      }
      return isNumber;
    }
    
    function isZero(numStr) {
      return /^-?0$/.test(numStr);
    }
    
    function isNagative(numStr) {
      return numStr[0] === '-';
    }
    
    function transformToNagative(numStr) {
      if (isNagative(numStr)) {
        return numStr;
      }
      return '-' + numStr;
    }
    
    function getPositivePart(numStr) {
      if (isNagative(numStr)) {
        return numStr.substr(1);
      }
      return numStr;
    }
    
    // 大数加法
    function add(numStr1, numStr2) {
      // 需要判断正负
      const isNum1Nagative = isNagative(numStr1);
      const isNum2Nagative = isNagative(numStr2);
    
      numStr1 = getPositivePart(numStr1);
      numStr2 = getPositivePart(numStr2);
    
      // 一正一负责需要调减法, 否则还是加法
      if (isNum1Nagative + isNum2Nagative === 1) {
        return sub(isNum1Nagative ? numStr2 : numStr1, isNum1Nagative ? numStr1 : numStr2);
      }
    
      // 补0以避免后续长度判断
      if (numStr1.length < numStr2.length) {
        numStr1 = '0'.repeat(numStr2.length - numStr1.length) + numStr1
      } else if (numStr2.length < numStr1.length) {
        numStr2 = '0'.repeat(numStr1.length - numStr2.length) + numStr2
      }
      const length = numStr1.length
      let carry = 0
      let result = ''
      // 逐位相加，记录进位
      for (let i = length - 1; i >= 0; i--) {
        const temp = +numStr1[i] + +numStr2[i] + carry;
        result = (temp % 10) + result
        carry = Math.floor(temp / 10);
      }
      // 最后进位要补上
      if (carry) {
        result = carry + result;
      }
      // 负数相加最后补负号
      if (isNum1Nagative && isNum2Nagative) {
        result = transformToNagative(result);
      }
      return result;
    }
    
    
    // 大数乘法
    function multiBy(numStr1, numStr2) {
      // 需要判断正负
      const isNum1Nagative = isNagative(numStr1);
      const isNum2Nagative = isNagative(numStr2);
    
      numStr1 = getPositivePart(numStr1);
      numStr2 = getPositivePart(numStr2);
      let len1 = numStr1.length;
      let len2 = numStr2.length;
      // 结果不会超过len1+len2位
      let result = [];
      // 从右往左计算
      for (let i = len1 - 1; i >= 0; i--) {
        for (let j = len2 - 1; j >= 0; j--) {
          // 每一位可能要经过几次相加
          result[i + j] = (result[i + j] || 0) + +numStr1[i] * +numStr2[j];
        }
      }
      // 要计算进位，不反转从右往左计算也是可以的，但是得处理result[-1]、result[-2]这类情况
      result = result.reverse();
      for (let i = 0; i < result.length; i++) {
        if (result[i] > 10) {
          result[i + 1] = (result[i + 1] || 0) + Math.floor(result[i] / 10);
          result[i] %= 10;
        }
      }
      // 前面反转过，需要再反转回来
      const resultStr = result.reverse().join('');
      if (isNum1Nagative + isNum2Nagative === 1) {
        return transformToNagative(resultStr);
      }
      return resultStr;
    }
    
    // 两个正数比较大小
    function bigger(numStr1, numStr2) {
      const len1 = numStr1.length;
      const len2 = numStr2.length;
      return len1 > len2 || (len1 === len2 && numStr1 >= numStr2)
    }
    
    function sub(numStr1, numStr2) {
      // 需要判断正负
      const isNum1Nagative = isNagative(numStr1);
      const isNum2Nagative = isNagative(numStr2);
    
      numStr1 = getPositivePart(numStr1);
      numStr2 = getPositivePart(numStr2);
    
      if (isNum1Nagative && !isNum2Nagative) {
        // 负数减正数，等于两个正数相加再取负
        return transformToNagative(add(numStr1, numStr2));
      } else if (isNum1Nagative && isNum2Nagative) {
        // 负数减负数，等于2-1
        return sub(numStr2, numStr1);
      } else if (!isNum1Nagative && isNum2Nagative) {
        // 正数减负数，等于两个正数相加
        return add(numStr1, numStr2);
      }
      // 小减大直接用大数减小数，再加上负号
      if (!bigger(numStr1, numStr2)) {
        return transformToNagative(sub(numStr2, numStr1));
      }
      // 补0
      if (numStr2.length < numStr1.length) {
        numStr2 = '0'.repeat(numStr1.length - numStr2.length) + numStr2
      }
      let carry = 0;
      let result = ''
      for(i = numStr1.length - 1; i >= 0; i--) {
        let current = numStr1[i] - carry;
        
        if (current < +numStr2[i]) {
          carry = 1;
          // 借位
          current += 10;
        } else {
          carry = 0;
        }
        result = (current - numStr2[i]) + result;
      }
      // 去掉前面的0
      let zeroLen = 0;
      for (let i = 0; i < result.length; i++) {
        if (result[i] === '0') {
          zeroLen++
        } else {
          break;
        }
      }
      if (zeroLen > 0) {
        result = result.substr(zeroLen);
      }
      return result;
    }
    
    function divide(numStr1, numStr2) {
      if (isZero(numStr2)) {
        throw new Error('dividend can not be zero');
      }
      // 需要判断正负
      const isNum1Nagative = isNagative(numStr1);
      const isNum2Nagative = isNagative(numStr2);
      // 一正一负则结果是负
      const resultIsNagative = isNum1Nagative + isNum2Nagative === 1;
    
      numStr1 = getPositivePart(numStr1);
      numStr2 = getPositivePart(numStr2);
      const len1 = numStr1.length;
      const len2 = numStr2.length;
      // 除数比被除数小，直接返回
      if (!bigger(numStr1, numStr2)) {
        return {
          integer: '0',
          remainder: numStr1,
        }
      }
      let remainder = '0';
      let integer = ''
      // 截一部分出来做除数
      let divider = numStr1.substr(0, len2);
      numStr1 = numStr1.substr(len2);
      do {
        // 当前位结果计数，和最终结果不一样，最终结果有可能溢出，只能用字符串表示，这个只会一位
        let currentInteger = 0;
    
        // 除数比较小，检查是否已到最后，如果到了最后，直接返回
        if (!bigger(divider, numStr2)) {
          if (!numStr1) {
            remainder = divider;
            break;
          } else {
            // 否则再取一位
            divider += numStr1[0];
            numStr1 = numStr1.substr(1);
          }
          
        }
        while(bigger(divider, numStr2)) {
          currentInteger++;
          divider = sub(divider, numStr2);
        }
        remainder = divider;
        integer += currentInteger; 
      } while(numStr1)
      if (!integer) {
        integer = '0'
      }
      if (resultIsNagative && integer !== '0') {
        integer = transformToNagative(integer)
      }
      return {
        integer,
        remainder,
      }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，6人围观）

还没有评论，来说两句吧...

相关阅读

相关大数取余运算(详解)

大数取余运算(详解) //(19^3 mod 23)^2 mod 31=25 //a=19 b=3 c=23 d=2 e=31 include<s

缺乏、安全感/ 2023年10月04日 15:45/ 0 赞/ 8 阅读

相关大数运算

大数指number无法存储的数字，一般用字符串来表示。以下分别讲述大数的加减乘除运算，运算之间可能有所交叉，例如正数减负数就变成两个正数相加，除法里也用到了减法，所以代码

青旅半醒/ 2023年06月13日 06:07/ 0 赞/ 7 阅读

相关需要大数运算的程序

哪位程序员朋友开发过大数运算的程序，可以挑战一下下面这个问题：对于较大的自然数k>100，(3/2)^k的小数部分总是小于1-(3/4)^k，这个问题和一个著名的[数

╰+攻爆jí腚メ/ 2022年09月17日 06:19/ 0 赞/ 36 阅读

相关大数运算

文章[位操作实现加减乘除四则运算][Link 1] 当整数很大，在计算机可以表示的范围内无法通过常规的加减等运算计算时，这里介绍的大数运算是一种有效的计算方法。这里

拼搏现实的明天。/ 2022年08月14日 01:38/ 0 赞/ 202 阅读

相关大数运算之加法

大数运算之加法：思路： 1.一次性输入大数，利用for循环读入缓冲区数据，当读到回车符时结束，将char型转化为int型数据，char-'0'=int 2.倒置

ゞ浴缸里的玫瑰/ 2022年07月16日 06:48/ 0 赞/ 219 阅读

相关大数运算之阶乘

Int不能存储较大数 int 代表有符号整数，也就是说，用 int 声明的变量可以是正数，可以是负数，也可以是零，但是只能是整数。标准规定 int 的最小取值范围是 -3

亦凉/ 2022年07月16日 06:12/ 0 赞/ 269 阅读

相关大数加法运算

// 大数加法运算 include <stdio.h> include <stdlib.h> include <string.h>

心已赠人/ 2022年05月28日 02:23/ 0 赞/ 223 阅读

相关大数运算模板

> 1、大数加法 string add(string a,string b) { string c; int len1=a.l

秒速五厘米/ 2022年04月17日 01:42/ 0 赞/ 188 阅读

相关大数模运算(JSU-ZJJ)

题目描述给定任意位数长度的两个整数，求第一个整数对第二整数的模数。输入每个测试用例含有两个整数，代表两个任意位数长度的整数A，B。输出计算出这两个任

柔光的暖阳◎/ 2022年04月03日 02:30/ 0 赞/ 192 阅读

相关 Java实现大数乘法运算

基本思路：将输入的两个大数以字符串的形式存储，然后转化成整型数组存储，通过整型数组进行乘法运算（采用分治的思想）即乘法分配律，如AB\CD=AC(AD+BC)BD,将两个数

ゝ一纸荒年。/ 2021年12月17日 07:57/ 0 赞/ 299 阅读