我在 c 中有一组无符号字符，我试图以 10 为基数打印，但我被卡住了。我认为这将在代码中得到更好的解释，因此，鉴于：
unsigned char n[3];
char[0] = 1;
char[1] = 2;
char[2] = 3;
我想打印 197121。
这对于小型基数 256 阵列来说是微不足道的。可以简单地 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 库）也许我可以给您一些东西。
首先，一点点理论。在基本数值理论（模算术水平）中，有一种算法可以启发我找到一个解决方案；乘法和幂算法求解a^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_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 <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>
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 <name>.c -Wall -O3 -lm //Math library if you wants to use log func
要检查结果，请使用直接输出 as 和输入到 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]... 我使用常规内存来工作，但可以使用动态内存进行改进。好的，但是它可能是数组的长度？（或者我们需要分配多少内存？）。使用 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 位 unsigned int 和 64 位 unsigned long long int 的关键常数。
代码有两部分，乘法（简单）和乘以 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 位的无符号短整数。在麦芽汁的情况下，我们将有这个数字：
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 的最后一次乘法中添加 0x FF FE（ B = k B + (C / module) ），依此类推（我们有 18 位算术偏移量，足以保证正确的值）。
功率更复杂，但本质上是相同的问题（乘法和加法），所以我给出了一些关于代码功率的技巧：
我开发了另一种添加大数字的方法。最后这些我没有证明太多，但我认为它运作良好。如果它有错误，请不要对我残忍。
...就这样！
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
计算 i^i 的 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中的实现应该是直截了当的......
这是一个可以满足您要求的功能：
#include <math.h>
#include <stddef.h> // 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 库，正如已经建议的那样。
作为奖励，我不喜欢您以 little-endian 顺序存储您的数字，所以如果您想以 big-endian 顺序存储 base-256 数字，这里有一个版本：
#include <stddef.h> // 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 为基数的数字？如果您还没有实现除法，那么这意味着您所拥有的只是加法、减法，也许还有乘法；那些不应该太难转换。一旦你这样做了，打印它就很简单了。
由于我对提供的其他答案不满意，我决定自己编写一个替代解决方案：
#include <stdlib.h>
#define BASE_256 256
char *largenum2str(unsigned char *num, unsigned int len_num)
{
int temp;
char *str, *b_256 = NULL, *cur_num = NULL, *prod = NULL, *prod_term = NULL;
unsigned int i, j, carry = 0, len_str = 1, len_b_256, len_cur_num, len_prod, len_prod_term;
//Get 256 as an array of base-10 chars we'll use later as our second operand of the product
for ((len_b_256 = 0, temp = BASE_256); temp > 0; len_b_256++)
{
b_256 = realloc(b_256, sizeof(char) * (len_b_256 + 1));
b_256[len_b_256] = temp % 10;
temp = temp / 10;
}
//Our first operand (prod) is the last element of our num array, which we'll convert to a base-10 array
for ((len_prod = 0, temp = num[len_num - 1]); temp > 0; len_prod++)
{
prod = realloc(prod, sizeof(*prod) * (len_prod + 1));
prod[len_prod] = temp % 10;
temp = temp / 10;
}
while (len_num > 1) //We'll stay in this loop as long as we still have elements in num to read
{
len_num--; //Decrease the length of num to keep track of the current element
//Convert this element to a base-10 unsigned char array
for ((len_cur_num = 0, temp = num[len_num - 1]); temp > 0; len_cur_num++)
{
cur_num = (char *)realloc(cur_num, sizeof(char) * (len_cur_num + 1));
cur_num[len_cur_num] = temp % 10;
temp = temp / 10;
}
//Multiply prod by 256 and save that as prod_term
len_prod_term = 0;
prod_term = NULL;
for (i = 0; i < len_b_256; i++)
{ //Repeat this loop 3 times, one for each element in {6,5,2} (256 as a reversed base-10 unsigned char array)
carry = 0; //Set the carry to 0
prod_term = realloc(prod_term, sizeof(*prod_term) * (len_prod + i)); //Allocate memory to save prod_term
for (j = i; j < (len_prod_term); j++) //If we have digits from the last partial product of the multiplication, add it here
{
prod_term[j] = prod_term[j] + prod[j - i] * b_256[i] + carry;
if (prod_term[j] > 9)
{
carry = prod_term[j] / 10;
prod_term[j] = prod_term[j] % 10;
}
else
{
carry = 0;
}
}
while (j < (len_prod + i)) //No remaining elements of the former prod_term, so take only into account the results of multiplying mult * b_256
{
prod_term[j] = prod[j - i] * b_256[i] + carry;
if (prod_term[j] > 9)
{
carry = prod_term[j] / 10;
prod_term[j] = prod_term[j] % 10;
}
else
{
carry = 0;
}
j++;
}
if (carry) //A carry may be present in the last term. If so, allocate memory to save it and increase the length of prod_term
{
len_prod_term = j + 1;
prod_term = realloc(prod_term, sizeof(*prod_term) * (len_prod_term));
prod_term[j] = carry;
}
else
{
len_prod_term = j;
}
}
free(prod); //We don't need prod anymore, prod will now be prod_term
prod = prod_term;
len_prod = len_prod_term;
//Add prod (formerly prod_term) to our current number of the num array, expressed in a b-10 array
carry = 0;
for (i = 0; i < len_cur_num; i++)
{
prod[i] = prod[i] + cur_num[i] + carry;
if (prod[i] > 9)
{
carry = prod[i] / 10;
prod[i] -= 10;
}
else
{
carry = 0;
}
}
while (carry && (i < len_prod))
{
prod[i] = prod[i] + carry;
if (prod[i] > 9)
{
carry = prod[i] / 10;
prod[i] -= 10;
}
else
{
carry = 0;
}
i++;
}
if (carry)
{
len_prod++;
prod = realloc(prod, sizeof(*prod) * len_prod);
prod[len_prod - 1] = carry;
carry = 0;
}
}
str = malloc(sizeof(char) * (len_prod + 1)); //Allocate memory for the return string
for (i = 0; i < len_prod; i++) //Convert the numeric result to its representation as characters
{
str[len_prod - 1 - i] = prod[i] + '0';
}
str[i] = '\0'; //Terminate our string
free(b_256); //Free memory
free(prod);
free(cur_num);
return str;
}
这一切背后的想法都源于简单的数学。对于任何以 256 为底的数字，其以 10 为底的表示可以计算为：
num[i]*256^i + num[i-1]*256^(i-1) + (···) + num[2]*256^2 + num[1]*256^1 + num[0]*256^0
扩展为：
(((((num[i])*256 + num[i-1])*256 + (···))*256 + num[2])*256 + num[1])*256 + num[0]
所以我们所要做的就是一步一步地将数字数组的每个元素乘以 256，然后将下一个元素加到它上面，依此类推……这样我们就可以得到以 10 为底的数字。