4

2 つの符号なし数値 'a' と 'b' を追加する必要があります。

ビット操作を使用して、次のコードを見つけました

unsigned int add (unsigned int a,unsigned int b)
{
    unsigned int carry, sum;
    if (b == 0)
    {
        return a;
    }

    sum = a ^ b; // xor takes sum
    carry = a & b; // collect carry;
    carry = carry << 1;
    return ( add (sum, carry) );
}

このコードが 2 つの数値を加算する方法がわかりません。

ヘルプ/指示の人々。

4

5 に答える 5

3

問題のビット操作コードは、半加算器と加算が交換可能であるという2 つの基本原則を使用しています。

単一の半加算器は、キャリーインなしで 2 ビットを加算します。単一ビット加算の結果は、入力の 1 つが 1 の場合は 1 になり、入力が等しい場合は 0 になります。これは、コード内のビット単位で表されxorます。

それをしても、キャリーに対処する必要があります。ビット位置からのキャリーアウトは、両方のビットが 1 の場合は 1、それ以外の場合は 0 です。これは、ビットごとの と、追加する必要があるビット位置にキャリーを移動andする次の組み合わせで表されます。shift

add の再帰呼び出しは、加算が可換であるという事実を利用してキャリーを適用します。キャリーが最初の追加とともにビットごとに追加されるか、後のステップでまとめて追加されるかは問題ではありません。

キャリーを追加すると、新しいキャリーアウトが発生する場合があります。これは、add にキャリーがなくなるまで再帰呼び出しを続けることで処理されます。

キャリーインがゼロの状態でゼロを追加すると、キャリーが発生しないため、再帰の基本ケースであるゼロキャリーに到達する必要があります。1 回のキャリー加算でキャリーの最下位kビットがすべて 0 の場合k+1、次のキャリーの少なくとも最下位ビットは 0 でなければなりません。

于 2013-09-10T14:01:56.833 に答える
0

これは、ハードウェアが加算を実装する方法です。ビットの加算の結果は、ビットの排他的論理和 ( ^C++ の演算子) です。これはあなたが得るものですsum。ただし、これは下位ビットからのキャリーを考慮していません。キャリーアウトは、ビット (&演算子) の and であり、 の初期値が得られますcarry。しかし、ビット n のキャリーアウトはビット n + 1 のキャリーインなので、左にシフトし、ビット n をビット n + 1 に移動して追加します。

キャリーインを追加する前の結果 (ビットレベル) が 1 で、キャリーインが 1 の場合、キャリーアウトも発生するため、再帰を使用して追加します。

再帰が終了する理由はもう少し微妙です (もちろん、ハードウェア バージョンでは再帰は行われず、ロジックが追加されます)。これは、元の値を考慮することで最も簡単に評価できます。

a   b   carry_in  sum carry_out

0   0       0      0      0
1   0       0      1      0
0   1       0      1      0
1   1       0      0      1
0   0       1      0      0
1   0       1      1      1
0   1       1      1      1
1   1       1      0      1

(「合計」列はa ^ b、キャリーを除いた の結果です。)

最初の再帰呼び出しでは、b のビット 0 は 0 になります (これは下位ビットの Carry_in を表し、1 がないため、または<<ビット n の Carry_out をビット n の Carry_in に移動する のため) + 1)。そしてもちろん、ビット 0 の Carry_in は 0 になります。そのため、最初の再帰呼び出しのビット 0 では、最初の 2 行だけが発生する可能性があります。つまり、carry_out は発生せず、次の再帰では、最初の 2 行だけがビット 0 と 1 に関連します。つまり、各再帰は、伝達されたキャリーから 1 つのセット ビットを効果的に削除します。キャリーは最終的に 0 になる必要があります。また、パラメータ b として伝播されるため、パラメータ b は最終的に 0 になる必要があります。

于 2013-09-10T14:23:57.830 に答える