以字符串的形式完成加法和乘法运算

问题描述和思路:当运算的数字过大时,会溢出范围,导致最后的结果出错。

PHP种整型数的字长和平台有关,32 位平台下的最大值通常最大值是大约二十亿,64 位平台下的最大值通常是大约 9E18。在PHP中,当数字超出整型范围时,会自动将其转换为浮点型,浮点数的字长和平台相关,通常最大值是 1.8e308 并具有 14 位十进制数字的精度。在本题中,虽然范围是在浮点数内的,但是精度却不足了,所以需要用别的方法来实现大数的运算,在这里我们可以使用字符串来实现。

直接运算——精度不足
//用字符串的形式实现数的乘法运算,是我们所熟悉的垂直乘法运算
function multiply(string $a, string $b): string {
  $lenA = strlen($a);
  $lenB = strlen($b);
  $result = '0';
  for ($inxA = $lenA - 1; $inxA >= 0; --$inxA) {
      $re = '';
      //补0操作,相当于位往前进一位,然后乘上10
      for ($i = $inxA + 1; $i < $lenA; ++$i) {
          $re = "0" . $re;
      }
      $j = 0;
      for ($inxB = $lenB - 1; $inxB >= 0; --$inxB) {
          //每一位乘法运算的结果
          $mul = $a[$inxA] * $b[$inxB] + $j;
          //进位
          if ($mul > 9) {
              $j = floor($mul / 10);
              $mul = $mul - $j * 10;
          } else {
              $j = 0;
          }
          $re = $mul . $re;
      }
      if ($j > 0) $re = $j . $re;
      $result = add($result, $re);
  }
  //去除字符串首的0
  if($result != '0') $result = preg_replace('/^0+/','',$result);
  return $result;
}
//用字符串的形式实现数的加法运算
function add($a, $b) {
    $j = 0;
    $re = '';
    for ($inxA = strlen($a) - 1, $inxB = strlen($b) - 1; ($inxA >= 0 || $inxB >= 0); --$inxA, --$inxB) {
        $itemA = $a[$inxA];
        $itemB = $b[$inxB];
        $sum = $itemA + $itemB + $j;
        //进位,因为是加法,所以进位最多为1
        if ($sum > 9) {
            $j = 1;
            $sum = $sum - 10;
        } else {
            $j = 0;
        }
        $re = (string)$sum . $re;
    }
    if ($j > 0) $re = (string)$j . $re;
    return $re;
}

虽然功能是实现了,但是还是离大佬的水平相差甚远呀。还是看看大佬的代码学习学习吧!

function multiply(string $a, string $b): string {
  //移除左侧无效的0,然后分割成数组,再反序。
  $a = array_reverse(str_split(ltrim($a, '0')));
  $b = array_reverse(str_split(ltrim($b, '0')));
  $r = [];
  foreach ($a as $ai => $av) {
    foreach ($b as $bi => $bv) {
      //两个数的每一位相乘,再存放至数组当中,这里以两数的位之和为键
      $m = $av * $bv;
      $r[$ai + $bi] += $m;
      //进位操作
      if ($r[$ai + $bi] >= 10) {
        $r[$ai + $bi + 1] += floor($r[$ai + $bi] / 10);
        $r[$ai + $bi] = $r[$ai + $bi] % 10;
      }
    }
  }
  //最后以字符串的形式输出
  return implode('', array_reverse($r));
}
function multiply(string $a, string $b): string {
  $result = array_fill(0, '0', strlen($a) + strlen($b));
  //反转字符串
  $a = strrev($a);
  $b = strrev($b);
  for ($i = 0; $i < strlen($a); $i++) {
    for ($j = 0; $j < strlen($b); $j++) {
      //计算每位乘法运算的结果和进位
      $tmp = $a[$i] * $b[$j] + $result[$i + $j];
      $result[$i + $j] = $tmp % 10;
      $result[$i + $j + 1] += floor($tmp / 10);
    }
  }
  //去掉字符串首的无效0字符
  return preg_replace('/^0+\B/', '', strrev(join($result)));
}

上面两个大佬写的思想是一样的,都是垂直乘法的实现,优化点在于使用了数组来存放每一位的运算结果,最后再拼接成字符串输出。这里都是先反转再运算,虽然这么做与我们自己笔算时从低位开始算不同,但是能够防止数组下标越界,是种更好的办法。

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注