二进制数精度如何计算（二进制数的高精度运算）

时间2025-09-19 00:03:15分类IT科技浏览5891

导读：我们知道，一个int型整数一般用32位二进制数存储，所表示的最大整数值为 231-1，对应1个10位的十进制整数。因此，一个更大的整数可能需要更多的二进制位来存储，在处理时需要对其进行高精度运算处理。...

我们知道，一个int型整数一般用32位二进制数存储，所表示的最大整数值为 231-1 ，对应1个10位的十进制整数。因此，一个更大的整数可能需要更多的二进制位来存储，在处理时需要对其进行高精度运算处理。

【例1】二进制加法

问题描述

二进制数相加与十进制数的长加非常相似。与十进制数字一样，从右到左，一次一列地进行各位对应数字的相加。与十进制加法不同，二进制位加法的进位规则是“逢二进一 ” 。

0 + 0 = 0

1 + 0 = 1

0 + 1 = 1

1 + 1 = 10

1 + 1 + 1 = 11

输入

第一行输入是整数N（1≤ N≤ 1000），表示测试用例的组数。之后N行，每行是一组测试用例，其中包含两个由单个空格字符分隔的二进制值。每个二进制值的最大长度为80位（二进制数字）。注：最大长度结果可能是81位（二进制数字）。

输出

对于每组测试用例，在一行中输出测试用例编号、空格和加法的二进制结果。必须省略额外的前导零。

输入样例

1001101 10010

1001001 11001

1000111 1010110

输出样例

1 1011111

2 1100010

3 10011101

（1）编程思路。

将二进制数用字符串保存，编写函数void binAdd(char *a,char *b,char *c) ，完成二进制数C=A+B这一功能。在函数中，先将字符串表示的二进制数A和B分别转换到整型数组X和Y中，转换时注意二进制字符串的最低位（如a[0]）对应到数组X的最高位（如x[strlen(a)-1]），二进制字符串的最高位（如a[strlen(a)-1]）对应到数组X的最低位（如x[0]）。然后将数组X和Y从下标0开始（也是二进制数的个位），逐位对应相加，逢二进一。

（2）源程序。

将上面的源程序提交给北大POJ题库POJ 2845 01000001（http://poj.org/problem?id=2845），可以Accepted 。

【例2】最大公约数

问题描述

给出两个二进制数A和B ，求它们的最大公约数。

输入

输入的第一行是T（1≤ T≤ 100），代表需要解决的测试用例数。

之后T行，每行包含两个二进制数A和B 。（0< A ，B ≤ 21000)

输出

对于每个测试用例，输出A和B的最大公约数，这个最大公约数也以二进制数显示。

输入样例

10 100

100 110

10010 1100

输出样例

Case #1: 10

Case #2: 10

Case #3: 110

（1）编程思路。

设gcd(a,b) 表示求两个二进制数的最大公约数。有

（1）若a ，b都为偶数，则 gcd(a,b) = 2*gcd(a/2,b/2) 。

（2）若 a为偶数，b为奇数，则 gcd(a,b) = gcd(a/2,b) 。

（3）若 a,b 都为奇数（设a大于等于b），则 gcd(a,b) = gcd((a-b),b) 。

按照这种思路直接求两个二进制数的最大公约数就比较简单了。主要涉及二进制的相减运算（a-b），相减时总是大数减小数（即a>b）；二进制数除以2 ，这个操作比较简单，直接去掉个位数即可，也就是删除bit数组中的bit[0]元素，同时len减1 。

定义结构体类型

struct BigNumber

{

int len; // 保存二进制数的位数

int bit[1005]; // 保存各位的数字，每个数组元素保存二进制数的1位数，其中bit[0]保存二进制数的个位数。

}; 的变量来保存二进制数。

同时定义4个函数，分别实现两个二进制数的大小比较、两个二进制数相减、一个二进制数除以2 、求两个二进制数的最大公约数等功能。

（2）源程序。

#include <stdio.h> #include <string.h> struct BigNumber { int len; int bit[1005]; }; int compare(struct BigNumber n1,struct BigNumber n2) // 比较两个大数的大小，n1小于n2则返回1 { if (n1.len<n2.len) return 1; if (n1.len>n2.len) return 0; int i; for (i=n1.len-1;i>=0;i--) { if (n1.bit[i]<n2.bit[i]) return 1; if (n1.bit[i]>n2.bit[i]) return 0; } return 0; } struct BigNumber minus(struct BigNumber n1,struct BigNumber n2) // 大数n1 - n2 { struct BigNumber ret; int i; ret=n1; for (i=0;i<n2.len;i++) { ret.bit[i]=ret.bit[i]-n2.bit[i]; if (ret.bit[i]<0) { ret.bit[i+1]--; // 向前一位借1当2 ret.bit[i]+=2; } } for (;i<ret.len;i++) // 处理n1比n2多出的高位 { if (ret.bit[i]>=0) // 向更高位不再有借位 break; else { ret.bit[i+1]--; // 向前一位借1当2 ret.bit[i]+=2; } } while (ret.len>=1 && !ret.bit[ret.len-1]) // 去掉前导0 ret.len--; return ret; } struct BigNumber div2(struct BigNumber n) // 大数n除以2 { struct BigNumber ret; ret.len=n.len-1; int i; for (i=0;i<ret.len;i++) // 去掉最末位的0即可 ret.bit[i]=n.bit[i+1]; return ret; } void gcd(struct BigNumber n1,struct BigNumber n2) // 求n1和n2的最大公约数并输出 { int b=0,i; while (n1.len && n2.len) { if (n1.bit[0]) { if(n2.bit[0]) // n1 、n2均为奇数，gcd(n1,n2)=gcd((n2-n1),n1) （设n2大于等于n1） { if (compare(n1,n2)) n2=minus(n2,n1); else n1=minus(n1,n2); } else // n2为偶数，n1为奇数。gcd(n1,n2)=gcd(n1,n2/2) n2=div2(n2); } else { if(n2.bit[0]) // n1为偶数，n2为奇数。gcd(n1,n2)=gcd(n1/2,n2) n1=div2(n1); else // n1 、n2都为偶数。gcd(n1,n2)=2*gcd(n1/2,n2/2) { n1=div2(n1); n2=div2(n2); b++; } } } if (n2.len) for (i=n2.len-1;i>=0;i--) printf("%d",n2.bit[i]); else for (i=n1.len-1;i>=0;i--) printf("%d",n1.bit[i]); while (b--) printf("0"); printf("\n"); } int main() { int t,iCase=0; struct BigNumber n1,n2; char str1[1005],str2[1005]; scanf("%d",&t); while (t--) { scanf("%s%s",str1,str2); int i; n1.len=strlen(str1); for (i=0;i<n1.len;i++) // 二进制字符串的str1[0]是二进制数的最高位，二者是逆序的 n1.bit[i]=str1[n1.len-1-i]-0; n2.len=strlen(str2); for (i=0;i<n2.len;i++) n2.bit[i]=str2[n2.len-1-i]-0; printf("Case #%d: ",++iCase); gcd(n1,n2); } return 0; }

将上面的源程序提交给 HDU题库 HDU 5050 Divided Land（http://acm.hdu.edu.cn/showproblem.php?pid=5050），可以Accepted 。

【例3】N!

问题描述

表达式N！，读作N的阶乘，表示前N个正整数的乘积。如果N的阶乘是十六进制的，没有前导零，你能告诉我们其中有多少个零吗？例如，15！=（13077775800）16 ，其中有3个零。

输入

输入包含几个测试用例。每个测试用例有一行，包含非负十进制整数N（N≤ 100) 。你需要计算N！对应的十六进制数中的零的个数。负数终止输入。

输出

对于每个非负整数N ，输出一行正好包含一个整数，为N！中的零的个数。

输入样例

-1

输出样例

（1）编程思路。

当N值较大时，N!的一个很大的数。为此定义结构体类型

struct BigNumber

{

int len; // 保存十六进制数的位数

int bit[1005]; // 保存各位的数字，每个数组元素保存十六进制数的1位数，其中bit[0]保存十六进制数的个位数。

};

的变量来保存N!的十六进制结果。

编写一个函数 struct BigNumber mul(struct BigNumber a,int b)完成十六进制整数a与十进制整数b相乘，结果是一个十六进制数并作为函数值返回，在函数中，将bit数组中保存的len位数字从下标0开始，逐位与int型整数b相乘，在相乘的过程中对乘积进行逢十六进一即可。

（2）源程序。

#include <stdio.h> #include <string.h> struct BigNumber { int len; int num[205]; }; struct BigNumber mul(struct BigNumber a,int b) // 十六进制整数a与十进制整数b相乘 { struct BigNumber ret; memset(ret.num,0,sizeof(ret.num)); int i; for (i=0;i<a.len;i++) { ret.num[i]=ret.num[i]+a.num[i]*b; ret.num[i+1]=ret.num[i]/16; // 向前进位 ret.num[i]%=16; } i=a.len; while (ret.num[i]!=0) // 高位继续向前进位 { ret.num[i+1]=ret.num[i]/16; ret.num[i]%=16; i++; } ret.len=i; return ret; } int main() { struct BigNumber fact[101]; fact[1].len=1; fact[1].num[0]=1; int i,j; for (i=2;i<=100;i++) fact[i]=mul(fact[i-1],i); int ans[101]={0,0}; for (i=2;i<=100;i++) { int cnt=0; for (j=fact[i].len-1;j>=0;j--) if (fact[i].num[j]==0) cnt++; ans[i]=cnt; } int n; while (scanf("%d",&n) && n>=0) { printf("%d\n",ans[n]); } return 0; }

将上面的源程序提交给 HDU题库HDU 2940 Hex Factorial（http://acm.hdu.edu.cn/showproblem.php?pid=2940），可以Accepted 。

【例4】进制转换

问题描述

编写一个程序，将一个基数的数字转换为另一个基数。有62个不同的数字：｛0-9 ，A-Z ，a-z｝

输入

第一行输入包含一个正整数N ，表示测试用例的组数。之后N行，每一行将有一个十进制整数表示的输入基数，后跟一个十进制整数表示的输出基数，再跟一个以输入基数表示的数字。输入基数和输出基数都将在2到62的范围内。A=10 ，B=11 ，… ，Z=35，a=36 ，b=37 ，…，z=61（0-9有其通常的含义）。

输出

程序的输出应包括每执行一次基本转换的三行输出。第一行应该是十进制的输入基数，后跟空格，然后是输入数字（以输入基数表示）。第二行应该是输出基数，后跟一个空格，然后是输出数字（以输出基数表示）。第三输出行为空。

输入样例

62 2 abcdefghiz

10 16 1234567890123456789012345678901234567890

16 35 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 23 333YMHOUE8JPLT7OX6K9FYCQ8A

23 49 946B9AA02MI37E3D3MMJ4G7BL2F05

49 61 1VbDkSIMJL3JjRgAdlUfcaWj

61 5 dl9MDSWqwHjDnToKcsWE1S

5 10 42104444441001414401221302402201233340311104212022133030

输出样例

62 abcdefghiz

2 11011100000100010111110010010110011111001001100011010010001

10 1234567890123456789012345678901234567890

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 333YMHOUE8JPLT7OX6K9FYCQ8A

23 946B9AA02MI37E3D3MMJ4G7BL2F05

49 1VbDkSIMJL3JjRgAdlUfcaWj

61 dl9MDSWqwHjDnToKcsWE1S

5 42104444441001414401221302402201233340311104212022133030

10 1234567890123456789012345678901234567890

（1）编程思路。

一般不同进制转换是以10进制为中介进行转换，但若转换的数较大的话，复杂度较高。可以采用短除法直接将A进制数x直接转化为B进制数y ，其基本原理是将x每次除以B ，得到的余数的逆序列是就B进制表示的结果。每次除的时候，从最高位开始除，商作为x当前位的值保存，得到的余数乘以A加到下一位，一直到最低位。最后得到的余数作为B进制数y的某位保存。重复这一过程，直到A进制数x为0 。

用一个例子简单说明：将十六进制数6E转换为八进制数。

为方便说明，设用数组x存储十六进制的各位数字，用数组y存储转换后得到的八进制各位数字。

首先将表示十六值数6E的字符串转换为x中存储的各位整数。转换后 x[0]=14，x[1]=6 。

从高位开始除，x[1]=6 ， 6/8商为0，余数为6 ，将商保存到当前位x[1]中，x[1]=0 ，将余数 6*16加到下一位x[0]中，x[0]=14+6*16=110 。

再接着进行下一位的除法。 X[0]=110 ，110/8商为13 ，余数为6 ，将商保存到当前位x[0]中，x[0]=13 ，因为这是最低位（个位），一次除法结束，余数6作为转换后八进制数的数字保存到y数组中，y[0]=6 。

去掉x数组的高位前导0后，x数组中 x[0]=13 。

X!=0 ，继续重复上面的过程。x[0]=13 ，13/8商为1，余数为5 ，将商保存到当前位x[0]中，x[0]=1 ，同样因为这是最低位（个位），一次除法结束，余数作为转换后八进制数的数字保存到y数组中，y[1]=5 。

X!=0 ，继续重复上面的过程。x[0]=1 ， 1/8商为0 ，余数为1，将商保存到当前位x[0]中，x[0]=0 ，同样因为这是最低位（个位），一次除法结束，余数作为转换后八进制数的数字保存到y数组中，y[2]=1。

至此，X等于0 ，转换结束。再将数组y中保存的数字按逆序的方式转换为字符串 156 。也就是说，十六进制数6E转换为八进制数为 156。

（2）源程序。

#include <stdio.h> #include <string.h> #define MAX_LEN 600 void Base1toBase2(char a[],char b[],int base1,int base2) { int num1[MAX_LEN],num2[MAX_LEN]; int n,i,j,k; n = strlen(a); j = 0; for (i = n - 1;i >= 0 ; i --) { if (a[i]>=A && a[i]<=Z) num1[j++]=a[i]-A+10; else if (a[i]>=a && a[i]<=z) num1[j++]=a[i]-a+36; else num1[j++]=a[i]-0; } k=0; while (n!=0) { for (i=n-1;i>0;i--) // 短除法 { num1[i-1]+=num1[i]%base2*base1; num1[i]/=base2; } num2[k++]=num1[0]%base2; num1[0]/=base2; while (n>0 && num1[n-1]==0) n--; } for (j=0,i=k-1;i>=0;i--) { if (num2[i]<10) b[j++]=num2[i]+0; else if (num2[i]<36) b[j++]=num2[i]-10+A; else b[j++]=num2[i]-36+a; } b[j]=\0; } int main() { int t,base1,base2; char src[MAX_LEN],dest[MAX_LEN],tmp[MAX_LEN]; scanf("%d",&t); while (t--) { scanf("%d%d",&base1,&base2); scanf("%s",src); Base1toBase2(src,dest,base1,base2); printf("%d %s\n",base1,src); printf("%d %s\n\n",base2,dest); } return 0; }

将上面的源程序提交给北大 POJ 题库 POJ 1220 NUMBER BASE CONVERSION（http://poj.org/problem?id=1220），可以Accepted 。

声明：本站所有文章，如无特殊说明或标注，均为本站原创发布。任何个人或组织，在未征得本站同意时，禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益，可联系我们进行处理。

展开全文READ MORE