大数相乘--golang简单实现

波涛澎湃 · · 1079 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

大数乘法之golang实现
所谓大数相乘(Multiplication algorithm),就是指数字比较大,相乘的结果超出了基本类型的表示范围,所以这样的数不能够直接做乘法运算。

解法:

模拟乘法手算累加

        9  8
×       2  1
-------------
       (9)(8)  <---- 第1趟: 98×1的每一位结果 
  (18)(16)     <---- 第2趟: 98×2的每一位结果 
-------------
  (18)(25)(8)  <---- 这里就是相对位的和,还没有累加进位 

这里唯一要注意的便是进位问题,我们可以先不考虑进位,当所有位对应相加,产生结果之后,再考虑。从右向左依次累加,如果该位的数字大于10,那么我们用取余运算,在该位上只保留取余后的个位数,而将十位数进位(通过模运算得到)累加到高位便可,循环直到累加完毕。

代码如下:

package main

import "fmt"

func main() {
    a := "999999999999"
    b := "111111111111"
    c := BigMulti(a, b)
    fmt.Println(c)
}

//BigMulti 大数相乘
func BigMulti(a, b string) string {
    if a == "0" || b == "0" {
        return "0"
    }
    // string转换成[]byte,容易取得相应位上的具体值
    bsi := []byte(a)
    bsj := []byte(b)

    temp := make([]int, len(bsi)+len(bsj))
    //两数相乘,结果位数不会超过两乘数位数和,即temp的长度只可能为 len(num1)+len(num2) 或 len(num1)+len(num2)-1
    // 选最大的,免得位数不够
    for i := 0; i < len(bsi); i++ {
        for j := 0; j < len(bsj); j++ {
            // 对应每个位上的乘积,直接累加存入 temp 中相应的位置
            temp[i+j+1] += int(bsi[i]-'0') * int(bsj[j]-'0')
        }
    }

    //统一处理进位
    for i := len(temp) - 1; i > 0; i-- {
        temp[i-1] += temp[i] / 10 //对该结果进位(进到前一位)
        temp[i] = temp[i] % 10    //对个位数保留
    }

    // a 和 b 较小的时候,temp的首位为0
    // 为避免输出结果以0开头,需要去掉temp的0首位
    if temp[0] == 0 {
        temp = temp[1:]
    }
    //转换结果:将[]int类型的temp转成[]byte类型,
    //因为在未处理进位的情况下,temp每位的结果可能超过255(go中,byte类型实为uint8,最大为255),所以temp选用[]int类型
    //但在处理完进位后,不再会出现溢出
    res := make([]byte, len(temp)) //res 存放最终结果的ASCII码

    for i := 0; i < len(temp); i++ {
        res[i] = byte(temp[i] + '0')
    }

    return string(res)
}

java代码参考实现:
https://blog.csdn.net/u010983881/article/details/77503519


有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:波涛澎湃

查看原文:大数相乘--golang简单实现

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:692541889

1079 次点击  
加入收藏 微博
暂无回复
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传