GAWK 2進数を考える

素直に2で割る2進数変換

AWKは2進数を直接扱うことができません。比較的新しい言語では "0b" 等の接頭語を併記して、直接数値として扱えるようにしてあるようですが、AWKには組み込みの変換関数も用意されていませんし、sprintf 等による書式変更もできません。なので、自力で文字列として2進数に変換し、抽象的にそれを利用することになります。しかしながら、ビットシフト等の関数は用意されているのだから不思議です。
以下に素直な関数(それなりに使える)を書いてみます。

   1 : function dec2bin_0(dec,    bin) {
   2 :     do {
   3 :         bin = (dec % 2) bin;
   4 :         dec = int(dec / 2);
   5 :     } while (dec)
   6 :     return bin;
   7 : }


2行：do-while であるのは、0==Dec+0 (数値) をはじかないようにするため
3行：2 で割る「前提」の余り( 0 か 1 )を逆順で追記 ※まだ割っていない 例）2^0

 　 　下1桁から計算される　括弧必須 文字列結合
4行：実際に 2 で割り dec は 1/2 になる

 　 　余り(小数部)は切り捨て (実際には奇数の時 intにより 0.5 が捨てられる)
5行：dec が 0 になるまで繰り返す

下記の算出方法が元になっています。右側を見ると、2進数と2のべき乗との関係性が理解できます。

    2 )  229 ...1  →  2^0 =   1
    2 )  114 ...0  →  2^1
    2 )   57 ...1  →  2^2 =   4
    2 )   28 ...0  →  2^3
    2 )   14 ...0  →  2^4
    2 )    7 ...1  →  2^5 =  32
    2 )    3 ...1  →  2^6 =  64
    2 )    1 ...1  →  2^7 = 128
           0                229

    binary   1 1 1 0 0 1 0 1

直接機械語から2進数を読み取れないので、一足飛びに解を得ることはできません。上記の算出法でみると、2進数の桁(ビット数)分のループが必要になります。大きな数になると、少し心配になりますが、
dec=4,294,967,295 (42億)の場合でも、ループは 32回なので、それほど大したものでもありません。

2進数は 1 と 0 の羅列となり、桁が揃っていないと、とにかく読みにくいので指定桁数で揃え、4bitごとに空白を入れるオプションを上記関数に付け加えます。ちなみによく使う単位「bit」(ビット)は「binary digit」の略です。

   1 : function dec2bin_1(dec, digit,    bin, pad0, i, tmp, ret) {
   2 :     do {
   3 :         bin = (dec % 2) bin;
   4 :         dec = int(dec / 2);
   5 :     } while (dec) 
   6 :     if (!digit) return bin;
   7 :     
   8 :     pad0 = length(bin) % 4;
   9 :     pad0 = (pad0) ? 4 - pad0 : 0;
  10 :     if (pad0) bin = substr("0000", 1, pad0) bin;
  11 :     i = (digit - length(bin)) / 4;
  12 :     while (i-- > 0) bin = "0000" bin;
  13 :     ret = substr(bin, 1, 4);
  14 :     i = 4;
  15 :     while (tmp = substr(bin, ++i, 4)) {
  16 :         ret = ret " " tmp;
  17 :         i += 3;
  18 :     }
  19 :     return ret;
  20 : }


06行：指定桁 digit が記述されていなければ、そのまま2進数を戻す
08行～10行：先頭bitが4bitに満たない時に"0"で埋める
11行～12行：全体で digit bitに満たない場合、”0000”を先頭に挿入
13行：先頭 4bit をバッファに格納
14行：インデックス初期化
15行～：2進数の終わりまで区切りながら4bitづつ格納

2進数の桁数を最初に求めていないので、かなり強引に書式を整えています。

アクション部は下記の通りです。$0を2進数に変換、16bitに揃えて、4bitごとに区切って表示します。

dec2bin.awk

   1 : {
   2 :     print dec2bin_1($0, 16) " : " $0;
   3 : }

入力テキスト (d2b.txt)

実行結果

コマンドプロンプト/Shift_JIS

ビットシフトと論理積を利用して変換してみる

唐突ですが、AWK で10進数のビット数を求める式は、下記になります。

bit = int(log(dec) / log(2) + 1);

log(dec) / log(2) は、log2のdec、つまり「dec は 2 の何乗なのか」を計算しています。
例えば 1024 は 2^10 です。log(1024) / log(2) = 10
2進数で書くと、2^10 の bit にフラグが立ちますが、右から10番目ではなく、11番目になります。

0000 0100 0000 0000...11桁... log(dec) / log(2) + 1 (最下位 2^0 の bit があるため)

次に桁が上がる 2048 は 2^11 です。log(2048) / log(2) = 11
0000 1000 0000 0000...12桁... log(dec) / log(2) + 1


当然ながら、この間にある整数値 1024 <= dec < 2048 は必ず 11桁(bit)となります。

2 の何乗なのかを実際に計算しますと以下の通りです。

log(1025) / log(2) = 10.0014...

log(1100) / log(2) = 10.1032...

log(1500) / log(2) = 10.5507...

log(1800) / log(2) = 10.8137...

log(1900) / log(2) = 10.8917...

log(2047) / log(2) = 10.9992...



小数点以下を切り上げれば、みんな11桁になるのですが、そのような関数はAWKにはありません。
そこで、
bit = int(log(dec) / log(2) + 1);
　「1 足して切り下げる!」

すさまじく良くできた式です。上述の整数乗の時と矛盾しません。考えた人すごいです。

ただし、dec=0 の時は注意が必要です。log(0) は計算不可(-∞)です。GAWKでは -inf が返ります。dec=0 のとき、桁数は 1 となりますので、if 文で回避しましょう。(負の整数や浮動小数はそもそも適用除外としている)






   1 : function dec2bin_2(dec, digit,    mask, ret, ct) {
   2 :     if (!digit) {
   3 :         if (0 == dec + 0) digit = 1;
   4 :         else digit = int(log(dec) / log(2) + 1);
   5 :         mask = lshift(1, (digit - 1));
   6 :         for (; mask > 0; mask = rshift(mask, 1)) {
   7 :             ret = ret (and(mask, dec) ? "1" : "0");
   8 :         }
   9 :         return ret;
  10 :     }
  11 :     mask = lshift(1, (digit - 1));
  12 :     ret = (and(mask, dec) ? "1" : "0");
  13 :     mask = rshift(mask, 1);
  14 :     for (; mask > 0; mask = rshift(mask, 1)) {
  15 :         if (!(++ct % 4)) ret = ret " " (and(mask, dec) ? "1" : "0");
  16 :         else ret = ret (and(mask, dec) ? "1" : "0"); 
  17 :     }
  18 :     return ret;
  19 : }



05行：例えば digit=8 の時
 　 　lshift により mask = 1 0 0 0 0 0 0 0 (binary)に初期化


06行：rshift で mask のフラグ(1)を1つずつ右へ移動(forの初期化部は05行:長いので出した)
 　 　1 0 0 0 0 0 0 0 (初回)
 　 　0 1 0 0 0 0 0 0 (2回目)
 　 　0 0 1 0 0 0 0 0 (3回目)
 　 　0 0 0 1 0 0 0 0 (4回目)
 　 　・
 　 　・
 　 　・
 　 　0 0 0 0 0 0 0 1 (8回目)
 　 　0 0 0 0 0 0 0 0 (9回目は実行されない)


07行：mask と dec で論理積(and)をとると mask のフラグ部分のみ 1 か 0 かが判明する
 　 　例229
 　 　1 1 1 0 0 1 0 1  dec=229
 　 　1 0 0 0 0 0 0 0  mask 初回
 　 　and() = 1 0 0 0 0 0 0 0  真であるので "1" を retに格納
 　 　・
 　 　・
 　 　・
 　 　1 1 1 0 0 1 0 1  dec=229
 　 　0 0 0 1 0 0 0 0  mask 4回目
 　 　and() = 0 0 0 0 0 0 0 0  偽であるので "0" を retに格納







求め方は高度?になりましたが、bit数だけループし、ループ内工数は2で割っていくものより増えてしまっています。rshift()、and()と3項演算と文字列結合。digit を超える入力があると、下位ビットを切り捨ててしまいます。

なんだか、面倒くさくなっただけのような気もします。かっこよく見えるのですが...




別解 ビットシフト(The GNU AWK User's Guide:9.1.6 Bit-Manipulation Functions )
上記は上位ビットから調べていきましたが、こちらは下位から行きます。こちらの方は、あらかじめビット数を知る必要がなく、マスクも 1 で良いので、一見効率が良いように見えますが、実測値は上記2つの関数より遅いです。while句をコメントアウトして、整形前の測定で比較したのですが...後述の処理速度測定で平均536msでした。先頭のゼロ埋めは独特で面白いです。
# bits2str --- turn an integer into readable ones and zeros

function bits2str(bits,        data, mask)
{
    if (bits == 0)
        return "0"

    mask = 1
    for (; bits != 0; bits = rshift(bits, 1))
        data = (and(bits, mask) ? "1" : "0") data

    while ((length(data) % 8) != 0)
        data = "0" data

    return data
}






辞書と16進数を利用した2進数変換
筆者の大好きな辞書です。概要を説明しますと、まず、4bitパターン16個すべてをを辞書に登録します。キーは16進数(文字0～f ※小文字)で、4bitパターンと意味的にリンクしています。次に変換関数側で、10進数を16進表記に変えます(sprintf "%x", dec)。 この16進数を1文字ずつ4bit辞書で置換します。
BEGIN 部での初期化と sprintf 1回分の手間はかかりますが、ループ回数は 1/4 に減ります。置換時のキー検索はほぼ 1：1 (ハッシュテーブルの特徴)となるので、ロスはありません。ボトルネックは substr() ですが、ループ回数が激減しているのでトレードオフというか、お釣りが来ます。
筆者はこの方法がもっとも AWK らしいと思うのですが、いかがでしょう。

   1 : BEGIN {
   2 :     _bit4_init();
   3 : }
   4 : 
   5 : {
   6 :     print dec2bin_3($0);
   7 : }
   8 : 
   9 : function _bit4_init(    s_id, s_b4, a, b, i) {
  10 :     s_id = "0,1,2,3,4,5,6,7,8,9,a,b,c,d,e,f";
  11 :     s_b4 = "0000,0001,0010,0011,0100,0101,0110,0111,1000,\
  12 : 1001,1010,1011,1100,1101,1110,1111";
  13 :     split(s_id, a, ",");
  14 :     split(s_b4, b, ",");
  15 :     for (i in a) _b4[a[i]] = b[i];
  16 : }
  17 : function dec2bin_3(dec, digit,    hex, i, ch, ret) {
  18 :     if (!digit) {
  19 :         hex = sprintf("%x", dec);
  20 :         ch = substr(hex, 1, 1);
  21 :         ret = _b4[ch];
  22 :         if (dec) sub(/^0+/, "", ret);
  23 :         else return "0";
  24 :         i = 1;
  25 :         while (ch = substr(hex, ++i, 1))
  26 :             ret = ret _b4[ch];
  27 :         return ret;
  28 :     }
  29 :     digit = int(digit / 4);
  30 :     hex = sprintf("%0*x", digit, dec);
  31 :     ch = substr(hex, 1, 1);
  32 :     ret = _b4[ch];
  33 :     i = 1;
  34 :     while (ch = substr(hex, ++i, 1))
  35 :         ret = ret " " _b4[ch];
  36 :     return ret;
  37 : }




ランダム数値データ(最大17bit)　65535個を2進数に変換する処理時間(ミリ秒)

	
		
		1回目
		2回目
		3回目
		4回目
		5回目
		平均
	
	
		dec2bin_1 整形なし
		500
		499
		484
		499
		499
		496
	
	
		dec2bin_2 整形なし
		453
		437
		437
		421
		437
		437
	
	
		dec2bin_3 整形なし
		421
		421
		421
		421
		421
		421
	
	
		dec2bin_1 整形あり
		906
		890
		890
		890
		890
		893
	
	
		dec2bin_2 整形あり
		765
		750
		750
		765
		741
		754
	
	
		dec2bin_3 整形あり
		406
		421
		422
		437
		406
		418
	



思ったほど差が出ませんでした。整形ありの3番は期待が大きかったのですが、2倍程度とは。32bitの数値だともっと顕著に速度差が現れるかと思い、実験したところ、2.25倍となりました。微妙です。
ビットシフトの2番が2で割る1番よりちょっと速いことがわかっただけでも良しとします。

	1回目	2回目	3回目	4回目	5回目	平均
dec2bin_1 整形なし	500	499	484	499	499	496
dec2bin_2 整形なし	453	437	437	421	437	437
dec2bin_3 整形なし	421	421	421	421	421	421
dec2bin_1 整形あり	906	890	890	890	890	893
dec2bin_2 整形あり	765	750	750	765	741	754
dec2bin_3 整形あり	406	421	422	437	406	418

GAWK 2進数を考える

素直に2で割る2進数変換

dec2bin.awk

入力テキスト (d2b.txt)

実行結果

ビットシフトと論理積を利用して変換してみる

別解 ビットシフト(The GNU AWK User's Guide:9.1.6 Bit-Manipulation Functions )

辞書と16進数を利用した2進数変換

別解ビットシフト(The GNU AWK User's Guide:9.1.6 Bit-Manipulation Functions )