我有一系列未签名的字符在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库),我可以给你一些东西.
毕竟,有点理论.在基本数值理论(模块化算术级别)中,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!";
我们有和无符号整数数组(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位算术偏移,足以保证正确的值).
功能更复杂但是在本质上,同样的问题(乘法和加法),所以我给出一些关于代码功能的技巧:
数据类型很重要,非常重要
如果您尝试将无符号整数与无符号整数相乘,则会得到另一个无符号整数.使用显式强制转换来获取unsigned long long int并且不会丢失数据.
总是使用无符号修饰符,别忘了!
功率2可以直接修改当前指数的2指数
gdb是你的朋友
我开发了另一种增加大数字的方法.这些最后我证明不是很多,但我认为它运作良好.如果它有虫子,请不要对我残忍.
...就这样!
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.(我不会做这个新代码,但如果有人有兴趣,可能会在考试后...)
京公网安备 11010802040832号 | 京ICP备19059560号-6 