【Java】n進数変換（基数変換）・桁の分割をする

2016/06/11 Sat [edit]

　今回のテーマは「10進数 ←→ n進数」の相互変換（基数変換）のアルゴリズムなのだが、標準ライブラリにもあるので、確認用のためにも、まずはおさらいしてみよう。もちろん不要なら「基数変換のアルゴリズム」まで読み飛ばしても良い。

■標準ライブラリでの基数変換
■コード上での n進数表記
■基数変換のアルゴリズム
■10進数 → n進数変換（桁の分解）
■n進数 → 10進数変換

■標準ライブラリでの基数変換

●10進数→n進数変換（標準ライブラリ）

int n;
n = 46;
String bin = Integer.toString(n, 2);    //10進数→2進数
//String bin = Integer.toBinaryString(n); //10進数→2進数(※同じ)
System.out.println(n + " -> " + bin + " (2)");

n = 51;
String tri = Integer.toString(n, 3);    //10進数→3進数
System.out.println(n + " -> " + tri + " (3)");

n = 16;
String oct = Integer.toString(n, 8);    //10進数→8進数
//String oct = Integer.toOctalString(n);  //10進数→8進数(※同じ)
System.out.println(n + " -> " + oct + " (8)");

n = 30;
String hex = Integer.toString(n, 16);   //10進数→16進数
//String hex = Integer.toHexString(n);    //10進数→16進数(※同じ)
System.out.println(n + " -> " + hex + " (16)");

46 -> 101110 (2)
51 -> 1220 (3)
16 -> 20 (8)
30 -> 1e (16)

　標準ライブラリでは、例のように、

　Integer.toString(10進数, 基数)

で良い。long を変換したい場合は、Long.toString() になる。内容的には数値から文字列への変換となる。

　2進数、8進数、16進数に関しては以下の専用の関数もある、

　Integer.toBinaryString(10進数)　10進数→2進数
　Integer.toOctalString(10進数)　10進数→8進数
　Integer.toHexString(10進数)　10進数→16進数

　基数がわかっているなら、専用関数の方が実行速度は速い。

●n進数→10進数変換（標準ライブラリ）

int v;
String bin = "101110";
v = Integer.parseInt(bin, 2);    //2進数→10進数
System.out.println(bin + " (2) -> " + v);

String tri = "1220";
v = Integer.parseInt(tri, 3);    //3進数→10進数
System.out.println(tri + " (3) -> " + v);

String oct = "20";
v = Integer.parseInt(oct, 8);    //8進数→10進数
System.out.println(oct + " (8) -> " + v);

String hex = "1e";
v = Integer.parseInt(hex, 16);   //16進数→10進数
System.out.println(hex + " (16) -> " + v);

101110 (2) -> 46
1220 (3) -> 51
20 (8) -> 16
1e (16) -> 30

　標準ライブラリでは、例のように、

　Integer.parseInt(n進数文字列, 基数)

で良い。long に変換したい場合は、Long.parseLong() になる。内容的には文字列から数値への変換となる。

　１つだけ気をつけないといけないのは、parseInt() では負の値の表現となる文字列のパースはできない（エラーとなる）。その場合は parseUnsignedInt() を使えば負の値でパースできる。
　

String s = "11111111111111111111111111111111";  //2進数は31ビット目(最下位を0とするとき)が1のとき負の値となる
//int v = Integer.parseInt(s, 2);  //エラー(NumberFormatException)
int v = Integer.parseUnsignedInt(s, 2);  //-1

■コード上での n進数表記

　ちなみに、変換ではないのだが、ソースコードに直接書きたい場合は、以下のように表記できる。

●n進数表現

int b = 0b101110;    //2進数表現
System.out.println("b = " + b);    //10進数

int o = 020;     //8進数表現
System.out.println("o = " + o);    //10進数

int h = 0x1e;    //16進数表現
System.out.println("h = " + h);    //10進数

b = 46
o = 16
h = 30

■基本的な基数変換のアルゴリズム

　では、ここからは本題の基数変換のアルゴリズムを考えてみよう。

●各桁の分解

　まずは、10進数の数はどのような構成でできているかを見てみよう。10進数の各桁を分解して考えると、

のように、

　各桁の数×基数^k-1＋・・・＋各桁の数×基数¹＋各桁の数×基数⁰ (1～k 桁のとき)

となっていることがわかる。つまりは、10進数というのは「桁ごとの数字に基数[=10]を掛けたもので構成され、それらを加算したもの」でできている。桁を表すには最下位を「10⁰(= 1)」とし、桁が上がるごとに、「×10¹(= 10)」「×10²(= 100)」「×10³(= 1000)」・・・としていけば良い。それらに各桁の数を掛けて合計すれば、１つの10進数の値となる。

　そしてこれは他の基数（n進数）でも同じで、例えば、2進数や3進数を分解してみると、

のようになる。

　これらのことをそのままコーディングすれば、「10進数 ←→ n進数」の相互変換は簡単にできることがわかる。

　
■10進数 → n進数に変換する（基数で分解する）

　「n進数に変換」とは上記の例を見れば、「値を0になるまで基数で割り続け、余りを並べる」ことと同じである。それをそのまま作ってみよう。

●基数変換したリストを作る（各桁を分解）

import java.util.ArrayList;
import java.util.List;

/**<h1>基数変換したリストを作る（各桁を分解）</h1>
 * <p>各桁の値は、下位から上位に向かって入る。</p>
 * @param value ： 元の数値 (10進数)
 * @param radix ： 変換する基数 (>= 2)
 * @return<b>List<Integer></b> ： 基数で割った余りのリスト
 */
public static final List<Integer> baseRemainder(int value, final int radix) {
    final List<Integer> list = new ArrayList<Integer>();
    int m;
    do {
        m = value % radix;
        value /= radix;
        list.add(m);
    } while (value > 0);

    return list;
}


//メインでは...
int n = 51;
List<Integer> list = baseRemainder(n, 3);
for (int k : list) {
    System.out.print(k + " ");
}

0 2 2 1

　これは「10進数の 51 を、3進数の 1220 に変換した」ことになる。戻値のリストの要素は「下位→上位」へ向かって各桁の値が入っていることに注意しよう。慣れていないと何となく数字の各桁は左から右へ上位→下位と考えてしまいがちだが、配列などは下位→上位へインデクスは増えていくわけで、コンピュータにとってはむしろ自然な順である。任意精度整数(多倍長整数)や n進数、ビット列などを扱うような実装をしてみれば、わりと普通に使うものだったりする。頭のなかで逆向きに読めば良い(笑)。あとはこのリストを文字列にするなり、逆順に表示するなりすれば良いのである。しかし、n進数で計算などするなら、文字列に直さないでこのまま計算する方がもちろん速い。

　そしてまた、基数を変換しないでそのまま使うなら、これは各桁の分解と同じことになる。例えば普通に基数を10進数にすると、

int n = 1234;
List<Integer> list = baseRemainder(n, 10);
for (int k : list) {
    System.out.print(k + " ");
}

4 3 2 1

のように「下位→上位」に向かって、各桁が分解されていることがわかる。もし、どうしても桁を「上位→下位」の順位にしたければ、Collecctions.reverse() を使って反転する手もあるが、baseRemainder() の要素追加部分「list.add(m)」を「list.add(0, m)」のように修正し、常に先頭から挿入していけば良い。ただし、10進数に変換したい場合は桁を逆向きにパースしなくてはいけなくなるため、コードが冗長となり、変換を繰り返す際には実行速度の面でも劣る。「上位→下位」へ修正したものは別の関数にして使い分けた方が利口だろう。

　
■n進数 → 10進数に変換する

　今度は「n進数を10進数に変換」してみよう。これは上記の例を見てもわかるように、これまでの桁の分解とは逆の操作になる。つまりは「各桁の値を基数のべき乗で掛けて、それらを合計する」ことで得られることがわかる。それをやってみよう。

import java.util.ArrayList;
import java.util.List;

/**<h1>各桁のリスト(n進数)を10進数に変換する</h1>
 * <p>要素(各桁の値)は、下位から上位に向かって入っているものを使う。</p>
 * @param list ： 各桁のリスト
 * @param radix ： リストの基数
 * @return<b>int</b> ： 10進数
 */
public static final int digitsToInt(final List<Integer> list, final int radix) {
    int sum = 0;
    int x = 1;
    final int len = list.size();
    for (int i = 0; i < len; i++) {
        sum += list.get(i) * x;
        x *= radix;
    }
    return sum;
}


//メインでは...
int b = 0b101110;    //2進数表現
List<Integer> list = baseRemainder(b, 2);

System.out.print("list = ");
for (int k : list) {
    System.out.print(k + " ");
}
System.out.println();

int v = digitsToInt(list, 2);
System.out.println("v = " + v);

list = 0 1 1 1 0 1
v = 46

　この例では、10進数の 46 （=2進数表現：0b101110）を一旦「baseRemainder()」で 2進数の桁に分解し、それを「digitsToInt()」で 10進数に戻す操作をしている。ただのサンプルなので無駄は大目に見て欲しい(笑)。

　リストの要素取得のループに for を用いているが、少し冗長と感じるようなら、以下のように、foreach(拡張for)に書き換えても良いだろう。

for (int v : list) {
    sum += v * x;
    x *= radix;
}

　実のところを言うと、オブジェクトの foreach は、その度に Iterator が生成されているのだが、このくらいのサンプルだと違いは出ないので、どちらでも構わない。しかし例えば、GC（ガベージコレクタ）が動きまくると困るようなものなら（リアルタイムなアクションゲームとか、延々とループするものとか）、オブジェクトの foreach を避けるのも１つの手かも知れない。

　単純な基数変換なら、標準ライブラリを使った方が確実だろう。ただし、標準ライブラリは基本的に数値←→文字列の変換となるため、変換を繰り返す場合は無駄が多く、実行速度は遅くなる。また、例えば「平衡三進法」や「n進数グレイコード」などを扱うなら、自分で実装した方が応用が効く。文字列に直さないで良いのなら、「baseRemainde()」や「digitsToInt()」を使って数値のままで処理した方がずっと速い。「桁の分解」として利用する分にも非常に幅広く使える。