2 つの 2 進数は、通常の「通常の冗長な」表現で表すことができます (つまり、別の数字、たとえば 2 を導入して、2 つの連続する 2 の間にゼロがあるような一意でない表現を取得します)。自由。複雑さは O(k) であると聞いたことがあります。ここで、k は 2 つの数値のうち短い方の長さです。しかし、アルゴリズム自体は何ですか？どこにもウェブ上に表示されていないようです。結果が規則性を維持するように、一定時間でそのような表現に1を追加できることを私は知っています。しかし、これを一般化する方法がわかりません。
質問する
782 次
1 に答える
0
これは古い投稿であり、ポスターには最近の活動はあまりありませんが、とにかく答えを出すと思いました.
この回路を従来の式として表すために、いくつかの表記法を示しましょう。RBR 表記の各「ビット」は実際には 2 つのビットで構成されているため、これらの右と左のビットを参照するには、それぞれ [0] と [1] を使用します。特定の「ビット」位置を参照するには、中かっこ {0}、{1}、{2}、...{n} を使用します。
2 つまたは 3 つの単一ビットを加算すると、2 ビットの合計になります (MSB は伝統的にキャリー ビットと呼ばれます)。これらは、[0] および [1] によって参照することもできます。後者はキャリー ビットです。例:これ以上説明(0+1+1)[0]=0, (0+1+1)[1]=1, (0+0+1)[0]=1, (0+0+1)[1]=0
する必要はありませんが、数値を加算する一般的なアルゴリズム z = x + y は次のようになります。z{n}[0] = ((x{n-1}[1] + x{n-1}[0] + y{n-1}[1])[0] + (y{n-1}[0]) + (x{n-2}[1] + x{n-2}[0] + y{n-2}[1])[1])[1]
z{n}[1] = ((x{n}[1] + x{n}[0] + y{n}[1])[0] + (y{n}[0]) + (x{n-1}[1] + x{n-1}[0] + y{n-1}[1])[1])[0]
ここでいくつかのキャリーが行われていることに注意してください。ただし、キャリーは 2 つのオーダーに制限されているため、アルゴリズムは O(n) を達成します。前述のリンクの回路図で定義されている z{0} と z{1} の特別な考慮事項にも注意してください。
于 2012-06-07T16:48:58.277 に答える