アルゴリズム入門(基数変換)

私達人間は0〜9の10個の数字を使った10進数を使うことが一般的です。
それに対し、コンピュータは2進数で動いています。
2進数は0と1の2つの数字だけを使った表現する方法です。
つまり、0,1,10,11,100,101,110,111,1000,・・・のように桁が増えていきます。
そこで、10進数から2進数に変換する方法を考えてみましょう。

下記の方法がよく使われています。
18 ÷ 2 = 9 あまり 0
9 ÷ 2 = 4 あまり 1
4 ÷ 2 = 2 あまり 0
2 ÷ 2 = 1 あまり 0
1 ÷ 2 = 0 あまり 1

ここで、あまりを下から順に並べると10010となり、欲しい値が求められました。
これをプログラムで実装することが出来ます。

#!/usr/bin/awk -f

BEGIN{
    ARGC == 2 ? n = ARGV[1] : n = 10;
    result = "";
    while (n > 0){
        result = (n % 2) result;
        n = int(n / 2);
    }
    print result;
}

もう少し汎用的にするために、基数を指定して変換出来る関数を作ってみましょう。

#!/usr/bin/awk -f

BEGIN{
    if(ARGC == 3){
        n = ARGV[1];base = ARGV[2];
    }else{
        print "shinsu_change3.awk n base";
    }
    result = "";
    while (n > 0){
        result = (n % base) result;
        n = int(n / base);
    }
    print result;
}

さて、次は2進数から10進数に変換するプログラムです。
たとえば10010という2進数は
1 ×2 ^ 4 + 0 × 2 ^ 3 + 0 × 2 ^ 2 + 1 × 2 ^ 2 + 1 × 2 ^ 0であると考えられます。
実際に計算してみると 1 × 16 + 0 × 8 + 0 × 4 + 1 × 2 + 0 × 1 = 18というように求められます。
これをプログラムでも実装してみます。

#!/usr/bin/awk -f

BEGIN{
    if(ARGC == 2){
        n = ARGV[1];
    }else{
        print "awk -f convert.awk num";
        exit;
    }
    split(n,num,"");
    for(i = 1; i <= length(num); i++){
        ans += num[i] * (2 ^ (length(num) - i))
    }
    print ans;

}

実際に実行してみます。

awk -f convert.awk 10010
18

これで基数変換もバッチリですね。