二进制数的高精度运算

        我们知道,一个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位(二进制数字)。

输出

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

输入样例

3

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)源程序。

#include <stdio.h>
#include <string.h>
void binAdd(char *a,char *b,char *c)
{
 int len1=strlen(a),len2=strlen(b);
 int x[91],y[91],z[91];
 int len=len1>len2?len1:len2;
 memset(x,0,sizeof(x));
 memset(y,0,sizeof(y));
 memset(z,0,sizeof(z));
 int i;
 for (i=len1-1;i>=0;i--)
 x[len1-1-i]=a[i]-'0';
 for (i=len2-1;i>=0;i--)
 y[len2-1-i]=b[i]-'0';
 int cf=0;
 for (i=0;i<len;i++)
 {
 z[i]=(x[i]+y[i]+cf)%2;
 cf=(x[i]+y[i]+cf)/2;
 }
 z[len++]=cf;
 while (len>=0 && z[len-1]==0) // 去前置0
 len--;
 if (len==0) // a+b=0时特判
 {
 c[0]='0';
 c[1]='\0';
 return ;
 }
 for (i=0;i<len;i++)
 c[i]=z[len-1-i]+'0';
 c[len]='\0';
}
int main()
{
 char s1[91],s2[91],ans[91];
 int n,i;
 scanf("%d",&n);
 for (i=1;i<=n;i++)
 {
 scanf("%s%s",s1,s2);
 binAdd(s1,s2,ans);
 printf("%d %s\n",i,ans);
 }
 return 0;
}

       将上面的源程序提交给 北大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的最大公约数,这个最大公约数也以二进制数显示。

输入样例

3

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

15

-1

输出样例

0

3

       (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有其通常的含义)。

输出

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

输入样例

8

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

 

16 3A0C92075C0DBF3B8ACBC5F96CE3F0AD2

35 333YMHOUE8JPLT7OX6K9FYCQ8A

 

35 333YMHOUE8JPLT7OX6K9FYCQ8A

23 946B9AA02MI37E3D3MMJ4G7BL2F05

 

23 946B9AA02MI37E3D3MMJ4G7BL2F05

49 1VbDkSIMJL3JjRgAdlUfcaWj

 

49 1VbDkSIMJL3JjRgAdlUfcaWj

61 dl9MDSWqwHjDnToKcsWE1S

 

61 dl9MDSWqwHjDnToKcsWE1S

5 42104444441001414401221302402201233340311104212022133030

 

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。

作者:aTeacher原文地址:https://www.cnblogs.com/cs-whut/p/16930315.html

%s 个评论

要回复文章请先登录注册