C++で学ぶ符号なし整数のリストアリング除算アルゴリズム

本記事では、除算アルゴリズムを用いて符号なし整数の割り算を行う方法について解説します。除算アルゴリズムには、紙の上で手計算として行われるものと、デジタル回路に実装されるものがあります。除算アルゴリズムは大きく「低速除算アルゴリズム」と「高速除算アルゴリズム」の2種類に分類され、低速除算アルゴリズムにはリストアリング法、非実行リストアリング法、SRT法、非リストアリング法などが含まれます。

このチュートリアルでは、0 < 除数 < 被除数 を前提として、リストアリング（Restoring）除算アルゴリズムについて詳しく見ていきます。

解法のアプローチ

ここでは、商を格納するレジスタQ、余りを格納するレジスタA、除数を格納するMを使用します。Aの初期値は0とし、各ステップでAの値を元に戻す（復元する）ことから、この手法は「リストアリング除算」と呼ばれています。

• レジスタを次のように初期化します。

  • Q = 被除数
  • A = 0
  • M = 除数
  • N = 被除数のビット数

• AQの左シフト：レジスタAとQを1つの連結した単位として扱い、左に1ビットシフトします。

• AからMを減算し、結果をAに格納します。

• Aの最上位ビット（MSB）を確認します。

  • MSBが0の場合：Qの最下位ビットを1に設定します。
  • MSBが1の場合：Qの最下位ビットを0に設定します。

• Aの値を復元し、カウンタNを1減らします。

• N = 0になればループを終了します。そうでなければステップ2に戻ります。

• 最終的に、商はレジスタQに格納されます。

フローチャート

実装例

上記アプローチのC++コード

#include <iostream>
using namespace std;
int main(){
    // 被除数 = 8、除数 = 3 として各変数を初期化
    int Q = 8, q = 1, M = 3;
    short N = 4;
    int A = Q;
    M <<= N;
    // ビット演算による除算のループ
    for(int i = N - 1; i >= 0; i--) {
        A = (A << 1) - M;
        // AのMSBを確認
        if(A < 0) {
            q &= ~(1 << i);  // i番目のビットを0に設定
            A = A + M;      // Aの値を復元
        } else {
            q |= 1 << i;    // i番目のビットを1に設定
        }
    }
    cout << "Quotient: " << q;
    return 0;
}

出力

Quotient: 2

このコードでは、被除数8を除数3で割り、商として2が出力されます。各反復処理では、AとQを連結して左シフトし、AからMを減算した結果の符号によって商の該当ビットを決定します。Aが負になった場合にMを加え直してAを復元する点が、このアルゴリズム最大の特徴です。

まとめ

このチュートリアルでは、符号なし整数に対するリストアリング除算アルゴリズムについて解説しました。フローチャートとビット演算を活用したシンプルなアプローチで問題を解く方法を説明し、実際のC++プログラムも紹介しました。同じロジックはC、Java、Pythonなど他のプログラミング言語でも同様に実装できます。本チュートリアルが皆さんの学習の一助となれば幸いです。