在c中的基数10中打印大基数256数组
我有一系列未签名的字符在c我试图在10号基础上打印，我被卡住了。 我认为这将在代码中得到更好的解释，因此，给出：
unsigned char n[3]; char[0] = 1; char[1] = 2; char[2] = 3; 我想打印197121。
这对于小型256基数arrays来说是微不足道的。 一个可以简单地1 * 256 ^ 0 + 2 * 256 ^ 1 + 3 * 256 ^ 2。
但是，如果我的数组大100字节，那么这很快就会成为一个问题。 C中没有100字节大的整数类型，这就是我将数字存储在unsigned char数组中的原因。
我怎么能在10号基地有效地打印这个数字呢？
我有点迷茫。
仅使用标准C库没有简单的方法。 您要么自己编写函数（不推荐），要么使用GMP等外部库。
例如，使用GMP，您可以：
unsigned char n[100]; // number to print mpz_t num; mpz_import(num, 100, -1, 1, 0, 0, n); // convert byte array into GMP format mpz_out_str(stdout, 10, num); // print num to stdout in base 10 mpz_clear(num); // free memory for num
当我看到这个问题时，我打算解决它，但那一刻我很忙。 上周末我可以获得一些空闲时间的奖金，所以我考虑了我的未决挑战。
首先，我建议你考虑上面的回应。 我从不使用GMP库，但我确信它比手工编写的代码更好。 另外，您可能有兴趣分析bc计算器的代码; 它可以使用大数字，我曾经测试过我自己的代码。
好的，如果您仍然对代码感兴趣，可以自己做（只有支持C语言和标准C库），我可以给你一些东西。
毕竟，有点理论。 在基本数值理论（模块化算术级别）中，theres是一种激励我得到一个解决方案的算法; 乘法和幂算法求解^ N模块m：
Result := 1; for i := k until i = 0 if n_i = 1 then Result := (Result * a) mod m; if i != 0 then Result := (Result * Result) mod m; end for;
其中k是二进制表示中N的一个数字减去N中的一个，并且n_i是i二进制数字。 例如（N是指数）：
N = 44 -> 1 0 1 1 0 0 k = 5 n_5 = 1 n_4 = 0 n_3 = 1 n_2 = 1 n_1 = 0 n_0 = 0
当我们进行模块操作时，作为整数除法，我们可以丢失部分数，所以我们只需要修改算法就不要错过相关数据。
这是我的代码（注意它是一个特殊的代码，可能是计算机拱的强依赖。基本上我玩C语言的数据长度所以，小心，因为我的数据长度不一样）：
#include #include #include #include enum { SHF = 31, BMASK = 0x1 << SHF, MODULE = 1000000000UL, LIMIT = 1024 }; unsigned int scaleBigNum(const unsigned short scale, const unsigned int lim, unsigned int *num); unsigned int pow2BigNum(const unsigned int lim, unsigned int *nsrc, unsigned int *ndst); unsigned int addBigNum(const unsigned int lim1, unsigned int *num1, const unsigned int lim2, unsigned int *num2); unsigned int bigNum(const unsigned short int base, const unsigned int exp, unsigned int **num); int main(void) { unsigned int *num, lim; unsigned int *np, nplim; int i, j; for(i = 1; i < LIMIT; ++i) { lim = bigNum(i, i, &num); printf("%i^%i == ", i, i); for(j = lim - 1; j > -1; --j) printf("%09u", num[j]); printf("\n"); free(num); } return 0; } /* bigNum: Compute number base^exp and store it in num array @base: Base number @exp: Exponent number @num: Pointer to array where it stores big number Return: Array length of result number */ unsigned int bigNum(const unsigned short int base, const unsigned int exp, unsigned int **num) { unsigned int m, lim, mem; unsigned int *v, *w, *k; //Note: mem has the exactly amount memory to allocate (dinamic memory version) mem = ( (unsigned int) (exp * log10( (float) base ) / 9 ) ) + 3; v = (unsigned int *) malloc( mem * sizeof(unsigned int) ); w = (unsigned int *) malloc( mem * sizeof(unsigned int) ); for(m = BMASK; ( (m & exp) == 0 ) && m; m >>= 1 ) ; v[0] = (m) ? 1 : 0; for(lim = 1; m > 1; m >>= 1) { if( exp & m ) lim = scaleBigNum(base, lim, v); lim = pow2BigNum(lim, v, w); k = v; v = w; w = k; } if(exp & 0x1) lim = scaleBigNum(base, lim, v); free(w); *num = v; return lim; } /* scaleBigNum: Make an (num[] <- scale*num[]) big number operation @scale: Scalar that multiply big number @lim: Length of source big number @num: Source big number (array of unsigned int). Update it with new big number value Return: Array length of operation result Warning: This method can write in an incorrect position if we don't previous reallocate num (if it's necessary). bigNum method do it for us */ unsigned int scaleBigNum(const unsigned short scale, const unsigned int lim, unsigned int *num) { unsigned int i; unsigned long long int n, t; for(n = 0, t = 0, i = 0; i < lim; ++i) { t = (n / MODULE); n = ( (unsigned long long int) scale * num[i] ); num[i] = (n % MODULE) + t; // (n % MODULE) + t always will be smaller than MODULE } num[i] = (n / MODULE); return ( (num[i]) ? lim + 1 : lim ); } /* pow2BigNum: Make a (dst[] <- src[] * src[]) big number operation @lim: Length of source big number @src: Source big number (array of unsigned int) @dst: Destination big number (array of unsigned int) Return: Array length of operation result Warning: This method can write in an incorrect position if we don't previous reallocate num (if it's necessary). bigNum method do it for us */ unsigned int pow2BigNum(const unsigned int lim, unsigned int *src, unsigned int *dst) { unsigned int i, j; unsigned long long int n, t; unsigned int k, c; for(c = 0, dst[0] = 0, i = 0; i < lim; ++i) { for(j = i, n = 0; j < lim; ++j) { n = ( (unsigned long long int) src[i] * src[j] ); k = i + j; if(i != j) { t = 2 * (n % MODULE); n = 2 * (n / MODULE); // (i + j) dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (t % MODULE); ++k; // (i + j + 1) dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + ( (t / MODULE) + (n % MODULE) ); ++k; // (i + j + 2) dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (n / MODULE); } else { dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (n % MODULE); ++k; // (i + j) dst[k] = ( (k > c) ? ((c = k), 0) : dst[k] ) + (n / MODULE); } for(k = i + j; k < (lim + j); ++k) { dst[k + 1] += (dst[k] / MODULE); dst[k] %= MODULE; } } } i = lim << 1; return ((dst[i - 1]) ? i : i - 1); } /* addBigNum: Make a (num2[] <- num1[] + num2[]) big number operation @lim1: Length of source num1 big number @num1: First source operand big number (array of unsigned int). Should be smaller than second @lim2: Length of source num2 big number @num2: Second source operand big number (array of unsigned int). Should be equal or greater than first Return: Array length of operation result or 0 if num1[] > num2[] (dosen't do any op) Warning: This method can write in an incorrect position if we don't previous reallocate num2 */ unsigned int addBigNum(const unsigned int lim1, unsigned int *num1, const unsigned int lim2, unsigned int *num2) { unsigned long long int n; unsigned int i; if(lim1 > lim2) return 0; for(num2[lim2] = 0, n = 0, i = 0; i < lim1; ++i) { n = num2[i] + num1[i] + (n / MODULE); num2[i] = n % MODULE; } for(n /= MODULE; n; ++i) { num2[i] += n; n = (num2[i] / MODULE); } return (lim2 > i) ? lim2 : i; }
编译：
gcc -o bgn .c -Wall -O3 -lm //Math library if you wants to use log func
要检查结果，请使用直接输出作为输入到bc。 简易shell脚本：
#!/bin/bash select S in ` awk -F '==' '{print $1 " == " $2 }' | bc`; do 0; done; echo "Test Finished!";
我们有和unsigned int（4个字节）数组，我们在数组的每个int中存储9个数字（％1000000000UL）; 因此num [0]我们将有前9个数字，num [1]我们将有数字10到18，num [2] …我使用常规内存工作，但改进可以用dinamic内存。 好的，但它的长度可能是多少？ （或者我们需要分配多少内存？）。 使用bc计算器（bc -l和mathlib）我们可以确定有多少位数有一个数字：
l(a^N) / l(10) // Natural logarith to Logarithm base 10
如果我们知道数字，我们知道我们需要的金额整数：
( l(a^N) / (9 * l(10)) ) + 1 // Truncate result
如果使用诸如（2 ^ k）^ N之类的值，则可以使用以下表达式解析对数：
( k*N*l(2)/(9*l(10)) ) + 1 // Truncate result
确定整数数组的确切长度。 例：
256^800 = 2^(8*800) ---> l(2^(8*800))/(9*l(10)) + 1 = 8*800*l(2)/(9*l(10)) + 1
值1000000000UL （10 ^ 9）常数非常重要。 一个像10000000000UL（10 ^ 10）这样的常数不起作用，因为可以产生和检测到溢出（尝试数字16 ^ 16和10 ^ 10常数发生）和一个常数更小，如1000000000UL（10 ^ 8）是正确的但是我们需要保留更多内存并执行更多步骤。 10 ^ 9是32位无符号整数和64位无符号长整数int的关键常量。
代码有两个部分，Multiply（简单）和Power by 2（更难）。 乘法只是乘法和缩放并传播整数溢出。 它采用数学中的关联属性原理完全相反的原理，所以如果k（A + B + C）我们想要kA + kB + kC，其中数将是k * A * 10 ^ 18 + k * B * 10 ^ 9 + k C.很明显，k C操作可以生成大于999 999 999的数字，但绝不会大于0xFF FF FF FF FF FF FF FF。 在乘法中不能出现大于64位的数字，因为C是32位的无符号整数，k是16位的无符号短整数。 在worts案例中，我们将有这个数字：
k = 0x FF FF; C = 0x 3B 9A C9 FF; // 999999999 n = k*C = 0x 3B 9A | 8E 64 36 01; n % 1000000000 = 0x 3B 99 CA 01; n / 1000000000 = 0x FF FE;
在Mul k B之后，我们需要从C的最后一次乘法（B = k B +（C /模块）） 添加0x FF FE ，依此类推（我们有18位算术偏移，足以保证正确的值）。
function更复杂但是在本质上，同样的问题（乘法和加法），所以我给出了一些关于代码function的技巧：
- 数据类型很重要，非常重要
- 如果您尝试将无符号整数与无符号整数相乘，则会得到另一个无符号整数。 使用显式强制转换来获取unsigned long long int并且不会丢失数据。
- 总是使用无符号修饰符，别忘了！
- 功率2可以直接修改当前指数之前的2指数
- gdb是你的朋友
我开发了另一种增加大数字的方法。 这些最后我certificate不是很多，但我认为它运作良好。 如果它有虫子，请不要对我残忍。
…就这样！
PD1：开发于
Intel(R) Pentium(R) 4 CPU 1.70GHz Data length: unsigned short: 2 unsigned int: 4 unsigned long int: 4 unsigned long long int: 8
它花费的数字如256 ^ 1024：
real 0m0.059s user 0m0.033s sys 0m0.000s
一个bucle，计算我^我在哪里我去i = 1 … 1024：
real 0m40.716s user 0m14.952s sys 0m0.067s
对于诸如65355 ^ 65355之类的数字，花费的时间是疯狂的。
PD2：我的回复太迟了，但我希望我的代码能有用。
PD3：对不起，用英语解释我是我最糟糕的障碍之一！
最后更新：我只是想到了使用相同的算法但是其他实现，改进响应并减少使用的内存量（我们可以使用unsigned int的完全位）。 秘密：n ^ 2 = n * n = n *（n – 1 + 1）= n *（n – 1）+ n。 （我不会做这个新代码，但如果有人感兴趣，可能会在考试后…）
我不知道你是否还需要解决方案，但我写了一篇关于这个问题的文章 。 它显示了一个非常简单的算法，可用于将任意长数字与基数X转换为相应数量的基数Y.该算法是用Python编写的，但它实际上只有几行而且不使用任何Python魔法。 我也需要这样一个C实现算法，但决定用Python描述它有两个原因。 首先，任何了解用伪编程语言编写的算法的人都可以阅读Python，其次，我不允许发布C版本，因为我是为公司做的。 看看你会发现这个问题一般可以轻松解决。 C中的实现应该是直截了当的……
这是一个完成你想要的function：
#include #include // for size_t double getval(unsigned char *arr, size_t len) { double ret = 0; size_t cur; for(cur = 0; cur < len; cur++) ret += arr[cur] * pow(256, cur); return ret; }
这看起来非常易读。 只需传递要转换的unsigned char *数组和大小。 请注意，它不会是完美的 - 对于任意精度，我建议查看GNU MP BigNum库，正如已经建议的那样。
作为奖励，我不喜欢以小端顺序存储你的数字，所以如果你想以big-endian顺序存储base-256数字，这里有一个版本：
#include // for size_t double getval_big_endian(unsigned char *arr, size_t len) { double ret = 0; size_t cur; for(cur = 0; cur < len; cur++) { ret *= 256; ret += arr[cur]; } return ret; }
只需要考虑的事情。
提出这个建议可能为时已晚或太无关紧要，但是你可以将每个字节存储为两个基数10位（或一个基数100）而不是一个基数256吗？ 如果你还没有实现除法，那么这意味着你所拥有的只有加法，减法和乘法; 那些不应该太难转换。 一旦你完成了它，打印它将是微不足道的。