二進位數的高精度運算

来源:https://www.cnblogs.com/cs-whut/archive/2022/11/29/16930315.html
-Advertisement-
Play Games

1 準備工作 獲取class文件byte[] public static byte[] getFileBytes(File file) { try (FileInputStream fileInputStream = new FileInputStream(file)) { int availabl ...


        我們知道,一個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。


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • 〇、參考資料 1、hutool介紹 https://blog.csdn.net/abst122/article/details/124091375 2、Spring Boot+Mybatis實現登錄註冊 https://www.cnblogs.com/wiki918/p/16221758.html ...
  • Filter過濾器02 5.Filter過濾器生命周期 Filter生命周期圖解 驗證-Tomcat來創建Filter實例,只會創建一個實例 package com.filter; import javax.servlet.*; import javax.servlet.http.HttpServl ...
  • 以前學習的過程中,有聽過 EasyExcel 這麼一個東西,不過從來沒用過,所以,正好藉此機會學習,看看如何使用它來實現需求。 在學習 EasyExcel 的這段時間里,也瞭解到工作中這種導入導出的需求還是挺常見的,所以決定記錄下來。 ...
  • 一.小結 1.字元串是封裝在String類中的對象。要創建一個字元串,可以使用11種構造方法之一,也可以使用字元串直接量進行簡捷初始化。 2.String對象是不可變的,它的內容不能改變。為了提高效率和節省記憶體,如果兩個直接量字元串有相同的字元序列,Java虛擬機就將它們存儲在一個對象中。這個獨特的 ...
  • layout: post categories: Java title: Java 中你絕對沒用過的一個關鍵字? tagline: by 子悠 tags: 子悠 前面的文章給大家介紹瞭如何自定義一個不可變類,沒看過的小伙伴建議去看一下,這節課給大家介紹一個 Java 中的一個關鍵字 Record,那 ...
  • 代碼1 #include <iostream> using namespace std; class A{ public: A(int _a):ma(_a){ cout<<"A()"<<endl; } ~A(){ cout<<"~A()"<<endl; } protected: int ma; }; ...
  • 您好,我是湘王,這是我的博客園,歡迎您來,歡迎您再來~ 有時某些業務或者功能,需要在用戶請求到來之前就進行一些判斷或執行某些動作,就像在Servlet中的FilterChain過濾器所做的那樣,Spring Security也有類似機制。Spring Security有三種增加過濾器的方式:addF ...
  • 初學flask部署,踩了一些坑記錄一下。 uwsgi配置 對於uwsgi的安裝不詳細描述 在centos7上部署flask 大型應用的時候會使用工廠模式create_app(),放置在一個module的__init__.py中, uwsgi配置的時候應該就不要使用 wsgi-file 來進行配置,查 ...
一周排行
    -Advertisement-
    Play Games
  • 概述:在C#中,++i和i++都是自增運算符,其中++i先增加值再返回,而i++先返回值再增加。應用場景根據需求選擇,首碼適合先增後用,尾碼適合先用後增。詳細示例提供清晰的代碼演示這兩者的操作時機和實際應用。 在C#中,++i 和 i++ 都是自增運算符,但它們在操作上有細微的差異,主要體現在操作的 ...
  • 上次發佈了:Taurus.MVC 性能壓力測試(ap 壓測 和 linux 下wrk 壓測):.NET Core 版本,今天計劃準備壓測一下 .NET 版本,來測試並記錄一下 Taurus.MVC 框架在 .NET 版本的性能,以便後續持續優化改進。 為了方便對比,本文章的電腦環境和測試思路,儘量和... ...
  • .NET WebAPI作為一種構建RESTful服務的強大工具,為開發者提供了便捷的方式來定義、處理HTTP請求並返迴響應。在設計API介面時,正確地接收和解析客戶端發送的數據至關重要。.NET WebAPI提供了一系列特性,如[FromRoute]、[FromQuery]和[FromBody],用 ...
  • 原因:我之所以想做這個項目,是因為在之前查找關於C#/WPF相關資料時,我發現講解圖像濾鏡的資源非常稀缺。此外,我註意到許多現有的開源庫主要基於CPU進行圖像渲染。這種方式在處理大量圖像時,會導致CPU的渲染負擔過重。因此,我將在下文中介紹如何通過GPU渲染來有效實現圖像的各種濾鏡效果。 生成的效果 ...
  • 引言 上一章我們介紹了在xUnit單元測試中用xUnit.DependencyInject來使用依賴註入,上一章我們的Sample.Repository倉儲層有一個批量註入的介面沒有做單元測試,今天用這個示例來演示一下如何用Bogus創建模擬數據 ,和 EFCore 的種子數據生成 Bogus 的優 ...
  • 一、前言 在自己的項目中,涉及到實時心率曲線的繪製,項目上的曲線繪製,一般很難找到能直接用的第三方庫,而且有些還是定製化的功能,所以還是自己繪製比較方便。很多人一聽到自己畫就害怕,感覺很難,今天就分享一個完整的實時心率數據繪製心率曲線圖的例子;之前的博客也分享給DrawingVisual繪製曲線的方 ...
  • 如果你在自定義的 Main 方法中直接使用 App 類並啟動應用程式,但發現 App.xaml 中定義的資源沒有被正確載入,那麼問題可能在於如何正確配置 App.xaml 與你的 App 類的交互。 確保 App.xaml 文件中的 x:Class 屬性正確指向你的 App 類。這樣,當你創建 Ap ...
  • 一:背景 1. 講故事 上個月有個朋友在微信上找到我,說他們的軟體在客戶那邊隔幾天就要崩潰一次,一直都沒有找到原因,讓我幫忙看下怎麼回事,確實工控類的軟體環境複雜難搞,朋友手上有一個崩潰的dump,剛好丟給我來分析一下。 二:WinDbg分析 1. 程式為什麼會崩潰 windbg 有一個厲害之處在於 ...
  • 前言 .NET生態中有許多依賴註入容器。在大多數情況下,微軟提供的內置容器在易用性和性能方面都非常優秀。外加ASP.NET Core預設使用內置容器,使用很方便。 但是筆者在使用中一直有一個頭疼的問題:服務工廠無法提供請求的服務類型相關的信息。這在一般情況下並沒有影響,但是內置容器支持註冊開放泛型服 ...
  • 一、前言 在項目開發過程中,DataGrid是經常使用到的一個數據展示控制項,而通常表格的最後一列是作為操作列存在,比如會有編輯、刪除等功能按鈕。但WPF的原始DataGrid中,預設只支持固定左側列,這跟大家習慣性操作列放最後不符,今天就來介紹一種簡單的方式實現固定右側列。(這裡的實現方式參考的大佬 ...