Cでの大きな数値の減算

Question

約20分前に入門Cコースで試験を終えました。試験の最初の質問は私に多少のガードをかけてくれました。その違いを見つけるには2つの大きな数字が必要でした。

目標は2つの構造（N1とN2）を値で取り、その差を参照渡しの構造体（N3）に格納することでした。私たちはN3が全ての '0'で始まったと仮定することが許されました。 MAXのサイズは何でもかまいません。したがって、数値が100桁を超える場合、ソリューションはまだ動作していなければなりません。

ここでベースコード（オリジナルは、これはメモリからのものである、わずかに異なっていてもよい）

#include <stdio.h> 
#include <stdlib.h> 
/* MAX can be any length, 10, 50, 100, etc */ 
#define MAX 10 

struct bignum 
{ 
    char digit[MAX]; 
    char decimaldigit[MAX/2]; 
}; 
typedef struct bignum bigNum; 
void difference(bigNum, bigNum, bigNum *); 

/* 
    Original values in N1 and N2 

    N1.digit = { '0', '0', '0', '5', '4', '8', '2', '0', '9', '0'}; 
    N1.decimaldigit { '0', '0', '0', '4', '9' }; 

    N2.digit = { '0', '0', '0', '4', '8', '1', '3', '1', '4', '5'}; 
    N2.decimaldigit { '8', '0', '1', '2', '0' }; 
*/ 

/* 
    Result would be: 
    N3.digit = { '0', '0', '0', '0', '6', '6', '8', '9', '4', '4'} 
    N3.decimaldigit { '1', '9', '9', '2', '9' } 
*/ 

問題が、この問題に対する解決策を見つけることにはあまりないが、わずか20〜約行があったことです完全な答えのために用意されています。私の解決方法は、整数に変換した後に数字を1つずつ減算した後、結果が負の場合に適切なキャリーを行うことでした。これは提供されたものよりも大幅に多くのスペースを必要とした。

この問題のために用意された少量のマークとスペースに基づいて、私は見ていない非常に些細な解決策があると信じています。それは何ですか？私は今コースを終えましたが、この質問はまだ私を悩ませています！

完全な解決策は必要ありません。機能の内部動作だけです。difference。

ビット単位の演算子を使用する必要はありません。

Answer 1

これはN1 >= N2の場合に有効です。これは、配列がdn...d2d1d0.e0e1...emのように配置されていることも前提としています。

char digchr(int); // Converts a single-digit integer into a character. 

void difference(bigNum N1, bigNum N2, bigNum *N3) { 
    int carry = 0; 

    for (int i = MAX/2 - 1; i >= 0; i--) { 
     int diff = N1.decimalDigits[i] - N2.decimalDigits[i] - carry; 
     if (diff < 0) { 
      diff += 10; 
      carry = 1; 
     } else { 
      carry = 0; 
     } 

     N3->decimalDigits[i] = digchr(diff); 
    } 

    for (int i = 0; i < MAX; i++) { 
     int diff = N1.digits[i] - N2.digits[i] - carry; 
     if (diff < 0) { 
      diff += 10; 
      carry = 1; 
     } else { 
      carry = 0; 
     } 

     N3->digits[i] = digchr(diff); 
    } 
} 

Answer 2

ほとんどのコンピュータサイエンスのBigNumberの問題は、記述したとおり正確に計算を行う必要があるように設計されています。各文字を整数に変換し、必要に応じて借用します。

あなたの計画攻撃は、あなたがそれを記述したのと同じように、わずか数行に過ぎません。 （。プラスすぎ桁に同じロジックを適用するために少し余分な手間）：擬似コード、このようなものでは

for each character (right to left): 
    difference = N1.digit[i] - N2.digit[i]; 
    if (difference < 0) 
     N1.digit[i - 1]--; 
     difference += 10; 
    N3.digit[i] = difference; 

それはあなたが正しい考えを持っていたように聞こえる、そしておそらくちょうどオーバー実装を考えた？

Answer 3

教授に、減算は加算の観点から定義する必要があります。私は単項演算子に過負荷をかけて、 " - "演算子をオーバーロードし、他の場所でビギナル追加ルーチンを定義しました。私は9's complementを使用して、テーブルベースのアンサー検索（なぜなら、それらのうち10個だけがある場合は合計を計算するのはなぜですか？）で、追加を高速化/高速化する必要があります。

void bigDifference(bigNum N1, bigNum N2, bigNum *N3) { 
    bigSum(N1, -N2, N3); 
}