社区
数据结构与算法
帖子详情
超长2进制数串转换为10进制数```````
sapala____
2008-10-07 08:25:43
看了一道题目
最长达到3000位的2进制数 转换为 10进制数
这样的算法该如何写? 复杂吗?
...全文
1309
29
打赏
收藏
超长2进制数串转换为10进制数```````
看了一道题目 最长达到3000位的2进制数 转换为 10进制数 这样的算法该如何写? 复杂吗?
复制链接
扫一扫
分享
转发到动态
举报
写回复
配置赞助广告
用AI写文章
29 条
回复
切换为时间正序
请发表友善的回复…
发表回复
打赏红包
lz3771
2010-11-18
打赏
举报
回复
mark
liangbch
2010-11-18
打赏
举报
回复
楼上各位,如果你需要对高精度算法(特别是乘法和除法)做更多的了解,你能够参考以下2个帖子
计算百万位e
:
高精度计算sqrt(2):
showjim
2010-07-30
打赏
举报
回复
[Quote=引用 24 楼 sbwwkmyd 的回复:]
引用 7 楼 liangbch 的回复:
计算b的倒数c=1/b,这一过程的运算量大体等于两个n位数乘法的运算量的一半。
你好,我对这个问题很感兴趣,对于大整数求倒数不知道怎样才能达到乘法运算量的一半,谢谢指教
[/Quote]
是不是与快速平方根倒数算法有关?谢谢指教
showjim
2010-07-30
打赏
举报
回复
[Quote=引用 7 楼 liangbch 的回复:]
计算b的倒数c=1/b,这一过程的运算量大体等于两个n位数乘法的运算量的一半。
[/Quote]
你好,我对这个问题很感兴趣,对于大整数求倒数不知道怎样才能达到乘法运算量的一半,谢谢指教
xmx2009
2010-07-30
打赏
举报
回复
见识算法了
winematrix
2010-07-30
打赏
举报
回复
能贴出来学习一下吗?
[Quote=引用 22 楼 nan7711 的回复:]
我今天刚写好一个 C语言代码,超长的二进制转成十进制~ 3000位以上都能处理的 只要修改下,想处理多少位就处理多少位!!!(只要计算机内存足够就行)
[/Quote]
namewchwch
2010-07-29
打赏
举报
回复
先以4为段换成16进制,再换成10进制 这样快点
nan7711
2010-07-29
打赏
举报
回复
我今天刚写好一个 C语言代码,超长的二进制转成十进制~ 3000位以上都能处理的 只要修改下,想处理多少位就处理多少位!!!(只要计算机内存足够就行)
zeroieme
2009-10-10
打赏
举报
回复
直接字符运算,从低位向高位
X=b[0]*1+b[1]*2+b[2]*4……+b[n]*2^n
人类经过几千年手算总结,从低向高运算是最符合计算规律的。
yu_xm
2009-10-09
打赏
举报
回复
[Quote=引用 7 楼 liangbch 的回复:]
.最简单最直观的方法,将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逆序
这个x不能大于32/64位的数吧?楼主要求的是3000位哦。
euroman
2009-10-09
打赏
举报
回复
如果你这个二进制数是字符串,那么也就是说可以表示为
byte [] array; (对于0<=i<3000, array[i] 不是等于0,就是等于1)
也就是需要大数运算咯,那么可以用Java的BIGDECIMAL
那么我们BigDecimal a;
a += array[i] * pow(2, 3000 - i - 1);
没有啦。如果非要用C,那么可以先写一套字符串表示的大数运算规则,然后再用这个公式咯。
24K純帥
2009-10-09
打赏
举报
回复
是得把数分到若干数组里,处理不是太复杂
hua_zhixing_
2009-10-08
打赏
举报
回复
常见的大数处理
showjim
2009-10-08
打赏
举报
回复
[Quote=引用 7 楼 liangbch 的回复:]
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)倍.
[/Quote]
大数2to10进制的算法中,我还没有找到过比二分结合10^9/18分割更快的方法。
[Quote=引用 7 楼 liangbch 的回复:]
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倍。
[/Quote]
这个有问题吧?
求精确解的时候,1/b的运算量应该和a/b差不多,怎么会大体等于两个n位数乘法的运算量的一半呢?
比如1000b/200b,直接除的需要保留800b左右的精度,而1/200b至少要保留800b的精度才能乘以1000b后求得精确解吧。
[Quote=引用 11 楼 liangbch 的回复:]
to 楼上,好主意,赞一个。和7楼不同,相对于7楼,该算法使用的是10(或者10^k)进制乘法,而非2进制除法。一开始R较小,做的是“小数”乘法,越到后来阶段,做的越是大数乘法。
算法描述,
step 1. 原始数据以2^8进制存放,低字节在前,高字节在后,n个字节的数组,记作B[0][0..n-1]
step 2. 以下要进行k=log2(n)趟计算,每次两量合并,R初值为2^8,J=1
step 3. 计算B[J][i]= b[J-1][i*2+1]*R + B[J-1][i*2] (i=0..n/2-1),如果n是奇数,B[J][n/2]==B[J0][n-1],
step 4. n=(n+1)/2, R=R*R, J++
step 5. if (n>1) 转 step 3
step 6: 现在目标数组只剩下一个元素,这个数是一个十进制数,将其输出即可。
注:
1. B[J]表示一个数组,第一趟计算时,原数组是B[0],计算结果数组是B[1],第2趟计算时,原数组是B[1],计算结果数组是B[2],依次类推。
2. 在运算过程中,需要计算的数始终是10进制或者10^k进制,例如10000进制或者1000000000进制。
9楼提到 gxq使用类似的转化算法,是我猜的,没有得到确认,也许这个算法比7楼的算法更好,感兴趣者可以借用HugeCalc库来编写一个转化进制转化程序,看看这个算法和7楼的算法哪个更快。
[/Quote]
B[0]={255,255,255,255}
B[1]={255*256+255,255*256+255}
B[2]={(255*256+255)*65536+(255*256+255)}
不知道是不是这个过程?
如果是二进制运算,这个过程像是什么都没做,是不是无用功呢?如果像下面描述的10进制分解后,不说效率问题,原来的空间大小能装下这个数吗?
[Quote=引用 11 楼 liangbch 的回复:]
2. 在运算过程中,需要计算的数始终是10进制或者10^k进制,例如10000进制或者1000000000进制。
[/Quote]
如果是自己模拟10进制乘法,这个效率大家应该一看就明白吧。
hucice
2009-10-08
打赏
举报
回复
mark
zzyjsjcom
2008-10-27
打赏
举报
回复
mark
wzyzb
2008-10-26
打赏
举报
回复
mark
yaos
2008-10-26
打赏
举报
回复
我想,两两归并的算法应该还能改进
liangbch
2008-10-10
打赏
举报
回复
to 楼上,好主意,赞一个。和7楼不同,相对于7楼,该算法使用的是10(或者10^k)进制乘法,而非2进制除法。一开始R较小,做的是“小数”乘法,越到后来阶段,做的越是大数乘法。
算法描述,
step 1. 原始数据以2^8进制存放,低字节在前,高字节在后,n个字节的数组,记作B[0][0..n-1]
step 2. 以下要进行k=log2(n)趟计算,每次两量合并,R初值为2^8,J=1
step 3. 计算B[J][i]= b[J-1][i*2+1]*R + B[J-1][i*2] (i=0..n/2-1),如果n是奇数,B[J][n/2]==B[J0][n-1],
step 4. n=(n+1)/2, R=R*R, J++
step 5. if (n>1) 转 step 3
step 6: 现在目标数组只剩下一个元素,这个数是一个十进制数,将其输出即可。
注:
1. B[J]表示一个数组,第一趟计算时,原数组是B[0],计算结果数组是B[1],第2趟计算时,原数组是B[1],计算结果数组是B[2],依次类推。
2. 在运算过程中,需要计算的数始终是10进制或者10^k进制,例如10000进制或者1000000000进制。
9楼提到
gxq使用类似的转化算法
,是我猜的,没有得到确认,也许这个算法比7楼的算法更好,感兴趣者可以借用HugeCalc库来编写一个转化进制转化程序,看看这个算法和7楼的算法哪个更快。
boxer_tony
2008-10-10
打赏
举报
回复
to liangbch:
你的算法要使用大数求余,而大数求余要想速度快似乎是一件很麻烦的事,我知道的就是方法就是该数减去他的商乘以基数,因此需要先计算基数的倒数,然后再计算该数与基数倒数的乘积,然后还得再减去,感觉太麻烦了。不知是否还有更好的方法?
你看这样是否更好些(我没有去实现过,呵呵)?可以使用类似归并的方法来把2进制转换为10进制:
(1)从低位到高位(以字节位单位或者更多也可以),两两合并成一个十进制数。假设以字节为单位,此时合并的时候,基数是2^8
(2)继续不断合并(当然基数也是不断改变2^16,2^32...),直到最后只剩下一个,转换完成。
不过,这样做似乎内存管理起来有些费事,呵呵。
另外,QXQ的HugeCalc现在9.0版都快出来了吧?呵呵
加载更多回复(9)
十六进制字符串
转换
为十进制
十进制字符串
转换
为十进制
数
char *str = "123"; int n = atoi(str); printf("%d\n", n); //输出:123 十六进制字符串
转换
为十进制
数
法一 long long change_num(char *str, int length) { char revstr[16] = {0}; //根据十六进制字符串的长度,这里注意
数
组不要越界...
16进制
转换
为
10进制
数
——算法
16进制
转换
为
10进制
数
题目描述 问题描述 从键盘输入一个不超过8位的正的十六进制
数
字符串,将它
转换
为正的十进制
数
后输出。 注:十六进制
数
中的10~15分别用大写的英文字母A、B、C、D、E、F表示。 样例输入 FFFF 样例输出 65535 题目分析 首先得将16进制
数
转换
为4位二进制
数
,装入到字符串中,再从字符串总从末尾开始,逐一将
2进制
转换
为
10进制
数
字。(从末尾
转换
就不存在倒序转...
十六进制字符串
转换
成十进制
数
减'0'的目的就是将arr[i]中的字符转化成
数
字 假设字符串是123
转换
成
10进制
循环第一圈:m=0*16+1; 第二圈:m=1*16+2; 第三圈:m=(1*16+2)*16+3,这不就相当于(1*16^2)+(2*16^1)+(3*16^0) 结果为:291 m=m*16+arr[i]-'A'+10; 这里为什么要加10因为A在
10进制
中表示10 比如:假设arr[i]='C'; arr[i]-'A'+10 = 'C'-'A'+10 = 12 12不就对应16进制中的C....
16进制字符串转化为
10进制
数
字
16进制字符串转化为
10进制
数
字,c语言,strtol函
数
,sscanf函
数
,PTA
C语言算法之将十进制
数
转换
成二进制
数
导语:在C语言中没有将其他进制的
数
直接输出为二进制
数
的工具或方法,输出为八进制
数
可以用%o,输出为十六进制可以用%x,输出为二进制就要我们自行解决了。下面给大家讲述一下如何编程实现将十进制
数
转换
成二进制
数
。 先将源代码展示给大家: #include <stdio.h> void main() { //进制
转换
函
数
的声明 int transfer(int x)...
数据结构与算法
33,007
社区成员
35,326
社区内容
发帖
与我相关
我的任务
数据结构与算法
数据结构与算法相关内容讨论专区
复制链接
扫一扫
分享
社区描述
数据结构与算法相关内容讨论专区
社区管理员
加入社区
获取链接或二维码
近7日
近30日
至今
加载中
查看更多榜单
社区公告
暂无公告
试试用AI创作助手写篇文章吧
+ 用AI写文章