0

符号なし 32 ビット 2 進整数 (オーバーフローを含む) のペアを追加しています。加算は実際に計算されるのではなく表現的なものであるため、効率的なアルゴリズムは必要ありませんが、各コンポーネントは個々のビットに関して手動で指定されるため、コンパクトな表現のアルゴリズムが必要です。助言がありますか?

編集:ブール演算子に関して。だから私はcarry = a & b; sum = a ^ b;最初のビットのためにそれを考えていますが、他の 31?

ああ、そして引き算!

4

3 に答える 3

0

おそらく、オーバーフロー(=キャリー)を使用して、2つの1ビット数の加算を記述することから始めることができます。

A | B | SUM | CARRY
===================
0   0    0      0
0   1    1      0
1   0    1      0
1   1    0      1

これをさらに一般化するには、前のステージからの入力としてキャリーも受け取る「全加算器」が必要です。次に、32ビット加算を32個のそのような全加算器のチェーンとして表現できます(最初のステージのキャリー入力は0に関連付けられています)。

于 2012-05-22T12:26:43.377 に答える
0
  • これらの数値を表現するためのデータ構造部分について。4つの方法があります

1)Bit Array
ビット配列は、個々のビットをコンパクトに格納する配列データ構造です。
これらは、ビットマップ、ビットセット、またはビットストリングとも呼ばれます。

2)Bit Field
ビット フィールドは、複数の論理値を一連の短いビットとしてコンパクトに格納するためにコンピューター プログラミングで使用される一般的なイディオムであり、各単一ビットを個別にアドレス指定できます。

3)Bit Plane
デジタル離散信号 (画像や音声など) のビット プレーンは、信号を表す 2 進数のそれぞれの特定のビット位置に対応するビットのセットです。

4)Bit Board
ビットボードまたはビット フィールドは、関連するブール変数のグループ全体を同じ整数に詰め込む形式であり、通常はボード ゲーム上の位置を表します。

  • 実装に関しては、各ステップで次のことを確認できます。
    S = a xor b xor c

S は現在のビット a と b の合計の結果
c は入力キャリー

Cout - 出力キャリーは(a & b) xor (c & (a xor b))

于 2012-05-22T13:17:47.423 に答える
0

単純なブール演算子では加算を実行できません。加算器が必要です。(もちろん、加算器は、より複雑なブール演算子を使用して構築できます。) 加算器は、2 ビットとキャリーを加算し、キャリーアウトを次のビットに渡します。

擬似コード:

carry = 0
for i = 31 to 0
  sum = a[i] + b[i] + carry
  result[i] = sum & 1
  carry = sum >> 1
next i

VEDITテキストエディタのマクロ言語を使った実装です。加算される 2 つの数値は、各行に 1 つずつ、ASCII 文字列として指定されます。結果は 3 行目に挿入されます。

Reg_Empty(10)                       // result as ASCII string
#0 = 0                              // carry bit
for (#9=31; #9>=0; #9--) {
    #1 = CC(#9)-'0'                 // a bit from first number
    #2 = CC(#9+34)-'0'              // a bit from second number
    #3 = #0+#1+#2                   // add with carry
    #4 = #3 & 1                     // resulting bit
    #0 = #3 >> 1                    // new carry
    Num_Str(#4, 11, LEFT)           // convert bit to ASCII
    Reg_Set(10, @11, INSERT)        // insert bit to start of string
}
Line(2)
Reg_Ins(10) IN
Return

入力と出力の例:

00010011011111110101000111100001
00110110111010101100101101110111
01001010011010100001110101011000

編集:
これは、加算器がブール演算で実装された疑似コードです:

carry = 0
for i = 31 to 0
  sum[i] = a[i] ^ b[i] ^ carry
  carry = (a[i] & b[i]) | (a[i] & carry) | (b[i] & carry)
next i
于 2012-05-22T13:38:05.260 に答える