大数相乘

朱雀 2022-06-02 02:36 237阅读 0赞

在这之前我们先来了解一下Java 中每种基本数据类型所占存储空间的大小。其中 1Byte = 8bit。

<table> 
 <tbody> 
 <tr> 
 <th>基本类型</th> 
 <th>大小</th> 
 <th>最小值</th> 
 <th>最大值</th> 
 <th>包装类型</th> 
 </tr> 
 <tr> 
 <td>boolean</td> 
 <td>-</td> 
 <td>-</td> 
 <td>-</td> 
 <td>Boolean</td> 
 </tr> 
 <tr> 
 <td>char </td> 
 <td> 16-bit </td> 
 <td>Unicode 0</td> 
 <td>Unicode 216−1 </td> 
 <td>Charater</td> 
 </tr> 
 <tr> 
 <td>byte</td> 
 <td> 8 bits </td> 
 <td>-128</td> 
 <td>+127</td> 
 <td>Byte</td> 
 </tr> 
 <tr> 
 <td>short</td> 
 <td> 16 bits </td> 
 <td> −215 </td> 
 <td> +215−1 </td> 
 <td>Short</td> 
 </tr> 
 <tr> 
 <td>int</td> 
 <td> 32 bits </td> 
 <td> −231 </td> 
 <td> +231−1 </td> 
 <td>Integer</td> 
 </tr> 
 <tr> 
 <td>long</td> 
 <td> 64 bits </td> 
 <td> −263 </td> 
 <td> +263−1 </td> 
 <td>Long</td> 
 </tr> 
 <tr> 
 <td>float</td> 
 <td> 32 bits </td> 
 <td>IEEE754</td> 
 <td>IEEE754</td> 
 <td>Float</td> 
 </tr> 
 <tr> 
 <td>double</td> 
 <td> 64 bits </td> 
 <td>IEEE754</td> 
 <td>IEEE754</td> 
 <td>Double</td> 
 </tr> 
 </tbody> 
</table>

这里实现大数相乘分为两步：

1.  对较大数进行拆分，分别与较小数相乘，逆序保存在数组中
2.  对数组中的数值进行保留与进位操作，使数组中的每一个元素都是小于10的数，完成大数运算

![这里写图片描述][SouthEast]

代码实现

import java.util.Scanner;
 
 public class BigIntegerTest {
 static long[] array = new long[100];
 static int index = array.length - 1;
 
 public static void main(String[] args) {
 
 Scanner read = new Scanner(System.in);
 long num1 = read.nextLong();
 long num2 = read.nextLong();
 boolean flag = false;
 
 bigNumMultiply(num1,num2);
 
 System.out.print("结果为：");
 
 for(int i=0; i<array.length; i++){
 if(array[i] != 0 && flag == false)
 flag = true;
 if(flag)
 System.out.print(array[i]);
 }
 }
 
 public static void bigNumMultiply(long num1, long num2){
 if(num1 < num2){ //始终保持 num1 > num2 
 long temp = num1;
 num1 = num2;
 num2 = temp;
 }
 
 while (num1 > 0){
 long num = num1 % 10; //对num1 进行取余，每次获得个位
 array[index] = num * num2; //取余后与num2 相乘，倒序保存在数组中
 num1 = num1 / 10; 
 index--;
 }
 
 index = array.length - 1;
 
 for(int i=array.length-1; i>0; i--){
 array[i-1] = array[i-1] + array[i] / 10; //进位
 array[i] = array[i] % 10; //保留个位
 }
 }
 }

> 测试  
> 99999999999999  
> 99999999999999  
> 结果为：9999999999999800000000000001

PS：Java 所能支持的最大基本整型数值类型是long ，long类型的数值最大是9223372036854775807。所以这种算法有一个局限就是较小数与较大数分解后相乘的数值不能大于long 类型的最大数值。

[SouthEast]: /images/20220602/32e5b33f04c24657a43936aa295e185a.png