1.最简单最直观的方法，将2进制方式表示的数转化为10进制表示的数，要用除10取余法，步骤如下
被除数记为x,10进制表示的结果用数组a表示
1. i=0;
2. a[i]= x % 10; x=x/10; i++;
3. 如果x>0,转2,否则转4
4. 将数组a逆序
2.上面的方法虽然简单，但是速度很慢，假如结果需要n位10进制数，大约需要进行 n^2/2 次除法。一种改进的方法是：
除以10^k来代替除以10，典型的做法是除以10^9,这样得到余数将是0-10亿之间的数，因此采用该法需要2个阶段的计算。
第1阶段，将2进制数转化为一个整形数组，数组中的每个元素为0- 999999999 的数。这个阶段需要做 n^2/(81*2)次 64bit/32bit的除法。
第2阶段，将每个10^9以内的数转化为9位‘0’-‘9’之间的数字，结合除法和查表，每个10^9以
被除数记为x,10进制表示的结果用数组a表示
1. i=0;
2. a[i]= x % 10; x=x/10; i++;
3. 如果x>0,转2,否则转4
4. 将数组a逆序
2.上面的方法虽然简单，但是速度很慢，假如结果需要n位10进制数，大约需要进行 n^2/2 次除法。一种改进的方法是：
除以10^k来代替除以10，典型的做法是除以10^9,这样得到余数将是0-10亿之间的数，因此采用该法需要2个阶段的计算。
第1阶段，将2进制数转化为一个整形数组，数组中的每个元素为0- 999999999 的数。这个阶段需要做 n^2/(81*2)次 64bit/32bit的除法。
第2阶段，将每个10^9以内的数转化为9位‘0’-‘9’之间的数字，结合除法和查表，每个10^9以
内的数转化为9位数字，仅仅需要2次除法。这一阶段需要需要 n/9*2=n/4.5次除法，当n较大时，相对于第一阶段，运算量可忽略不计，因此这个方法比方法1要快45(9*9/2)倍.
3.多位数（大数）乘以或除以一位数（这里指可以用内置的整数类型表示的数，比如2^32以内的数）没有高效的算法，大数进制转化最根本的解决之道是采用多位数除以多位数的大数运算。和多位数乘以一位数不同，随着大数位数的增多，最好的n位数乘以n位数的算法的运算量相比于最简单的硬乘法（复杂为n*n）优势越来越明显，性能最佳的大数乘法依次为分治法，Toom-cook算法，FFT算法。通常情况下，大数除法的可以使用大数乘法来实现，求 a/b 的商和除数并精确到n位有效数字的具体方法如下：
1. 计算b的倒数c=1/b，这一过程的运算量大体等于两个n位数乘法的运算量的一半。
2. 计算a/b的商d=a*c, 这一过程的运算量等于两个n位数乘法的运算量
3. 计算余数 a-d，当n较大时，这一过程可忽略不计。
综上所述，计算a/b的的商和余数大体等于同等精度大数乘法的1.5倍。
3.多位数（大数）乘以或除以一位数（这里指可以用内置的整数类型表示的数，比如2^32以内的数）没有高效的算法，大数进制转化最根本的解决之道是采用多位数除以多位数的大数运算。和多位数乘以一位数不同，随着大数位数的增多，最好的n位数乘以n位数的算法的运算量相比于最简单的硬乘法（复杂为n*n）优势越来越明显，性能最佳的大数乘法依次为分治法，Toom-cook算法，FFT算法。通常情况下，大数除法的可以使用大数乘法来实现，求 a/b 的商和除数并精确到n位有效数字的具体方法如下：
1. 计算b的倒数c=1/b，这一过程的运算量大体等于两个n位数乘法的运算量的一半。
2. 计算a/b的商d=a*c, 这一过程的运算量等于两个n位数乘法的运算量
3. 计算余数 a-d，当n较大时，这一过程可忽略不计。
综上所述，计算a/b的的商和余数大体等于同等精度大数乘法的1.5倍。
4.利用大数除法，我们可以实现效率很高的转化算法，假如这个2进制数转化为10进制数后有n位10进制数，那么我们使用下面的方法去转化他，其基本思路是2分法。
1. 计算10^(n/2), 10^(n/4),10^(n/8),10^(n/16)...,当然，实际计算的时候以相反的顺序进行，10^(n/k)可以通过 10^(n/2k)的平方来计算。
例如，被转化的数有1000位整数，我们可以依次计算10^8,10^16,10^32,10^64,10^128,10^256,10^512,容易看到，后面的数正好是前面的数的平方，我们将这些数称为标准单位。
2. 对被转化的数 除以尽可能大的标准单位，如此，则所的余数和商均小于标准单位，这样，一个数将分裂为两个更小的大小大致相当的数，将商放在前面，余数放在后面。
3. 对分裂后的2个数分别除以次大的标准单位，采用同样的放置方法，2个数将分裂为4个数。这样得到的每个数均小于次大标准单位。
4. 不断重复这一过程，最终这个数组中所有的数都小于最小的标准单位。
5. 依次将小于最小标准单位的每个数转化为10进制字符串，到此为止，整个转化过程全部
1. 计算10^(n/2), 10^(n/4),10^(n/8),10^(n/16)...,当然，实际计算的时候以相反的顺序进行，10^(n/k)可以通过 10^(n/2k)的平方来计算。
例如，被转化的数有1000位整数，我们可以依次计算10^8,10^16,10^32,10^64,10^128,10^256,10^512,容易看到，后面的数正好是前面的数的平方，我们将这些数称为标准单位。
2. 对被转化的数 除以尽可能大的标准单位，如此，则所的余数和商均小于标准单位，这样，一个数将分裂为两个更小的大小大致相当的数，将商放在前面，余数放在后面。
3. 对分裂后的2个数分别除以次大的标准单位，采用同样的放置方法，2个数将分裂为4个数。这样得到的每个数均小于次大标准单位。
4. 不断重复这一过程，最终这个数组中所有的数都小于最小的标准单位。
5. 依次将小于最小标准单位的每个数转化为10进制字符串，到此为止，整个转化过程全部
完成。
下面是一个具体的例子，我们以一个1000位10进制的整数做例子，详细分析一下转化过程。我们采用每个整数单位表示9位10进制数，则需要112个整数。
1. 112向上取2的整数次幂，得到128. 我们需要分配128个的int存储单位。
2. 计算10^9,10^18,10^36,10^72,10^144,10^288,10^576，这些数分别需要1，2，4，8，16，32，64个int存储单位。
3. 计算 a0[0]= x / 10^576, a0[1]= x % 10^576. a0[1]占用64个int, a0[0]大约需占用58个int. 我们将a0[0],a0[1]连续存放，各占64个int.
4. a1[0]= a0[0] / 10^288,
a1[1]= a0[0] % 10^288,
a1[2]= a0[1] / 10^288,
a1[3]= a0[1] % 10^288,
下面是一个具体的例子，我们以一个1000位10进制的整数做例子，详细分析一下转化过程。我们采用每个整数单位表示9位10进制数，则需要112个整数。
1. 112向上取2的整数次幂，得到128. 我们需要分配128个的int存储单位。
2. 计算10^9,10^18,10^36,10^72,10^144,10^288,10^576，这些数分别需要1，2，4，8，16，32，64个int存储单位。
3. 计算 a0[0]= x / 10^576, a0[1]= x % 10^576. a0[1]占用64个int, a0[0]大约需占用58个int. 我们将a0[0],a0[1]连续存放，各占64个int.
4. a1[0]= a0[0] / 10^288,
a1[1]= a0[0] % 10^288,
a1[2]= a0[1] / 10^288,
a1[3]= a0[1] % 10^288,
这4个元素中的每一个均可用 32个int的空间存放。
5. a2[0]= a1[0] / 10^144,
a2[1]= a1[0] % 10^144,
a2[2]= a1[1] / 10^144,
a2[3]= a1[1] % 10^144,
a2[4]= a1[2] / 10^144,
a2[5]= a1[2] % 10^144,
a2[6]= a1[3] / 10^144,
a2[7]= a1[3] % 10^144,
这8个元素中的每一个均可用 16个int的空间存放。
6.逐次将1个数分裂成2个更小的数，最后得到128个小于10^9的数，其中前16(128-112)个数为0
5. a2[0]= a1[0] / 10^144,
a2[1]= a1[0] % 10^144,
a2[2]= a1[1] / 10^144,
a2[3]= a1[1] % 10^144,
a2[4]= a1[2] / 10^144,
a2[5]= a1[2] % 10^144,
a2[6]= a1[3] / 10^144,
a2[7]= a1[3] % 10^144,
这8个元素中的每一个均可用 16个int的空间存放。
6.逐次将1个数分裂成2个更小的数，最后得到128个小于10^9的数，其中前16(128-112)个数为0
7.将128个中的后112在线进制转换计算个数每个转化为9位10进制数，就得到最终的结果。注，第17个数得到8个零和1位数字，第18-128个数得到111×9=999个数字，总共将得到1000位数字。
发表评论