プログラミング言語のビット演算はなぜ NOT, AND, OR, XOR か

大半のプログラミング言語のプリミティブなビット演算は NOT, AND, OR, XOR である。

もしあなたが世界で初めて言語を作ったとして、 NOT, AND, OR はともかく XOR をプリミティブとして用意するかはちょっと迷うかもしれない。逆に暗号などの分野の人は、体 F₂ をなす AND, XOR こそが基本演算だというかもしれない。もちろん NAND 一つだけの過激派もいるだろうし、分野によっては他の頻出二項演算がありそうな気もする。

そんな中で、汎用のプログラミング言語が NOT, AND, OR, XOR をプリミティブとして選ぶ必然性はあるだろうか。「それなりにあるかも」というのがこの文章の趣旨である。

注: この文章では「自明な演算」を「恒等演算および全ての引数を使わない演算」の意味で使う。 f(x, y) = ¬x などを含むことに注意。

ビット演算を選ぶ

いったん全てを忘れ、どうやって演算を選ぶか考えてみる (証明などは後述)。

まず単項演算を考える。自明でない演算は NOT しかないので、これを追加する。
次に二項演算を考える。二項演算はすべて追加するには多すぎる。そこで「入出力のいずれか 1 つに NOT を追加することで、任意の自明でない二項演算を行える演算の集合」を考えてみる。この条件を満たす集合の最小要素数は 3 である (補題 0)。
この最小要素数を実現する集合は複数ある。性質のよい集合を選ぶため、演算に結合性を要請してみる。条件を満たす集合は {AND, OR, XOR}, {AND, OR, XNOR} の 2 個である。

補題と証明

補題 0: 二項ビット演算の集合 F = {f: {0, 1}² → {0, 1}} を考える。 f(x, y) ≡ g(y, x) のとき、 f と g を同一視する。

F' ≔ {f(⋅, ⋅), f(¬⋅, ⋅), f(⋅, ¬⋅), ¬f(⋅, ⋅) | f ∈ F} .

F' が全ての自明でない二項ビット演算を含むとき、最小の |F| は 3 である。

証明: 二項演算の真理値表において、 f(¬⋅, ⋅), f(⋅, ¬⋅) は行や列の入れかえ対応し、 ¬f(⋅, ⋅) は値の反転に対応する。

各演算 (の真理値表) を頂点とし、 NOT を 1 個追加することで移り変わる演算同士を辺で結んだグラフを作る。自明な演算の除外と対称関係にある演算の同一視を行うと、下図のようになる。

  OR              NAND
⎛0 1⎞ __ ⎛1 0⎞ __ ⎛1 1⎞
⎝1 1⎠    ⎝1 1⎠    ⎝1 0⎠
  |        |        |
  |        |        |
⎛1 0⎞ __ ⎛0 1⎞ __ ⎛0 0⎞
⎝0 0⎠    ⎝0 0⎠    ⎝0 1⎠
 NOR               AND

    ⎛0 1⎞ __ ⎛1 0⎞
    ⎝1 0⎠    ⎝0 1⎠
     XOR     XNOR

F に属する頂点から 1-hop 以内で全ての頂点に辿りつければ、 F' が任意の演算を含むことになる。図より、最小の |F| は 3 である。

補題 1: 結合則を満たす二項ビット演算は、自明なものを除いて AND, OR, XOR, XNOR の 4 個である。

証明: 力技。

def is_associative(table):
    for i in range(2):
        for j in range(2):
            for k in range(2):
                if table[table[i][j]][k] != table[i][table[j][k]]:
                    return False
    return True

def enumerate_associative():
    for i in range(2):
        for j in range(2):
            for k in range(2):
                for l in range(2):
                    table = [[i, j], [k, l]]
                    if is_associative(table):
                        yield table

余談

今みてきたような、ある集合とその上で結合則を満たす二項演算の組を半群という。このような対象を分類する試みは数学の一大分野になっている。筆者はその分野について全く無知なのだが (知っていたらこんなしょぼい記事を晒す気にはならない)、なんでも有限群は 50 年の歳月とトータル 15000 ページを超える論文の集合によって、 2004 年に分類が完成したそうである。すごい。