どうも, ビット演算が好きなたぬきです。
本記事は以下の要素を含みます。 苦手な方はブラウザの戻るボタンを, それ以外の方はそのままお待ち下さい(ニコニコ動画風)。
- ポエム
- ビット演算
- 突然の VB ディス
デファクトスタンダードとなったビット演算
世の中のプログラミング言語の潮流がどんどんと抽象化していき, メモリ上の表現など気にしなくてもアプリケーションが作れるようになってさえ, ほぼすべての言語にビット演算子が搭載されています。
型として整数型が存在しない JavaScript だって, 多倍長整数がデフォルトになった Python3 だって, ビット演算子を持ちます。
ビット演算子を導入している言語では, ビットシフト以外におおむね以下の 4 種が搭載されているはずです。
- ビット NOT
- ビット AND
- ビット OR
- ビット XOR
あ, VB ではなぜか以下のビット演算子もあります。 なんで???
- ビット EQ
- ビット IMP
論理演算子と併用しているからなのでしょうがそもそも論理演算としてもあんま使わないよこれ!!
忘れられたビット演算子
こんなもの用意するよりもまず先に実装すべきだったにも関わらず, 誰からも忘れ去られたかわいそうなビット演算があるのです。
その名は, ビット NIMP。
「……誰?」という声が聞こえてきそうなので, 以下に真理値表とベン図を挙げます。
| a | b | a NIMP b |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
この演算子を用意しなかったのがどれほどの損失だったのかを, 以下の 2 点で説明いたします。
損失 1: フラグ管理の可読性が悪い
今ほどにメモリ資源が潤沢ではなかった時代, 複数の状態をひとつの変数で扱うために, ビットによるフラグ管理というものが生まれました。 なにせたったふたつの状態しか取らない真理値型の変数でさえ最低でも 1 バイトもの領域を要求せざるを得ないのですから, どうせならビットごとに使えば 8 状態も管理できるじゃん(じゃん)となったのは自然な成り行きでしょう。
しかも, ビット演算はこういったフラグ管理にとてもとても便利だったのです。
たとえば, if 文の条件式などとして, フラグが立ち上がっているかどうかを調べたいとします。 そういうとき, そのフラグとの AND をとってやれば, もしフラグが立っていなければ結果は必ず 0 になります。 立っていれば, 0 以外になります。 C のような言語では 0 以外は Truthy なので, 条件式としてこれをそのまま使うことができます。
フラグの状態を切り替えるにはそのビットと XOR をとればすみました。
現在の状態に関わらずとにかくオンにするには OR をすればよい。
そしてその逆にとにかくオフにするには NOT して AND をするだけですんだのでした。
……あれ?
なんか最後だけめちゃめちゃややこしくなかった?
はい, ためしにコードで書いてみるとこういうことになります。
/* フラグが立っているか確かめる */
if (x & someBit) {
/* ... */
}
/* フラグを切り替える */
x = x ^ someBit;
/* フラグをオンにする */
x = x | someBit;
/* フラグをオフにする */
x = x & ~someBit; /* ← Oh... */
うん, どう考えても最後だけややこしい。
「オンにする」と「オフにする」は対応しているべきなのに, オフだけ相当する演算子が実装されていないわけです。
先程あげた真理値表ならびにベン図を見ていただければ分かる通り, ビット NIMP 演算子, たとえば\が実装されていたとしたら,
x = x \ someBit;
と, シンプルに書けたはずなのです。
損失 2: 集合演算とのねじれ
まあでも実際のところ, 今どきにビットによるフラグ管理なんてしてる人はそうそういないでしょう。
むしろ現代は猫も杓子もオブジェクト指向, メモリもじゃばじゃば使って構造体で情報管理しようやという時代です。
オブジェクト指向 3 本の柱のひとつにポリモーフィズムがありますが, 最近の言語は演算子のオーバーロードなんかができたりして便利ですよね。
ところで, ビット列というのは, 0 と 1, つまり「ない」と「ある」を示していると考えることができます。
あるなしといえば集合です。最近の言語には基本コレクション型として Set が使えたり, そうでなくても外部ライブラリとして Set 構造が使えたりします。
そこで欲しくなるのが集合演算です。 先程も言ったとおり, ビット列と集合にはある種の類似性があり, ここに抽象化の光が見えます。
そこで演算子のオーバーロードを用いてビット演算子を集合の演算子として利用できるようにしている言語は多いです。 今をときめく Python だってその一人です。
以下にビット演算と集合演算の対応表を示します。 ベン図を書いてみるとちょうどうまく対応しているのがわかるかと思います。
| ビット演算 | 集合演算 |
|---|---|
| a AND b | 交叉 $S \cap T$ |
| a OR b | 和 $S \cup T$ |
| a XOR b | 対称差 $S \bigtriangleup T$ |
さて, ここで欲しくなるのは集合の差 $S \setminus T$ です。 もう何度も何度もビット NIMP の話をしていますから察しはついていると思いますが, 差に対応しているのはビット NIMP です。
では, 集合の差を求めるために, 先に示したように NOT して AND してみましょうか。
s = {0, 1, 2}
t = {1}
print(s & ~t)
Traceback (most recent call last):
File "Main.py", line 6, in <module>
print(s & ~t)
TypeError: bad operand type for unary ~: 'set'
ぎゃーっ, 実行時エラーです。 集合には NOT 演算ができません。
それもそのはずです。 なぜなら集合における NOT, すなわち補 $\complement S$ は「すべての元を含む」集合, ベン図における外側を覆う大きな四角である普遍集合 $U$ がなければ定義することはできないからです。
普遍集合はそれを想定することは簡単ですが, プログラミングにおける Set という構造においては「入りうるすべての値が入った Set」なんて表現できません。 だから NOT はサポートされていないのです。
しかし, 差自体は宇宙が定義できるかどうかに関わらず求められます。 実際には, Python では-演算子で差を求められるようになっています。
s = {0, 1, 2}
t = {1}
print(s - t)
{0, 2}
しかし, 当然-を整数型に対して使用するとビット NIMP ではなく引き算になってしまいます。 整数型に対して使用するか, Set に対して使用するかでセマンティクスが変わってしまうのです。
なので, 抽象的には同様の演算にも関わらず, ビット列の場合にはa & ~bと書き, Set に対してはs - tと書くという「ねじれ」が生まれてしまいます1。
なんという悲劇!! ああ, もしもビット NIMP 演算子\があれば衝突しないですんだのに!!
まとめ
人類がビット NIMP の演算子を用意しなかったのは大きな損失である。
この上はもはや革命しかない。
-
一応, 双方で利用できる等価な演算として
x & (x ^ y)があります。 たぶん誰も使おうとは思わないでしょうけど。 ↩