问题请教：如何实现任意大整数到16进制的转换？

soloforce

给出一个无符号大整数，如何快速的转换到一个十六进制数？

程序要求：
1、输入：无符号大整数字符串，比如"123456789098765432199999"
2、输出：相应的十六进制数，以字符串方式显示，如 "0xFFEE8899AA"
3、时间效率越高越好

谢谢达人帮忙～～


PS: 这是某公司的面试题之一，555

soloforce

继续，同样是面试题之一。

如何实现int64到十进制的转换

程序要求：
1、输入：一个int64（8字节，以int32类似方式存放）的指针
2、输出：该int64的十进制字符串表示式。
3、必须手动写出转换过程，不得借助其他库函数。
4、时间效率越高越好。

Tetris

第一个好难, 思考中.

rwimn

记得以前作八数码问题的时候，用64位整数表示过数组，表示起来比较方便，这个跟本贴关系不大，但我觉得是个好思路，今天看到楼主的帖子，突然想起来，所以想加到这里，供大家参考[php]一个是从数组到整数
trans()
{long   iii;
  (b)=0;
  for(iii=o;iii<max;iii++)
(b)=((b)<<4)+a[iii];

   
}
另一个是从整数到数组
rtrans()
{
    long iii;
    unit64 ttt=(a);
    for (iii=max-1;iii>=0;iii--)
  {
         b[iii]=ttt&0xf;
         ttt>>=4;
   }
}[/php]

soloforce

Post by Lolita
继续，同样是面试题之一。

如何实现int64到十进制的转换

程序要求：
1、输入：一个int64（8字节，以int32类似方式存放）的指针
2、输出：该int64的十进制字符串表示式。
3、必须手动写出转换过程，不得借助其他库函数。
4、时间效率越高越好。

2. #include <stdio.h>
3. const int base=10;
4. const int max_int64_digits=20;
5. char hex[]="0123456789ABCDEF";
7. char * hex2dec(char *p, long long int *np)
8. {
9.     long long int n=*np;
10.     while(n){
11.         p--;
12.         *p=hex[n%base];
13.         n/=base;
14.     }
15.     return p;
16.    
17. }
19. int main()
20. {
21.     char dec[max_int64_digits+1];
22.     dec[max_int64_digits]=0;
23.     long long int test_int=998877665544332211;
24.     char * p=hex2dec(&dec[max_int64_digits], &test_int);
25.     printf("dec value is: %s \n", p);
26.    
27.     return 0;
28. }

复制代码

~/coding/c $  gcc hex2dec.c -std=c99
~/coding/c $  ./a.out
dec value is: 998877665544332211

刚好c99支持int64运算，所以实现起来很容易。

如果题目要求改成输出 int128 、 int256的10进制字符串的话不知有什么快速的算法？

DoDo

题 一:
10 进制数到 16 进制数的经典转换方法就是用长除法, 非常简单, 但依据本题的要求, 难点是如何表示任意大整数及相关运算. 代码如下

2. #include <stdio.h>
3. #include <string.h>
5. int mod = 0;
7. /* s / 16
8. * if result is short than the original s, return 1
9. * */
10. int div(char s[], int n)
11. {
12.         int i = 0;
13.         mod = 0;
14.         for (i = n - 1; i >= 0; i--) {
15.                 int t = ((mod * 10) + s[i]);
16.                 s[i] = t >> 4;
17.                 mod = t & 0x0F;
18.         }
19.         if (s[n - 1] != 0) return 0;
20.         if (s[n - 2] != 0) return 1;
21.         return 2;
22. }
24. int main(void)
25. {
26.         char src[1000];
27.         char dst[1000];
28.         int src_len = 0;
29.         int dst_len = 0;
31.         memset(dst, 0, sizeof(dst));
32.         printf("input number: ");
33.         scanf("%s", src);
34.         src_len = strlen(src);
36.         int i = 0;
37.         for (i = (src_len - 1) / 2; i >= 0; i--) {
38.                 int t = src[i] - '0';
39.                 src[i] = src[src_len - i - 1] - '0';
40.                 src[src_len - i - 1] = t;
41.         }
43.         while (src_len > 0) {
44.                 src_len -= div(src, src_len);
45.                 dst[dst_len++] = mod;
46.         }
48.         printf("result is: ");
49.         for (i = dst_len - 1; i >= 0; i--) {
50.                 printf("%c", dst[i] > 9 ? dst[i] - 10 + 'A' : dst[i] + '0');
51.         }
52.         printf("\n");
54.         return 0;
55. }

复制代码

运行结果

2. rf@RemoteFish:~/tmp/t$ time ./a.out
3. input number: 1234567890987654321234567890987654321234567890987654321
4. result is: CE3B5A137DD015278E09864703E4FF9952FF6B62C1CB1
6. real    0m17.300s
7. user    0m0.000s
8. sys     0m0.003s

复制代码

没有严格测试, 求证

DoDo

2. rf@RemoteFish:~/tmp/t$ time ./a.out
3. input number: 123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432123456789098765432
4. result is: 49E49DD122F6F55D224108B9204FD93151F7F53F23F679DC29147E0EB4AF2219EDA950D7C9B1B060E1E508F78B22C73EB238AF8670C6F1C4A205D49E050D6A1CAECB404F01BBE0D88A45DAFD493FC59A104D5B77934132CC93193E714692BAB0CC02657596755FCAEEDC993821D8AB01BD7AF63737CF53D89D9AC2462FA699E082906FD49EDA2A90191EAAFA06271299CE49BFA0480FFEF8C4616A320863129A051240936930A38A858B169ED9005CB368EC6CC4874E6614B8749B7A6FE4AE4AB9ED1E5825BA8D6E7A8A5DF74900BD9D0B8A97A6E04C7F54E70A3D8B47885B2CABBC6E3B9937DC2C07B4254A7CEC38D5BB7FF12379C78
6. real    0m6.567s
7. user    0m0.004s
8. sys     0m0.002s

复制代码

这是另一组稍微大一点的数据, 看起来执行效率一般

soloforce

嗯，DoDo的方法可行。
不过长除法效率的确偏低，题目要求之一就是要效率，这才是难点

PS：DoDo的对那个src数组进行反转那一步（for循环）好像不必要吧， div、src、dst全部统一用human阅读顺序存储也可以，即最高位字符放在 数组[0] 位置。

DoDo

做除法的时候位数会越来越少. 当然这个时候把指针偏移一下也行, 不过反转这种方法是高中写高精度计算器时留下的习惯, 写也写习惯了, 想也想习惯了, 呵呵

DoDo

Lolita 兄有什么好的想法吗?

我考虑过预计算 k * 10^n (k = 1 ~ 9) 的值并保存在文件中, 然后程序运行时首先载入数据, 然后只要根据用户的输入做加法即可, 这样对于 N 位十进制数只要做 N 次高精度加法即可, 而且加法的长度由 0~N 逐渐增加, 这样的效率应该比较高. 不过 预计算 是否属于合法的手段只有看题目的要求了, 而且这样也不能达到 任意精度 的要求.