ビット演算のまとまった勉強

準備: 数を記号列にする

本稿では 32bit の符号付き整数 をビット演算の対象とする。つまり操作対象は 長さ32の記号列で表現できる:

数を記号列に.txt

数    記号列
----------------------------------------
0     00000000000000000000000000000000
5     00000000000000000000000000000101
-5    11111111111111111111111111111011

以降よく使うので、この記号列を生成する関数を作っておく:

repr.js

const repr = (n, sep = '') => {
  const bits = [...Array(32).keys()].map(i => n & (1 << i) ? '1' : '0').reverse();
  return bits.reduce((a, x, i) => a + x + ((i % 4 === 3) ? sep : ''), '');
};

使い方:

repr(-5);      // -> '11111111111111111111111111111011'
repr(-5, ' '); // -> '1111 1111 1111 1111 1111 1111 1111 1011'

準備: JavaScript とビット演算

整数は 54bit扱えるけど ビット演算子をつけると、自動的に 符号付き32bit に変換される。

0xffffffff             // 4294967295
0xffffffff >> 0        // -1
0xffffffff ^ 0         // -1
0xffffffff + 1         // 4294967296. ビット演算でないのでオーバーフローしない
(0xffffffff + 1) >> 0  // 0
0xffffffff << 4        // -256, 0xfffffff0 に等しい

符号なし32bit は原則扱えないと思った方がよいが、以下の注意を十分理解すれば不可能というわけではない。>>>でシフト: 右シフト >> は他言語と同様、負数の場合に 1 で fillする。>>> ならどんな場合でも 0 でfillしてくれる。算術には最大の注意: 1 << 31以上の数が負数として扱われるので各種算術、===, +, - などを扱う場合は十分注意が必要。

Lesson: 符号反転

n に NOT をした ~n は全てのビットを反転させたものになる:

5    00000000000000000000000000000101
~5   11111111111111111111111111111010

なので n + ~n は全ビットが立つ。なので n + ~n + 1 はオーバーフローして 0 になる。「足すとオーバフローして 0 になるやつ」が補数なので n の補数は ~n + 1 となる。この議論は負数でも成り立つので 正数から負数を作る操作というより 符号を反転させる操作 とみなした方が適用範囲が広がる:

minus.js

const minus = n => ~n + 1;

minus(5);          // -> -5
minus(minus(5));   // -> 5
minus(-5);         // -> 5
minus(-4);         // -> 4
minus(minus(-4));  // -> -4

なお、符号反転は 1項演算子 - として言語に内蔵されているので、上記 minus を使う場面はない。

Lessonを終えるにあたって注意を一つ。上記の議論では「足し算」について 十分詳しいことを前提にしている。実際 minus の定義の中で 2項演算子 + が使われているが、これは符号反転に先立って理解すべき事項であるように思われる。そこで 次は足し算について勉強したい。

Lesson: 足し算/add

2項演算子 + をビット演算に帰着させたい。つまり a + b と add(a, b) が一致するように ビット演算 だけで作られた add を実装しよう。

とっかかりは、以下のような ひっ算:

Q. ひっ算で計算するのは簡単だが、どうビット演算に落とし込む？

91     0000 0000 0000 0000 0000 0000 0101 1011
97     0000 0000 0000 0000 0000 0000 0110 0001
------------------------------------------------ (add)
91+97  0000 0000 0000 0000 0000 0000 1011 1100

アプローチの一つは 繰り上がりなしの加算 と 繰り上がり のひっ算に変形すること:

91^97は半加算(繰り上がり無視の足し算), (91&97)<<1 は繰り上がりの配置とみなせる

91^97       0000 0000 0000 0000 0000 0000 0011 1010
(91&97)<<1  0000 0000 0000 0000 0000 0000 1000 0010
-----------------------------------------------------(add)
 91+97      0000 0000 0000 0000 0000 0000 1011 1100

これは、ひっ算を別のひっ算に変形しただけ ではあるが意味がある。なぜならこれは必ず終了する再帰になるから。具体的には以下を示したことになる:

add(a, b) = add(a ^ b, (a & b) << 1)

第二引数は再帰を繰り返すといつか0になる(後述)ので、それを終了条件にすると(a + 0 = a)、再帰呼び出しは必ず止まるので実装完了となる:

const add = (a, b) => b ? add(a ^ b, (a & b) << 1) : a;

add(3, 4);   // -> 7
add(7, 4);   // -> 11

（第二引数がいつか0になる理由）: a&b<<1 の最下位ビットはシフトのせいで必ず0になる。これが再帰の第二引数になるので。再帰が 1深くなるごとに 0が保証されているしきいが（下位ビットから数えて）増えていく。再帰の深さは最大でも 32回になる。

以上、2項演算子 + をビット演算に帰着できることを示した。もっと効率のよい（≒命令数が少なくて済む）方法もあるはず。逆に愚直にループを使って 最下位ビットから手でのひっ算をするように実装することもできたはず。

Lessonを終えるにあたり注意点を一つ。上記の議論はa, b のどちらか（もしくは両方）が負数であっても成立する。これに関しては次のLessonで検討する。

Lesson: 足し算再考

言語同梱の 2項演算子 + や 先ほど実装した add では、負数であってもきちんと動作する。しかし これは自明ではない。しっかり確かめて 補数に関する理解を底上げする必要がある。

別の言い方をすると、「足してオーバーフローして0になるやつを補数と呼ぶ」という補数の概念が「ひっ算として手続き化された足し算」と整合的であることを確かめよう。

例えば 41 - 7 = 34 であるが、確かにひっ算の手続きで答えを求めることができる:

41  00000000000000000000000000101001
-7  11111111111111111111111111111001
--------------------------------------------- (add)
34  00000000000000000000000000100010

例えば 7 - 41 = -34 であるが、確かにひっ算の手続きで答えを求めることができる:

7    00000000000000000000000000000111
-41  11111111111111111111111111010111
--------------------------------------------- (add)
-34  11111111111111111111111111011110

例えば -7 - 41 = -48 であるが、確かにひっ算の手続きで答えを求めることができる:

-7   11111111111111111111111111111001
-41  11111111111111111111111111010111
--------------------------------------------- (add)
-48  11111111111111111111111111010000

これまで見たように、負数を含むひっ算は オーバーフローを起こしたり起こさなかったりが上手くかみ合うことによって正しい結果を導く。この機微を数式で考察しよう。

2の補数表現とは以下のような写像 f とみなせる。

f(N) = N           (N が非負の場合)
     = 2^32 + N    (N が負の場合)

まず f が符号化方式として妥当であることを確かめよう。容易に確かめられるように、f によって 区間 [-2^31, 2^31 - 1] は 区間 [0, 2^32 - 1] に1対1に写る。したがって 符号化方式として妥当。

続いて、ひっ算add(a, b)の手続きが f の下でどう解釈されるか 符号で場合分けして考察しよう。つまり f(a+b)と add(f(a),f(b))が一致するかを確認しよう。

片方が負, 足すと非負になる場合(例 41-7): f(a) + f(b) = 2^32+a+b となる。仮定より a+b>=0 が成立するので この値は 2^32 より大きい。よって、オーバーフローする。よって(2^32が無視されることで) a+b が符号になる。OK。

片方が負, 足すと負になる場合(例 -41+7): f(a) + f(b) = 2^32+a+b となる。仮定より a+b<0 が成立するので この値は 2^32 より小さい（ついでに言うと0より大きい）。よってオーバーフローせず 2^32+a+b がそのまま符号になるが、これは（負数である） a+b の表現として妥当。

両方負の時(例 -41-7): ひっ算結果は f(a) + f(b) = 2^32+2^32+a+b となる。この値は区間 [2^32, 2^33] に収まる。よって 2^32 が一つ分 オーバーフローする。つまり 2^32+a+b が符号になるが、これは（負数である） a+b の表現として妥当。

以上、「足してオーバーフローして0になるやつを補数と呼ぶ」という補数の概念が「ひっ算として手続き化された足し算」と整合的であることを確かめた。

Lesson: 絶対値/abs

絶対値を求める関数は以下の実装が有名:

const abs = n => (n ^ (n >> 31)) - (n >> 31);

abs は「引数が正の場合何もせず、 負の場合は符号反転する」操作とみなせるので場合分けして上記実装の妥当性を確認する。

nが非負の場合: n が非負の場合 n >> 31 は最上位ビットを取得することに等しいので 0 になる。したがって n ^ 0 - 0 と変形され 結局 n になるので「何もしない」操作となる。よって abs の動作として妥当だ。

nが負の場合: 負数の場合 n >> 31 は -1 になる(負数の右シフトでは 1で埋めながらシフトされるので結局 32のビットが全部立つことになる)。よって式は n ^ (-1) - (-1) すなわち n ^ (-1) + 1になる。これは「全ビット反転させて 1を足す」という操作と読めるのだが、この操作こそ「符号反転」という操作そのものだ(一つ目のLesson参照)。ということで abs の動作として妥当だ。

上記の議論では、負数のシフトと正数のシフトの違いを理解している必要があった:

右シフトでは 正数は 0で埋められ 負数は 1で埋められる

5       00000000000000000000000000000101
5>>1    00000000000000000000000000000010
5>>2    00000000000000000000000000000001
-5      11111111111111111111111111111011
-5>>1   11111111111111111111111111111101
-5>>2   11111111111111111111111111111110