6つのレジスタを持つ符号なし整数の除算とモジュロ
Dec 02 2020
最大6つのレジスタ（a、b、c、d、e、f）を使用して2つの符号なし整数N1とN2を除算するログ時間アルゴリズム（仮想マシンの場合）を見つける必要があります（[両方とも> = 0]正または0）ここで、除算器が0の場合、結果は0であり、モジュロ演算です。
- div-> N1 / N2
- mod-> N1％N2
次のようなコマンドで
- リセットa-> a = 0
- ADD ab-> a = a + b
- SUB ab-> a = max（0、ab）
- SHR a-> a = floor（a / 2）
- SHL a-> a = floor（a * 2）
- INC a-> a + = 1
- DEC a-> a = max（0、a-1）
- JUMP j-> j行目にジャンプ
- JZERO xj-> xが0の場合、k + jにジャンプします
- JODD xj-> xがk + jにジャンプするよりも奇数の場合
私を助けることができるアルゴリズムはありますか？
regの値がODDかZEROかしか確認できません。
ご協力ありがとう御座います。
回答
1 PeterCordes Dec 02 2020 at 18:34
飽和-減算し、jzero以下（またはより大きい）の比較を可能にするので、ビットシフトと加算のみを使用して乗算と除算を行うにはどうすればよいですか？に関するnjuffaの回答のCバージョンを実装できます。商と剰余を生成します。非飽和addがあるので、ラッピングaddを実装できます（その後、NathanがCで行うように、ラップアラウンドをチェックして手動で実行検出を実行します）。
joddのように下位ビットをテストできますif (x&1)。これにより、標準の乗算アルゴリズムも実装できます。したがって、商のみを与える除算アルゴリズムがある場合は、remainder = dividend - quotient*divisor対数時間の乗算を使用できます。
その他のバイナリ除算に関するQ＆A：
- ビットシフトと加算のみを使用して乗算と除算を行うにはどうすればよいですか？-同じQ＆Aに関する別の回答。今回は、シフトを使用して除数の最上位ビットを配当に「揃え」てから、教科書の筆算に進みます。しかし、拡張幅の整数がなくても安全かどうかは明らかではありません。
- ビットシフトの加算と減算のみを使用した対数時間整数除算
- ビットシフトを使用して整数除算を置き換えるにはどうすればよいですか？
- ビットシフトを使用して10で除算しますか？すべてのステップで乗算を実行します。これは、高速の乗算がある場合、または数ビットが設定されている既知の定数の場合にのみ有効であるため、シフト/加算は数回しかかかりません。もう1つの利点は、右シフトを必要としないことですが、右シフトはあります。（一部のおもちゃのISAとは異なり）