大数相乘---吃米粉时想到的

    技术2022-11-28  31

    好不容易,你得到个为银行工作的机会。作为程序员的你,上班第一天就遇到个头痛的问题。你上司要你写程序计算出10000000000234567800000 X 2343466888888880000000的结果。 也许是为了考验你,也许是真的有这个需求。不管怎样,面对这道题,你要怎么做?用32位的整数肯定不行,64位的也不能保证不会溢出。 题目要是求2的幕就好了,求2^m你只要将2左移m位就万事大吉。这么变态的大数,还要相乘,你都在怀疑自己是否真的适合这份工作。 把大数赋给整形变量,再用传统的c = a * b来求结果肯定不行。将大数看成字符串,接着移位倒是不错的做法。假设y代表一个大数,你要求y * 22的结果,问题可以转换成这个样子:   y * 22 = y * (20 + 2)          = (y * 20) + (y * 2)          = (y * 10 * 2) + (y * 2) 假设z = y * 10,z的值可以通过在y后直接补一个0得到,等式就变成:   y * 22 = (z * 2) + (y * 2)   将大数z和y都看成字符串,乘于2的操作可以逐位进行,对于形如123456234 * 2这样的算式,可以先取最后一个字符4,将4与2相乘,得8,同时将8作为字符保存起来;接着将倒数第二位的3与2相乘,得6,保存结果;再取排在倒数第3位的2,将它与2相乘......,依次类推。逐位击破,最后得到的就是相乘的结果。 回到文章开头的例子,求10000000000234567800000 X 2343466888888880000000的结果可以分解为移位再、逐位相乘、再相加,乘数234346688888888的最高位为2,2后面跟着  21个0,计算的第一步就是在代表被乘数的字符串“10000000000234567800000”后面加上21个0,变成“1000000000023456780000000000000000000000”,再将该字符串逐位与2相乘,得到字符串“2000000000046913560000000000000000000000”,接着用同样的方法处理次高位的3。

    最新回复(0)