唐突にビット演算の話です。今回は本当に基礎的な事しか書きませんので、ある程度のレベルの方には常識レベルの話になることをご承知ください。

近年のプログラミング環境で、ビットを意識する機会はほとんど無くなりました。プログラミングの抽象化が進んだおかげで良いことだと思います。今や知らないのが普通なのかもしれません。しかし、もしちょっと低レイヤーな処理を書く機会があった時に、今までの私達にとっては常識レベルであった知識であっても、重要度が下がり学ぶ機会も無くなってしまったが故に、知らない人はそこで躓いてしまう可能性が高いことに気が付きました。この記事は、普段のプログラミングにはあまり必要のないビット演算を、とりあえずこれだけ知っておけばその先は自力でなんとかなるかな、というレベルまで解説したいと思います。

解説は JavaScript を使って行いますが、基本は他の言語でも同じです。

JavaScript における数値

JavaScript には数値型がありますが、それは浮動小数点数です。今回は細かい話はしませんが、整数だと Number.MAX_SAFE_INTEGER === 9007199254740991 と Number.MIN_SAFE_INTEGER === -9007199254740991 の間の数字は誤差が出ることなく扱えます。

一方で、ECMAScript の仕様により、演算途中で整数を 32bit 整数に変換する命令がいくつかあります。それにより変換されると、32bit の整数の表現範囲を超えると扱えなくなります。例えば、

console.log(12345678901 >> 0); // === -539222987

>> 0 は意味的には右に 0 ビットシフト（＝本来意味のない演算）ですが、JavaScript ではビットシフト命令を呼ぶと内部で 32bit 整数に変換され、結果として 32bit の範囲を超えた数字が扱えなくなります。32bit の数字は、符号付き（singed）だと 2147483647 〜 -2147483648 の値が、符号無し（unsigned）だと 4294967295 〜 0 までの値が利用可能です。なぜこのような値になるのかについては後で説明します。

ここではとりあえず、「今日は 32bit の話をするので 2147483647 〜 -2147483648 くらいの数字を扱うんだな」と思っておいてください。

あと、この記事中で 0b11010011 みたいな表記を使いますが、これは JavaScript の 2 進数リテラルで、2 進数で 11010011 を表記する方法です。また、 x ** y は、x の y 乗を計算する演算子です。念のために記しておきます。

ビットとは

数は、コンピュータの中ではビットの集まりで表現されます。32bit の整数の場合、32 個のビットを使って 1 つの数字を表します。ビットは 0 か 1 を取る単位であり、32bit の整数は 32 個並んだビットを何らかの数字に紐付けているのです。

ビットの表現を無駄なく整数に紐付けるために、2 進数を用いて表現しています。例えば 01101001 という 8bit の数があった場合、

0 * (2 ** 7) +
1 * (2 ** 6) +
1 * (2 ** 5) +
0 * (2 ** 4) +
1 * (2 ** 3) +
0 * (2 ** 2) +
0 * (2 ** 1) +
1 * (2 ** 0) === 0b01101001 // === 105

となります。これは 32 bit になっても 64 bit になっても変わりません。桁ごとの計算がわからないという方は、10 進数に置き換えるとわかりやすいと思います。

1 * (10 ** 7) +
2 * (10 ** 6) +
3 * (10 ** 5) +
4 * (10 ** 4) +
5 * (10 ** 3) +
6 * (10 ** 2) +
7 * (10 ** 1) +
8 * (10 ** 0) === 12345678

もし 32bit を全部使った場合、0b11111111111111111111111111111111 === 4294967295 (=== 2 ** 32 - 1) が最大値となります。しかし、この表現だと一番小さい値はゼロになり、マイナスの整数を表現することが出来ません。こういった表現を一般的に「符号なし整数（unsigned integer）」と呼びます。32bit の符号なし整数の最大値は 4294967295 となります。最小値は 0 です。

余談ですが、ファミコン版のドラクエ 4 の 5 章のカジノで 20G のコインを 838861 枚買うと 4G で買えてしまう裏技は、ドラクエ 4 の内部処理で 24bit の符号なし整数で扱っていたためです。24bit の符号なし整数の最大値は (2 ** 24 - 1) === 16777215 で、これを超えるとオーバーフローした数字が無視される実装であったため、838861 * 20 - 2 ** 24 = 4 ということで 4 ゴールドになってしまうバグでした。

マイナスの表現（2の補数）

ではここから、マイナスの整数を考えてみましょう。先程の 01101001 === 105 という数に対して、8bit 整数で -105 を表現するにはどうするのが良いでしょうか？

-105 を x と置いてみましょう。当然ながら、105 + x = 0 になります。これを 2 進数で考えると、

  01101001
+)xxxxxxxx
----------
  00000000

となってくれれば理想的ですが、たとえ 2 進数でも正の数に何を足してもゼロになることはありません。しかしここで「8 bit より上の桁にあふれても無視する」という条件を入れてみるとどうでしょうか？

  01101001
+)xxxxxxxx
----------
 100000000

9 桁目に 1 が出てきてもそれを無視する、という条件になりましたので、100000000 を作るための足し算になります。これなら x が求まりそうですよね！実際には次のようになります。

  01101001
+)10010111
----------
 100000000

8bit 表現において、10010111 を -105 とすると足し算が計算しやすいことがわかりました。このようなマイナスの整数の表現を「2の補数」と呼びます。これは 32bit でも全く同じで、

  0000 0000 0000 0000 0000 0000 0110 1001
+)1111 1111 1111 1111 1111 1111 1001 0111
-----------------------------------------
1 0000 0000 0000 0000 0000 0000 0000 0000

となり、実際 JavaScript において 0b11111111111111111111111110010111 >> 0 === -105 となります。

2 の補数の表現において、一番上のビットが 1 であることはマイナスであることを示します（一番上のビットのことを符号ビットと呼びます）。なので、32bit において一番大きな正の整数は、一番上のビットをゼロにする必要があるので

0b01111111111111111111111111111111 === 2147483647

となるのです。

正の整数から負の整数のビット表現に変換するには、「正の整数から 1 を引いて、その後全ビットをひっくり返す」という工程で行えます。例えば -2147483647 という数を作る場合、

0b01111111111111111111111111111111 - 1 === 0b01111111111111111111111111111110

と 1 を引いた後に、

0111 1111 1111 1111 1111 1111 1111 1110
                 ↓↓↓↓↓
1000 0000 0000 0000 0000 0000 0000 0001

と 0 と 1 をひっくり返した、0b10000000000000000000000000000001 >> 0 === -2147483647 となります。 >> 0 は ECMAScript の仕様を利用して符号付き 32bit 整数に変換しています。

なお、1 から -1 を作るとわかるように、 1 - 1 === 0 となり、ゼロは全てのビットがゼロなので、それを反転して全てのビットが立った 0b11111111111111111111111111111111 >> 0 === -1 となります。

2 の補数表現の場合、 0b10000000000000000000000000000000 >> 0 === -2147483648 がマイナスで一番大きな値になります。正の数の最大値が 2147483647 なので、 -2147483648 はそれより絶対値で 1 大きくなります。これは 2 の補数の特色でもあります。

このように、符号付き 32bit 整数では -2147483648 〜 2147483647 までの整数を扱うことが出来るわけです。

余談ですが、スーパーマリオブラザーズで無限 1up をし続けて残機が 127 を超えると即ゲームオーバーになってしまうのは、8bit 整数でビットの足し算をし続けた結果、128 機を超えたタイミングで一番上のビットが立ってしまい、結果として残機がマイナスと判断されてしまうためです。

ビット演算

整数の表現方法がわかった所で、次は主なビット演算を解説します。

NOT / ビット否定 (~)

先程「全ビットをひっくり返す」と言いましたが、まさにその演算をビット否定と呼びます。JavaScript の場合の演算子は ~ です。

const a = 0b11001100001010110101011110000100;
console.log((~a).toString(2));

この出力結果を整形すると、こうなります

 a: 11001100001010110101011110000100
~a: 00110011110101001010100001111011

0 が 1 に、1 が 0 に変わっているのが確認できます。

先程 2 の補数の項で紹介した、「1 を引いて、その後全ビットをひっくり返す」というのをコードにしてみました。

const positive = Math.trunc(Math.random() * 2147483647);
console.log(positive); // 例えば 1692412457
const negative = ~(positive - 1);
console.log(negative); // 例えば -1692412457

ビット演算で正の整数から負の整数に変換出来ていることが確認出来ます。

2の補数の項で述べた通り、0 のビット否定は -1 になります。

console.log(~0 === -1); // true

また、ビット否定を 2 回繰り返すと元の値に戻ります。JavaScript において、ビット演算は強制的に数値を 32bit 整数に変換するので、これを利用して以前小数を整数にするテクニックがありましたが、可読性に劣るので使うのはやめましょう。今は Math.trunc という関数で同じことが出来ます。

console.log(~~4.3 === 4); // true
console.log(~~-3.5 === -3); // true

余談ですが、JavaScript では Number(true) === 1 Number(false) === 0 ですが、一部の言語（VB.NET とか N88BASIC とか）は TRUE が -1 であることがあります。それは FALSE が 0 であり、それをビット否定すると -1 になるためです。 NOT FALSE == TRUE ってことですね。TRUE を数字に変換出来る場合でも、常に 1 とは限らないのです。

AND / ビット論理積 (&)

ビット論理積、一般的には単に AND、もしくは目的によってはマスクと呼ばれます。JavaScript の場合の演算子は & です。A & B と呼ばれた場合、A と B の両方でビットが 1 だった場合のみ 1 になります。

const a = 0b01001100001010110101011110000100;
const b = 0b00111001110100000010110011010011;
console.log(a.toString(2));
console.log(b.toString(2));
console.log((a & b).toString(2));

この出力結果を整形すると、こうなります

  A: 01001100001010110101011110000100
  B: 00111001110100000010110011010011
A&B: 00001000000000000000010010000000

両方 0、もしくは片方 0 の桁の出力が 0 に、両方 1 の桁の出力が 1 になっているのが確認出来ますね。

AND は、「マスク」によく使われます。自分が必要としている桁だけを残す使い方です。例えば A の下位 16bit だけほしい、と思った場合、

  A: 0100 1100 0010 1011 0101 0111 1000 0100
  B: 0000 0000 0000 0000 1111 1111 1111 1111
A&B: 0000 0000 0000 0000 0101 0111 1000 0100

このような形で 0b1111111111111111 === 0xffff で AND を取ることにより、A の下位ビットだけを抽出することが出来ます。同じ用に 0xffff0000 で AND を取ると、今度は A の上位 16 bit だけを得ることが出来ます。AND を使う場合、ほとんどがこの「マスク」の処理だと考えてもよいくらい多用されています。

OR / ビット論理和 (|)

ビット論理和、一般的にはビット OR もしくは単に OR と呼ばれます。JavaScript の場合の演算子は | です。A | B と呼ばれた場合、A と B のどちらか片方でビットが 1 だった場合に 1 になります。

const a = 0b01001100001010110101011110000100;
const b = 0b00111001110100000010110011010011;
console.log(a.toString(2));
console.log(b.toString(2));
console.log((a | b).toString(2));

この出力結果を整形すると、こうなります

  A: 01001100001010110101011110000100
  B: 00111001110100000010110011010011
A|B: 01111101111110110111111111010111

片方だけでも 1 の桁の出力が 1 に、両方 0 の桁の出力が 0 になっているのが確認出来ますね。

OR は、AND で「マスク」された結果に対して上書きする時に多用されます。先程 AND の例で 0xffff0000 でマスクして上位 16bit だけ得る話をしましたが、その下位 16bit に任意の数を書き込む時に OR がよく使われるイメージです。

まず、適当な A に対して M = 0xffff0000 で AND してみましょう

  A: 0100 1100 0010 1011 0101 0111 1000 0100
  M: 1111 1111 1111 1111 0000 0000 0000 0000
A&M: 0100 1100 0010 1011 0000 0000 0000 0000

その結果に対して、W = 0x00001234 で OR してみましょう

  A&M: 0100 1100 0010 1011 0000 0000 0000 0000
    W: 0000 0000 0000 0000 0001 0010 0011 0100
A&M|W: 0100 1100 0010 1011 0001 0010 0011 0100

このように、下位 16bit に 0x1234 を埋め込むことが出来ました。この例だと足し算でも良いのですが、足し算だとビットを書き込むという意図が伝わらないので OR を使うのが望ましいです。（40 年前とかだと、足し算より OR の方が速く、その速度差がクリティカルだった、みたいな話もあったりはしますが、少なくとも現代の JavaScript では気にする必要はないです）

OR は、ビットを使ってフラグを書き込む時などにも使われます。例えば 4 ビットの整数に対して、

上位 1 ビット目: 敵から痛恨の一撃を食らったフラグ
上位 2 ビット目: 味方が会心の一撃を出したフラグ
上位 3 ビット目: 敵から攻撃を食らったフラグ
上位 4 ビット目: 味方が攻撃したフラグ

みたいに用意した場合、もし味方が会心の一撃を出したら、何も考えずに flag |= 0b0100 と書けます。足し算の場合、元のフラグの上位 2bit 目が 0 ならばいいのですが、もし 1 だった場合は桁あふれして上位 1 ビットの値を変えてしまいます。余談ですが、ファミコンのドラクエ 4 で 8 回逃げると会心の一撃ばかり出る裏技は、まさにこの足し算で余計な場所のフラグを立ててしまいバグを出してしまった例ですね。

このフラグをチェックする場合、 if (flag & 0b0100) { ... } というような形で書きます（実際は 0b0100 を使わずに 0x4 と書くことが多いです。ビット演算を使う人は、16 進数の 0x1 0x2 0x4 0x8 と 0x7 0xf のビットの立ち方は魂で覚えていることが多いです）

XOR / ビット排他的論理和 (^)

ビット排他的論理和、一般には XOR（エックスオア）と呼ばれる演算です。XOR は面白いんですが、実際に使われることはそんなにありません 。特性だけ覚えておきましょう。

JavaScript の場合の演算子は ^ です。A ^ B と呼ばれた場合、A と B のビットが同じだった場合は 0、違った場合は 1 になります。

A	B	A ^ B
0	0	0
0	1	1
1	0	1
1	1	0

const a = 0b01001100001010110101011110000100;
const b = 0b00111001110100000010110011010011;
console.log(a.toString(2));
console.log(b.toString(2));
console.log((a ^ b).toString(2));

この出力結果を整形すると、こうなります

  A: 01001100001010110101011110000100
  B: 00111001110100000010110011010011
A^B: 01110101111110110111101101010111

A と B が同じ値だと 0 に、違う値だと 1 になることが確認出来るかと思います。

XOR の重要な特性として、同じ値で 2 回 XOR を取ると元の値に戻るというものがあります。

const a = 0b01001100001010110101011110000100;
const b = 0b00111001110100000010110011010011;
console.log(a === (a ^ b ^ b)); // true

    A: 01001100001010110101011110000100
    B: 00111001110100000010110011010011
  A^B: 01110101111110110111101101010111
    B: 00111001110100000010110011010011
A^B^B: 01001100001010110101011110000100

この特性は、文字列などの難読化の初歩の初歩に使われることがあります。

const str = 'TestString';
const encoded = [...str].map(v => v.charCodeAt(0) ^ 0x33);
const encodedStr = String.fromCharCode(...encoded);
console.log(encodedStr); // gV@G`GAZ]T

const decoded = [...encodedStr].map(v => v.charCodeAt(0) ^ 0x33);
const decodedStr = String.fromCharCode(...decoded);
console.log(decodedStr); // TestString

また、XOR は同じ値同士で演算すると 0 になります。

    A: 01001100001010110101011110000100
    B: 01001100001010110101011110000100
  A^B: 00000000000000000000000000000000

アセンブラで eax に 0 を代入する時に MOV EAX, 0 よりも XOR EAX, EAX がよく使用されますが、これは XOR の方がインストラクションのバイト数が短くバイナリが小さくなるため XOR を利用しているそうです。昔は MOV よりも XOR の方が速かったのですが、今はどうなのかわかりません。検索すると世界中の人が議論していて面白いです。

余談ですが、XOR を使って変数の値を入れ替えるネタがあります。もちろんこんなコードを書かないようにしてくださいね。

let x = 12345678;
let y = 98765432;
x ^= y, y ^= x, x ^= y;
console.log({x, y}); // {x: 98765432, y: 12345678}

左シフト (`<<`)

左シフトは、ビットを左にずらします。右の空いたところには 0 が入ります。32bit の桁から溢れたビットは捨てられます。

const num = 123;
console.log(num.toString(2)); // 1111011
console.log((num << 1).toString(2)); // 11110110
console.log((num << 4).toString(2)); // 11110110000
console.log((num << 24).toString(2)); // 1111011000000000000000000000000

2 進数の性質上、桁あふれさえしなければ、左ビットシフトは 2 の累乗の掛け算の結果と等しくなります。

const num = 123;
console.log((num << 1) === num * 2); // true
console.log((num << 4) === num * (2 ** 4)); // true
console.log((num << 24) === num * (2 ** 24)); // true
console.log((num << 25) === num * (2 ** 25)); // false: 123 を 25bit 左にシフトすると signed 32bit からあふれてしまう

10 進数で右にゼロを 1 個追加したら 10 倍に、2 個追加したら 100 倍になるのと同じですね。ただこのテクニックは可読性が良くないので、通常の要件においてはあまり使わない方が良いでしょう。

符号なし右シフト (`>>>`)

>> より先に >>> を説明します。符号なし右シフトは、ビットを右にずらします。右の空いたところには、0 が入ります。一番下のビットは捨てられます。

const num = 123;
console.log(num.toString(2)); // 1111011
console.log((num >>> 1).toString(2)); // 111101
console.log((num >>> 4).toString(2)); // 111
console.log((num >>> 24).toString(2)); // 0

これも 2 進数の性質上、右ビットシフトは、2 の累乗の割り算の結果を切り捨てしたものと等しくなります。これも可読性が良くないので、通常の要件においてはあまり使わない方が良いでしょう。

const num = 123;
console.log((num >>> 1) === Math.trunc(num / 2)); // true
console.log((num >>> 4) === Math.trunc(num / (2 ** 4))); // true
console.log((num >>> 24) === Math.trunc(num / (2 ** 24))); // true, ゼロだけど

またこれは JavaScript 特有なのですが、符号なし右シフトを使うと、結果が符号なし（unsigned）の 32bit 整数になります。他のビット演算は全て符号あり（signed）32bit 整数になるので、この特性を利用して unsigned 32bit 整数を得ることがよくあります。

const num = 0b10000000000000000100000000000000;
console.log(num >> 0); // -2147467264
console.log(num >>> 0); // 2147500032 ← 符号付き 32bit 整数の上限を超えている
console.log((num >> 0).toString(2)); // -1111111111111111100000000000000
console.log((num >>> 0).toString(2)); // 10000000000000000100000000000000

3 つ目のマイナスの 2 進数は ECMAScript の Number#toString の仕様上マイナスの数字はこうなってしまうのですが、 >>> 0 で符号なし 32bit 整数に変換することで本来の bit 表現を得ることが出来ました。

右シフト (`>>`)

右シフトは、ビットを右にずらします。右の空いたところには、 一番上位ビットの数がそのまま入ります 。一番下のビットは捨てられます。

一番上のビットがゼロの場合は、普通にビットが右に行くだけ、>>> と全く同じです。

const num = 123;
console.log(num.toString(2)); // 1111011
console.log((num >> 1).toString(2)); // 111101
console.log((num >> 4).toString(2)); // 111
console.log((num >> 24).toString(2)); // 0

const num = 123;
console.log((num >> 1) === Math.trunc(num / 2)); // true
console.log((num >> 4) === Math.trunc(num / (2 ** 4))); // true
console.log((num >> 24) === Math.trunc(num / (2 ** 24))); // true, ゼロだけど

さて問題は一番上のビットが 1 の場合です。

const num = (0b10000000000000000100000000000000) >> 0;
console.log((num >> 1 >>> 0).toString(2)); // 11000000000000000010000000000000
console.log((num >> 4 >>> 0).toString(2)); // 11111000000000000000010000000000
console.log((num >> 24 >>> 0).toString(2)); // 11111111111111111111111110000000

2 の補数の項で説明した通り、一番上のビットが 1 であるとその整数表現は必ずマイナスになります。なので、>> でビットシフトをする場合、マイナスを維持したままビットシフトをしていることになります。これが大きな意味を持つのが「符号拡張」と呼ばれる場面です。

符号拡張

上の 2 の補数の解説で、8bit の整数であれば 10010111 が -105 を表現する、という話をしました。しかし JavaScript は 8bit の整数型を持たないので（TypedArray を使えば実現出来るのですが）、0b10010111 === 151 と全然違う数字になってしまいます。

これを 32bit に拡張するのを「符号拡張」と言います。8bit の整数を 32bit の整数に拡張する場合、24bit 拡張する必要があります。そこで、まず 10010111 を 24 bit 左にシフトします。そうすると、右に 24 個の 0 が追加されるので、

1001 0111 0000 0000 0000 0000 0000 0000

となります。今度はこれを符号付きシフト(>>)で 24 ビットシフトしてみましょう。一番上のビットが 1 なので、次のようになります。

1111 1111 1111 1111 1111 1111 1001 0111

これで、本来欲しかった 32bit 整数の -105 を得ることが出来ました。コードにすると次の通りです。

const num = 0b10010111;
console.log(num); // 151
console.log(num << 24 >> 24); // -105

一番上のビットがゼロの場合は、ただ24ビット移動するだけで何の変化もありません。

const num = 0b01101001;
console.log(num); // 105
console.log(num << 24 >> 24); // 105

同じ数でシフトの往復ビンタをしている時は、まず間違いなくこの符号拡張をしています。整数のビット数を変換する時に極めて一般的な手法ですので、見たら「あれか！」と思い出すくらいには心に留めておくと良いと思います。

まとめ

余談を書きすぎたせいか、思ったより長くなりました。次はここからリトルエンディアン＆ビッグエンディアンの話や浮動小数点の表現などに進んでいったりするのが良いのでしょうが、とりあえずここまで完全に理解しておけば、いきなりビット演算の世界に放り込まれてもソースを読むことくらいは出来るのではないかと思います。

ビット演算なんて知らなくても、2 の補数なんて意識しなくても、プログラムを書く上でそんなに困ることはないのかもしれません。ただ、必要がない故に学ぶ機会も同様に減っているのは少し残念だな、と思って記事にしてみました。釈迦に説法だった人も多いかと思いますが、もし知らない内容をこの記事で学べた、ということがあれば本望です。

JavaScript で学ぶビット演算の基礎

JavaScript における数値

ビットとは

マイナスの表現（2の補数）

ビット演算

NOT / ビット否定 (~)

AND / ビット論理積 (&)

OR / ビット論理和 (|)

XOR / ビット排他的論理和 (^)

左シフト (<<)

符号なし右シフト (>>>)

右シフト (>>)

符号拡張

まとめ

左シフト (`<<`)

符号なし右シフト (`>>>`)

右シフト (`>>`)