Js的大整数(实际是字符串的乘法运算)踩坑记录

以下内容仅供学习交流,切勿用作其他用途

代码写得我头皮发麻

本来写代码好好的,用sproto传输网络数据也都好好的,突发的出来一个64位的和服务器不一样的整数,就想着是不是网络传输代码有bug了,找了半天也没发现问题。正当头皮发麻的时候看到了js中的sproto转大整数的时候,是有一个加法和乘法的。才想起js的整数是有安全范围的,安全范围里面这个数是准确的,否则都是有误差的

js的整数安全范围参照
https://developer.mozilla.org/zh-CN/docs/Web/JavaScript/Reference/Global_Objects/Number/isSafeInteger

js的整数安全范围如下

console.log(Number.MAX_SAFE_INTEGER ) //9007199254740991
console.log(Number.MIN_SAFE_INTEGER) //-9007199254740991

可以用Number.isSafeInteger来判断是不是安全的数字,

var t = 0xf00000020055;//这个t 是随便的数字
console.log(Number.isSafeInteger(t)) //

解决方案

google了一下,很多文章说有BigInt,但是我的node终端却是 ReferenceError: BigInt is not defined。于是,只好撸起袖子干。自己实现一个字符串代替数字的操作(这里只有加法减法和乘法,暂时没有考虑除法->理由就是除法我用不到)


function addArray(a1,a2){
    let mlen = a1.length - a2.length;
    let arr1 = a1,arr2 = a2;
    if(mlen < 0){
        arr1 = a2,arr2 = a1;
        mlen = -mlen;
    }
    arr2.forEach((v,i) => {
        arr1[mlen+i] += v;
    });

    for(let i=arr1.length-1;i>-1;i--){
        if(arr1[i] > 9){
            if(i>0){
                arr1[i-1] += Math.floor(arr1[i]/10);
                arr1[i] %= 10;
            }else{
                arr1.unshift(Math.floor(arr1[i]/10));
                arr1[i+1] %= 10;
            }
        }
    }

    return arr1;
}

/**
 * 这里的话 a1必须比a2的,因为我不想弄个负数
 * @param {*} a1 
 * @param {*} a2 
 */
function subArray(a1,a2){
    let l1=a1.length,l2 =a2.length
    for(let i=0;i<l2;i++){
        a1[l1-i-1] -= a2[l2-i-1];
    }

    for(let i=1;i<l1;i++){
        if(a1[l1-i] < 0){
            a1[l1-i] += 10;
            a1[l1-i-1] -=1;
        }
    }

    return a1;
}

/**
 * 长度必须相等呀数组
 * @param {*} arr1 
 * @param {*} arr2 
 */
function mulArray(arr1,arr2){
    let len = arr1.length;
    if(len == 1){
        let t = arr1[0] * arr2[0];
        let res = []
        while(t>9){
            res.push(t%10);
            t=Math.floor(t/10);
        }
        res.push(t);
        return res.reverse();
    }else{
        let mid = Math.floor(len/2),ti = mid*2-len;
        let x1 = arr1.slice(0,mid),x2=arr1.slice(mid,len),y1 = arr2.slice(0,mid),y2=arr2.slice(mid,len);
        
        let r1 = mulArray(x1,y1);
        let r2 = mulArray(x2,y2);
        let xx1 =x2.map((v,i)=>{return v+~~x1[i+ti]}),yy1 =y2.map((v,i)=>{return v+~~y1[i+ti]})
        let r3 = mulArray(xx1,yy1);
        subArray(r3,r2),subArray(r3,r1);


        let shiftLen = len-mid;
        Array.prototype.push.apply(r1,new Array(2*shiftLen).fill(0));
        Array.prototype.push.apply(r3,new Array(shiftLen).fill(0));
        Array.prototype.unshift.apply(r2,new Array(2*shiftLen).fill(0));
        r1 = addArray(r1,r2);
        r1 = addArray(r1,r3);

        while(r1.length > 0 && r1[0] ==0){
            r1.shift()
        }
        return r1;
    }

}


/**
 * @return 返回一个数组,arr.join("") 就是最终的结果
 * 参数不定,但是只能是由0-9构成的字符串,毕竟我用了parseInt,不然会有NaN的
 * @param arg1,arg2,arg3,.....
 * 
 * @example
 * mulString("13","13") //return  [1,6,9]
 * mulString("14","14").join("") //return  169
 * mulString("1234","25864","33358","555664")
 * ...
 * 
 */
function mulString() {
    let mularr = Array.prototype.slice.call(arguments, 0).map(v => {
        return v.split("").map(vv => { return parseInt(vv) });
    }) || [];

    if (mularr.length > 1) {
        let m_arr = mularr[0],m_maxlen = m_arr.length,temp_len=0,temp_arr;
        for (let i = 1, c = mularr.length; i < c; i++) {
            temp_len = mularr[i].length
            if(m_maxlen < temp_len){
                temp_len = temp_len - m_maxlen;
                m_maxlen += temp_len;
                temp_arr = m_arr;
            }else{
                temp_len = m_maxlen - temp_len;
                temp_arr = mularr[i]
            }
            Array.prototype.unshift.apply(temp_arr,new Array(temp_len).fill(0));
            m_arr = mulArray(m_arr,mularr[i]);
            m_maxlen = m_arr.length;
        }
        return m_arr;
    } else {
        return mularr[0];
    }
}

/**test */
var a = mulString("15","15").join("")
console.log(a)//225
a = mulString("12225","15").join("")
console.log(a)//183375
a = mulString("1578643","15").join("")
console.log(a)//23679645

a = mulString("1513486","15123456").join("")
console.log(a)//22889138927616
a = mulString("1513486","15123456","33").join("")
console.log(a)//755341584611328
a = mulString("22889138927616","33").join("")
console.log(a)//755341584611328
a = mulString("22889138927461315413616","45648435153463133").join("")
console.log(a)//1044853374048826543153421290634702218928



代码思路分治法,分而治之,参照算法的大数相乘

如果有问题欢迎讨论沟通。

结语

希望上诉代码对你有所帮助,如果没有,就当做无事发生

最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 216,039评论 6 498
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 92,223评论 3 392
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 161,916评论 0 351
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 58,009评论 1 291
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 67,030评论 6 388
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 51,011评论 1 295
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 39,934评论 3 416
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 38,754评论 0 271
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 45,202评论 1 309
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 37,433评论 2 331
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 39,590评论 1 346
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 35,321评论 5 342
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 40,917评论 3 325
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 31,568评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 32,738评论 1 268
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 47,583评论 2 368
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 44,482评论 2 352

推荐阅读更多精彩内容