code: multiplication algorithm for a long long integer,(you can not store the integer with int or even long, unsinged long)
c*2
2 楼
How about this: 1) count how many digits are in the numbers, let's say it's 11 digits 2) reduce it: a=long long (11 digits) double b=a/10^10; then easy double operations. In short, do it in units of billions.
这个是正解! Wiki里面的伪代码非常经典: multiply(a[0..n−1], b[0..n−1]) // Arrays representing the binary representations x ← 0 for i from 0 to 2n−2 for j from max(0,i+1−n) to min(i,n−1) k ← i − j x ← x + (a[j] × b[k]) result[i] ← x mod 2 x ← floor(x/2) return result[]; 其中a, b [0,..n-1]表示从低位到高位的顺序,计算的顺序也是从低到高 改成10进制也很简单,x mod 2 改成 x%10, x/2-> x/10 即可。 注意,最后的进位上面代码里面没处理,需要处理一下。 自己练一下,还是很好玩的,特别是里面j的取值范围。 此外,如果a和b的数量级不一样,比如a是n位数,b是m位数,再写这个程序就更刺激了。 发信人: westcamp (西草), 信区: JobHunting 标 题: Re: 经典面试题 发信站: BBS 未名空间站 (Wed Nov 24 11:56:12 2010, 美东) http://en.wikipedia.org/wiki/Multiplication_algorithm