binary - Binary 符号付き数字の 2 による除算 (冗長な Binary 表現)

Question

Binary Signed digit (冗長バイナリ表現) で 2 による除算を行うにはどうすればよいですか? シフトが効かないよね？

Answer 1

冗長なバイナリ表現は、次の形式の単なる表現です。

\sum_{i=0}^n d_i 2^n

はd_iだけでなく、より大きなセットから抽出され{0,1}ます。

2 で割るか右にシフトすると、

\sum_{i=0}^{n-1} d_{i+1} 2^n + f(d_0)

トリックは、 の冗長な表現を調整する方法にありますd_0。

RBR にフォームの数字があり{0,1,2}、最下位桁が 2 の場合は、1補正するために結果に追加する必要があるためf(0) = 0、 , f(1) = 0,f(2) = 1が機能するはずです。

• 4 = 12_base2、だから12_base2 >> 1====1 + f(2)予想1 + 1通り。2_base22
• 6 = 102_base2、そう102_base2 >> 1= 10_base2 + f(2)= 11_base2=3

d_iを設定することにより、符号付き冗長バイナリ表現 (つまりin を使用{-1,0,1})に対して同様のものを得ることができますf(-1) = -1。

• 1 = 1(-1)_base2、そう1(-1)_base2 >> 1= 1 + f(-1)= 1 - 1=0

したがって、最終的には、シフトするだけの素朴なアプローチが機能します。シフトされた数字の冗長なエンコードを説明するためのファッジファクターが必要です。

選択した RBR にさらにオプションが含まれている場合は、それに応じてファッジ ファクターを調整する必要があります。