N進法

2016年04月27日(編集2016年04月27日)
このエントリーをはてなブックマークに追加

符号化や暗号化の処理を実装するとき、プログラムでN進法の実装をできる必要があります。
この記事は、Javaを使ってN進法の説明と実装をおこないます。
コードを通して、N進法の理解と実装方法を理解します。

javaはoracle jdk 1.8.0_77を利用します。

環境

  • Windows8.1
  • oracle jdk version 1.8.0_77
  • Eclipse version Luna Service Release 2 (4.4.2)

内容

初心者向け

N進法

皆さんが普段、生活の中で何気なく使っている数が10進数です。
例えば、なにか物をカウントする時に、1,2,3,...10,11と数えると思います。この数を

10進数

と呼びます。

10進数は、基数を10とした数値の表現方法で、0から9までの10種類の数字を用いて表現します。

一方で、パソコン内部では2進数を使います。数え方は、0,1,10,11のように表現します。これは、0と1でスイッチのON/OFFを処理しているからです。

また、プログラムでは、2進数の他に、8進数、16進数をよく使います。

2進数

この記事では、パソコンの基本となる2進数でN進法の計算方法を理解します。
ただ暗記するだけでなく、考え方をしっかりと理解してください。
N進法の考え方は、どんな数値でも同じなので、8進数、16進数、58進数(Base58)、64進数(Base64)でもプログラム実装できるようになるはずです。

10進数 → 2進数(計算)

10進数を2進数にします。
例として、10進数の8を2進数に変換する計算をします。

10進数から2進数を求める

10進数の値と基数の割り算の余り(剰余)を逆さから書いた数がN進数です。
上記の図の例だと、基数が「2」、剰余が青い矢印の左の値「0,0,0,1」になります。
よって、2進数の値は

1000

です。

10進数 → 2進数(プログラム)

では、上記の計算をプログラムで実装します。

{project_folder}/src/main/java/{package}/Radix.java
public class Radix {
  
  public static final char[] BINARY_CHAR = "01".toCharArray();
  
  /**
   * 10進数を2進数を変換して返します
   * @param decimal 10進数
   * @return binary 2進数
   */
  public static String encode_binary(String decimal) {
    
    int i_decimal = Integer.valueOf(decimal);
    
    StringBuffer res = new StringBuffer();
    while (i_decimal > 0) {
      res.append(i_decimal%2);
      i_decimal = i_decimal/2;
    }
    
    return res.reverse().toString();
  }

}
        

ポイントとなる箇所を説明します。

  • 2進数の計算

10進数(i_decimal)と基数の剰余(i_decimal mod 2)、除算(i_decimal = i_decimal / 2)をwhile文で繰り返します。

while (i_decimal > 0) {
  res.append(i_decimal%2);
  i_decimal = i_decimal/2;
}
        

10進数が8なら、2進数の剰余は

0, 0, 0, 1

です。これらの値を文字列でつなげて、"0001"を生成します。

  • 文字列を逆順にする

つなげた文字列の順を逆にします。

return res.reverse().toString();
        

逆順にすることで"0001"が"1000"になります。

以上がエンコード処理です。

実行

Eclipseで上記のencode_binaryメソッドを実行します。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {    
    System.out.println(Radix.encode_binary("8")); 
  }
}
        

10進数"8"を、2進数にエンコードします。

Eclipse Console
1000
        

2進数"1000"が出力されました。

10進数 → 2進数(Javaライブラリ)

Javaライブラリを利用しても、10進数 → 2進数の変換は可能です。

Integer.toBinaryString(int i))
        

Binaryは英語で2進数を意味します。
to(〜へ) + Binary(2進数) + String(文字列)
つまり、「2進数文字列へ」という意味のメソッド名です。

Eclipseで実行してみましょう。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {    
    System.out.println(Integer.toBinaryString(8));
  }
}
        

10進数"8"を、2進数にエンコードします。

Eclipse Console
1000
        

正常に変換されました。

2進数 → 10進数(計算)

2進数を10進数にします。
例として、2進数の10100を10進数に変換する計算をします。

2進数から10進数を求める

10進数の数は、基数に(桁数 - 1)の乗数を加算していきます。

上記の図の例だと、

1 * 2^4 + 0 * 2^3 + 1 * 2^2+ 0 * 2^1 + 0 * 2^0

16 + 0 + 4 + 0 + 0

20

となります。

2進数 → 10進数(プログラム)

では、上記の計算をプログラム化してみましょう。

{project_folder}/src/main/java/{package}/Radix.java
public class Radix {
  
  public static final char[] BINARY_CHAR = "01".toCharArray();
  
  /**
   * 2進数を10進数に変換して返します
   * @param binary 2進数
   * @return decimal 10進数
   */
  public static String decode_binary(String decimal) {
    
    char [] chars = decimal.toCharArray();
    
    int num = 0;
    for (int i = 0; i < chars.length; i++) {
      char c = chars[i];
      
      int index = 0;
      for (int j = 0; j < BINARY_CHAR.length; j++) {
        if (BINARY_CHAR[j] == c) {
          index = j;
        }
      }
      
      num = num*2;
      num = num + index;
    }
    
    return String.valueOf(num);
  }

}
        

ポイントとなる箇所を説明します。

  • 基数の乗数を加算していく

基数の乗数を加算していくプログラムは以下のようになります。

int num = 0;
for (int i = 0; i < chars.length; i++) {
  char c = chars[i];
  
  int index = 0;
  for (int j = 0; j < BINARY_CHAR.length; j++) {
    if (BINARY_CHAR[j] == c) {
      index = j;
    }
  }
  
  num = num*2;
  num = num + index;
}
        

ループ内でnum*2するのがポイントです。桁数の重みの処理です。

実行

Eclipseで上記のencode_binaryメソッドを実行します。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {    
    System.out.println(Radix.decode_binary("10100"));
  }
}
        

2進数"10100"を、10進数にデコードします。

Eclipse Console
20
        

10進数"20"が出力されました。

2進数 → 10進数(Javaライブラリ)

Javaライブラリを利用しても、2進数 → 10進数の変換は可能です。

Integer.parseInt(String s, int radix)
        

文字列sの基数をradixに指定します。

Eclipseで実行してみましょう。

{project_folder}/src/main/java/{package}/App.java
public class App {

  public static void main(String [] args) {    
    System.out.println(Integer.parseInt("10100", 2));
  }
}
        

2進数"10100"を、10進数にエンコードします。

Eclipse Console
20
        

正常に変換されました。

まとめ

N進数の変換は、文字エンコードやセキュリティの実装をする場合に役立ちます。
この記事の考え方が理解できれば、8進数、16進数だけでなく、Base58やBase64のアルゴリズムも実装できるはずです。

ぜひ試してみてください。

関連記事

タグ検索で調べてみよう

ビットコイン 技能