awk と bit 演算

プログラミング言語で、「.. かつ」、「.. あるいは」、「.. でなくて」といった論理条件を扱う演算子として、 awk 言語の設計者が選択したのは、

&& - 論理 AND (かつ)
|| - 論理 OR (あるいは)
! - 論理 NOT (でなくて)

だけですが、これで全ての論理条件の組み合わせを実現することができます。 (注１)

これは、現代のコンピュータ技術の基盤となる、 2 進演算の知識を前提とすべきではないという判断だったのではないかと思いますが、 2 進演算が論理学の基盤でもあって、複数の論理演算の同時処理に向いていることを理解している人には、複雑な論理条件の切り分けを能率的に行うために、ビット演算(bitwise operation)の AND, OR, exclusive-OR, complement がほしくなるとこが多いと思います。

その結果、awk に自前の bit 演算を組み込みたくなったり、 awk そのものに、bit 演算を組み込みたくなったり(注２)しますが、これは、2 進演算を基盤にする本来の CPU 命令を使う場合、つまり、アセンブラや C で書く場合と比べれば、極めてまわりくどい処理になって、プログラムの実行を引き受ける CPU が知ったら、さぞかしあきれると思います。

それでも、awk の論理演算子 (&&, ||) だけを使うのにくらべれば、コーディングは遥かに簡単で、すっきりしますから、組み込み関数としての bitwise opeator を用意するのは悪くありません。

この実現方法にも、いろいろありますが、数値演算だけでやる方法と、文字列処理を併用する方法の 2 つを作ってみました。

もっと、すっきりした方法、あるいは、コンパクトな方法もありそうですが、私自身は思い付いた方法のうち、この 2 つを残しました。もっと面白い方法を見付けた方は、ぜひ公開してください。

bitwise 演算関数

1. 文字列利用

awk '
BEGIN  {
  print and(15, 7)
  print or(15,7)
  print and(32767, 7)
  print and(32767, 32760)
  print xor(15, 7)

  exit 0
}
# bitwise AND
function and(x, y,  i, k, s, t) {
  s = bin(x)
  t = bin(y)
  k = 0
  for (i = 1; i <= 16; i++) {
	if ((substr(s, i, 1) * substr(t, i, 1)) > 0)
		k += 2 ^ (16 - i)
  }
  return k
}
# bitwise OR
function or(x, y,  i, k, s, t) {
  s = bin(x)
  t = bin(y)
  k = 0
  for (i = 1; i <= 16; i++) {
	if ((substr(s, i, 1) + substr(t, i, 1)) > 0)
		k += 2 ^ (16 - i)
  }
  return k
}
# bitwise exclusive OR
function xor(x, y,  i, k, s, t) {
  s = bin(x)
  t = bin(y)
  k = 0
  for (i = 1; i <= 16; i++) {
	if ((substr(s, i, 1) + substr(t, i, 1)) == 1)
		k += 2 ^ (16 - i)
  }
  return k
}
# bitwise complement
function complement(x,  i, k, q) {
  k = 0
  for (i = 15; >= 0; i--) {
	q = int(x / 2^i)
	if (!q)
		k += 2^i
	x %= 2^i
  }
  return k
}
# decimal to binary string
function bin(x,  i, k, q, s) {
  s = ""
  for (i = 15; i >= 0; i--) {
	q = int(x / 2^i)
	s = s ((q > 0) ? "1" : "0")
	x %= 2^i
  }
  return s
}
'

2. 数値演算のみ

# bitwise AND
function and(x, y,  b, i, k, qx, qy) {
  k = 0
  for (i = 15; i >= 0; i--) {
	b = 2^i
	qx = int(x / b)
	qy = int(y / b)
	if (qx * qy)
		k += b
	x %= b
	y %= b
  }
  return k
}
# bitwise OR
function or(x, y,  b, i, k, qx, qy) {
  k = 0
  for (i = 15; i >= 0; i--) {
	b = 2^i
	qx = int(x / b)
	qy = int(y / b)
	if (qx + qy)
		k += b
	x %= b
	y %= b
  }
  return k
}
# bitwise exclusive OR
function xor(x, y,  b, i, k, qx, qy) {
  k = 0
  for (i = 15; i >= 0; i--) {
	b = 2^i
	qx = int(x / b)
	qy = int(y / b)
	if (qx + qy && (!qx || !qy))
		k += b
	x %= b
	y %= b
  }
  return k
}
# bitwise complement
function complement(x,  b, i, k, q) {
  k = 0
  for (i = 15; i >= 0; i--) {
	b = 2^i
	q = int(x / b)
	if (!q)
		k += b
	x %= b
  }
  return k
}
# decimal to binary string
function bin(x,  i, k, q, s) {
  s = ""
  for (i = 15; i >= 0; i--) {
	q = int(x / 2^i)
	s = s ((q > 0) ? "1" : "0")
	x %= 2^i
  }
  return s
}

注

注１ - 最低限必要な論理素子

最低限必要な論理素子としては、 NAND (!(A&B)) 一つであることが知られています。

注２ - gawk の隠し機能

なお、gawk では「undocumented feature」(隠し機能)として、「bitwise ops」(ビット演算)が用意してあって、 Makefile の CFLAGS か config.h で BITOPS を定義(define)すると、 and(), compl(), lshift(), or(), rshift(), strtonum(), xor() といったビット演算関数が使えるようになっていますが、公開すべきかどうか迷った末に、非公開にしたようで、ソースコードを見ないとわかりません。

なお、gawk の隠し機能には、NDECDATA というのもあって、こちらは「0123」といった先行「0」の数値を 8 進数として解釈させる機能ですが、「0001239」が「9」になるといった、いい加減な実装になっています。