FC2ブログ
ヽ|∵|ゝ(Fantom) の 開発blog? ホーム » Java »【Java】n進数変換(基数変換)・桁の分割をする

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


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




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

●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() になる。内容的には文字列から数値への変換となる。

 1つだけ気をつけないといけないのは、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+各桁の数×基数0 (1~k 桁のとき)

となっていることがわかる。つまりは、10進数というのは「桁ごとの数字に基数[=10]を掛けたもので構成され、それらを加算したもの」でできている。桁を表すには最下位を「100(= 1)」とし、桁が上がるごとに、「×101(= 10)」「×102(= 100)」「×103(= 1000)」・・・としていけば良い。それらに各桁の数を掛けて合計すれば、1つの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 を避けるのも1つの手かも知れない。


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





(関連記事)
【Java】グレイコード変換をする
【Java】平衡三進数変換をする


関連記事
スポンサーサイト



category: Java

thread: プログラミング

janre: コンピュータ

tag: 算術関数  アルゴリズム 
tb: 0   cm: --


トラックバック

トラックバックURL
→http://fantom1x.blog130.fc2.com/tb.php/216-1182ba30
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

Social

検索フォーム

全記事一覧

カテゴリ

ユーザータグ

最新記事

リンク

PR