13

問題：

2 つの n 要素配列 A および B に格納されている 2 つの n ビット 2 進整数を加算する問題を考えてみましょう。2 つの整数の合計は、(n + 1) 要素配列 C に 2 進形式で格納する必要があります。問題を述べてください。正式に、2 つの整数を追加するための擬似コードを記述します。

解決：

  1. C ← [1 ... n + 1] ▹ C はゼロで埋められます。
  2. for i ← 1 ～ n
  3. do sum ← A[i] + B[i] + C[i]
  4. C[i] ← 合計 % 2
  5. C[i + 1] ← sum / 2 ▹ 整数除算。
  6. 出力C

質問：

  1. C[i] は A[i]+B[i] だと思っていましたが、ステップ 3 で sum ← A[i] + B[i] + C[i] を追加するのはなぜですか?
  2. なぜ % 2 を合計するのか (なぜステップ 4 でモジュロを使用する必要があるのですか?)
  3. なぜ sum / 2 (ステップ 5 で除算を使用する必要があるのですか?)

上記の解決策を実際の例で説明していただけますか? ありがとう。

4

3 に答える 3

20

C はソリューションとキャリーの両方です。実際の例として、11 + 3 を足してみましょう。かっこ内は 10 進数で 2 進数で書きます)

A = 1011 (11) + B = 0011 (3) [C starts as 00000 (0)]
       ^               ^                      ^

^ は最初の位置を示し、左から右に読むので左に進みますが、数学は右から左に進みます。また、整数を除算するので、1.5 ではなく 3/2 = 1 です。次に手順です。

1. sum = 1+1+0 = 10 (2), c[1] = 2 % 2 = 0, c[2] = 2/2 = 1
2. sum = 1+1+1 = 11 (3), c[2] = 3 % 2 = 1, c[3] = 3/2 = 1
3. sum = 0+0+1 = 01 (1), c[3] = 1 % 2 = 1, c[4] = 1/2 = 0
4. sum = 1+0+0 = 01 (1), c[4] = 1 % 2 = 1, c[5] = 1/2 = 0
^        ^ ^ ^                               ^
i        A B C, all at position i            note that we store the carry for the NEXT step

結果: C = 01110 (14)

于 2011-04-10T05:56:46.930 に答える
5
  1. 前の反復で追加したときのキャリー ビットが含まれている可能性があるC[i]ため、同様に追加します。たとえば、最初の繰り返しですが、これは 2 進数なので、1 を上に置き、残り ( ) を に入れる必要があります。これにより、C[i]A[i-1] + B[i-1] + C[i-1]1 + 1sum = 1 + 1 + 0 = 2C[1]2 % 2 = 0C[0]10
  2. C[i]の合計は 1 より大きい可能性があるため、sum % 2 を取得A[i] + B[i] + C[i]しますが、その桁に収まる最大値は 1 です。合計の残り (ある場合) は、キャリー ビットに入れられます。そして、それは私たちに...
  3. C[i+1]キャリー量であるsum / 2ため、割り当てられます。forsum / 2を実行すると、次の反復で使用されます。A[i] + B[i] + C[i]i = i + 1
于 2011-04-10T05:57:39.807 に答える
5

10 進数を足すのと同じように 2 進数を足すと考えることができます。各桁で実行する「足し算」ステップと「桁上げ」ステップがあります。

それでは、少しずつ計算してみましょう。追加しているとしましょう:

101
+
011

最初のステップとして、右端から始めます。(あなたの例では、これは i=1 に対応します)。(1+1)%2 を追加すると、0 になります。ここで実際に何が起こっているのでしょうか? 1+1 は 2 で、2 進数では 2 桁の数字 (「10」) です。下位の桁（「0」）しか書けないので、合計を「mod 2」と表現することは、「今は繰り越しの合計について心配する必要はありません」と言っているだけです。だから私たちは持っています：

101
+
011
---
  0 (1 を運ぶ)

ここで、整数除算 ("sum / 2") を実行し、それを一時的に格納することによって "carry a 1" を実装します。

101
+
011
---
 10

これで、2 桁目を追加する準備が整いました: (0+1)%2 -- しかし、追跡してきたキャリーオーバー 1 を追加する必要があるため、(0+1+1)%2 を取得します。降伏:

101
+
011
---
 00

ここでもキャリー ビットを追跡する必要があり、(0+1+1)=1 が得られます。

101
+
011
---
100

最後に、3 番目のビット (1+0+1)%2 を追加して、答えを出します。

101
 +
 011
 ---
1000
于 2011-04-10T05:59:39.660 に答える