主题：超大十进制数转为二进制数，有无较快的算法？
eastcowboy
[专家分：25370] 发布于 2005-07-02 11:21:00
如题，传统的除二取余，时间复杂度似乎高了点。
回复列表 （共19个回复）
沙发
eastcowboy [专家分：25370] 发布于 2005-07-03 20:45:00
晕，兄弟们倒是说句话啊，都整整一天了。
板凳
gene91 [专家分：100] 发布于 2005-07-05 13:34:00
不可能有更快的算法。
3 楼
编程黑客 [专家分：1660] 发布于 2005-07-06 21:45:00
别做梦了,绝对没有,除非找比尔盖茨
4 楼
davidw017 [专家分：4170] 发布于 2005-07-07 15:58:00
可能吧……我也不知会不会快
这里举一个例子，比如
N = 4294967299(2^32+3)
那么 让 N - 2^32，一看可以减，那么 N = N-2^32 = 3，然后把二进制数组的第 32 位标示为 1，然后 N - 2^31 减不了，N - 2^30......N - 2^2 减不了，N - 2^1 可以，那么 N = N - 2^1 = 1, 第 1 位标示为 1，N - 2^0 = 0，第 0 位标示为 1，这样 N = 0 就分解完了。
2^n 可以算好了放到数组里
5 楼
ArrayNil [专家分：320] 发布于 2005-07-08 16:52:00
楼主啊!你会不会估计时间复杂度?
logn级别的还高!?
2^32都到2147483648*2了,把MaxLongInt分解掉才做31次运算,而且每次都输出bool类型,还不够快!?
莫非谁有O(1)?不可能~~
但可能稍微快一点点,如果是用C语言,用While做"<<"(这种提速只能说是“微秒级”)
6 楼
eastcowboy [专家分：25370] 发布于 2005-07-10 15:20:00
2^32才比long类型大一点。
我是想如果一个100位的十进制数，如果转为二进制的话，虽然表面上看只要进行300多次除二就可以，但是由于是比较大的数，每次除法的时间复杂度并不是O(1)，而是O(log n)，这样的话整个的时间复杂度就变成O(log2 n * log10 n)了。
7 楼
FancyMouse [专家分：13680] 发布于 2005-07-11 17:47:00
有O(1)的，就是你存放这个大数本身就用2进制来存储，这样要“转为二进制”直接输出就行了~~~
8 楼
eastcowboy [专家分：25370] 发布于 2005-07-17 20:10:00
晕了。
那么计算机又是如何将一个超大数转为二进制并储存的呢？
如果这个数超过了64位二进制长度，又该怎么办？
9 楼
brianzf [专家分：30] 发布于 2005-07-28 14:13:00
我觉得他说的很对的，计算机就是用2进制存数据的，用指针把，能横好的解决问题的
10 楼
brianzf [专家分：30] 发布于 2005-07-28 14:16:00
其实初2的方法也很快的
我来回复
您所在位置：