長除法

2025年10月18日

長除法

英語表記: Long Division

概要

長除法（ちょうじょほう）は、大きな数を小さな数で割る際に、商と剰余（あまり）を段階的に求めていく基本的な算術アルゴリズムです。ITの分野、特に基数変換（二進数, 十六進数）の文脈においては、10進数をN進数（2や16）に手計算で変換するための最も確実な手計算アルゴリズムとして機能します。これは、変換後のN進数の各桁の値を、連続的な除算とその都度発生する剰余を利用して決定していく手法なのですね。

詳細解説

基数変換における長除法の役割

長除法は、単なる算数の計算手法にとどまらず、基数変換（10進数から他のN進数への変換）を実現するための核心的なツールです。私たちがこのアルゴリズムを変換ツールと実装のカテゴリで学ぶ理由は、コンピュータが内部でどのように数値を扱っているかを理解する上で、この手計算の原理が基礎となるからです。

基数変換において長除法を使う目的は明確です。それは、元の10進数を変換したい基数（$N$）で繰り返し割ることで、その数の$N$進数表記における各桁の値（0から$N-1$の範囲の数字）を順番に取り出すことです。

動作原理：なぜ剰余が重要なのか

N進数（例えば2進数）表記とは、「2のべき乗の塊がいくつあるか」を示す表現です。10進数 $D$ を $N$ 進数に変換する場合、まず $D$ を $N$ で割ります。

$$D = Q_1 \times N + R_0$$

ここで、$R_0$ は最初の剰余であり、これは $D$ を $N$ の塊に分けたときの「最も小さな塊（1の位）」、すなわち $N$ 進数における最下位桁の値に他なりません。これは非常に重要なポイントです！

次に、得られた商 $Q_1$ を再び $N$ で割ります。

$$Q_1 = Q_2 \times N + R_1$$

この $R_1$ は、変換後の数の2番目の桁（$N^1$ の位）の値になります。このプロセスを商が 0 になるまで繰り返します。

$$Q_k = 0 \times N + R_k$$

最後に得られた剰余 $R_k$ が最上位桁となり、すべての剰余を「最後に得られたものから順に」（逆順に）並べることで、変換後の $N$ 進数が完成します。この一連の反復的な除算と剰余の利用こそが、長除法が基数変換における手計算アルゴリズムとして確立されている理由なのです。

手計算アルゴリズムとしての位置づけ

この手法は、現代のコンピュータが高速に基数変換を行う際の基礎的なロジックそのものです。私たちは通常、計算機を使って変換しますが、資格試験においては、この手計算のステップを理解しているかどうかが問われます。つまり、長除法は、コンピュータの「変換ツール」がどのように「実装」されているかを、人間の手で追体験するための必須の「アルゴリズム」なのですね。この仕組みを理解しておくと、計算ミスが減り、なぜその結果になるのかを深く納得できるはずですよ。

具体例・活用シーン

基数変換における長除法の具体的な活用シーンとして、10進数 45 を 2進数に変換する例を見てみましょう。

10進数 45 を 2進数へ変換する例

目標：45 (10) を ? (2) に変換します。基数 $N=2$ を使って繰り返し割ります。

ステップ1 (最下位桁 $2^0$ の決定):
$45 \div 2 = 22$ あまり 1
（この「1」が2進数の最下位桁です。）
ステップ2 ($2^1$ の決定):
$22 \div 2 = 11$ あまり 0
ステップ3 ($2^2$ の決定):
$11 \div 2 = 5$ あまり 1
ステップ4 ($2^3$ の決定):
$5 \div 2 = 2$ あまり 1
ステップ5 ($2^4$ の決定):
$2 \div 2 = 1$ あまり 0
ステップ6 (最上位桁 $2^5$ の決定):
$1 \div 2 = 0$ あまり 1
（商が 0 になったら終了です。）

得られた剰余を、最後のものから逆順に並べます。
1 (ステップ6), 0 (ステップ5), 1 (ステップ4), 1 (ステップ3), 0 (ステップ2), 1 (ステップ1)
よって、45 (10) = 101101 (2) となります。

初心者向けの類推：両替のプロセスメタファー

長除法を理解するための良いメタファーは、「大量の硬貨を、特定の額面の紙幣や硬貨に両替していくプロセス」です。

あなたが持っているのが大量の1円玉（元の10進数）だと想像してください。これを2進数に変換したい場合、目標は「2円玉」「4円玉」「8円玉」…というように、2のべき乗の額面のコインに両替することです。

まず、手持ちの1円玉をすべて集め、可能な限り2円玉（基数 $N$）に両替します。
両替しきれずに手に残った1円玉（剰余 $R_0$）が、2進数の1の位の値（0か1）になります。
次に、手に入れた2円玉をすべて集め、可能な限り4円玉（次の桁の位）に両替します。
両替しきれずに手に残った2円玉（剰余 $R_1$）が、2進数の2の位の値になります。

この作業を、最大の額面のコイン（商が0になるまで）まで繰り返すことで、元の1円玉の総額を、2進数という新しい通貨体系で表現できるのです。この「仕分けと残りの確認」の作業こそが、長除法の本質であり、手計算アルゴリズムの面白さだと感じませんか？

資格試験向けチェックポイント

長除法は、ITパスポートから応用情報技術者試験まで、数値表現の基本として必ず出題されるテーマです。特に、基数変換（二進数, 十六進数）の分野で確実に得点するために、以下のポイントをチェックしておきましょう。

逆順の重要性（ITパスポート・基本情報）: 長除法で得られた剰余は、必ず「最後に得られたものから順に」並べる、というルールを絶対に忘れないでください。試験では、この並び順を逆にして誤答を誘うパターンが非常に多いです。
16進数への適用（基本情報）: 10進数から16進数への変換でも、長除法は有効です。この場合、基数 $N=16$ で割ります。剰余が 10～15 になった場合は、それぞれ A～F に変換するステップを忘れないように注意が必要です。この手計算の正確さが問われます。
小数点の変換との区別（基本情報・応用情報）: 長除法は主に整数部の変換に使われます。小数部の変換（例えば 0.625を2進数へ）には、長除法ではなく「繰り返し乗算（掛け算）」を使うため、両者を混同しないように区別して覚える必要があります。
アルゴリズム理解（応用情報）: 応用情報技術者試験では、長除法そのものの計算を問うよりも、この原理を利用したプログラムのコード（擬似言語）を読み解かせたり、計算量の概念と結びつけたりする問題が出る可能性があります。手計算のプロセスが、そのままループ処理として実装されていることを理解しておくと有利です。