プログラミング頻出概念！二進数とは？基礎からビット演算までわかりやすく解説

二進数とは

二進数（binary number）は、0 と 1 の 2 種類の数字だけを使って数を表す方法です。

普段私たちが使っているのは十進数で、0〜9 の 10 種類の数字を使って数を表します。それに対して二進数は、0 と 1 だけですべての数を表現します。

なぜ二進数が大事なのか

コンピュータの中は、すべて二進数で動いています。

コンピュータは電気で動いていて、電気の「流れている／流れていない」という 2 つの状態を使って情報を表しています。この 「流れている = 1 / 流れていない = 0」 が、二進数の本質です。

だからプログラミングを少し深く理解しようとすると、遅かれ早かれ二進数と向き合うことになります。競技プログラミングでは特に、bit 全探索やビット演算など、二進数の考え方を直接使うテクニックがたくさん出てきます。

二進数の仕組み

二進数の桁は、右から順に 1 の位、2 の位、4 の位、8 の位、16 の位、... と、2 倍ずつ増えていく「重み」を持っています。

十進数が「1 の位、10 の位、100 の位、1000 の位」と 10 倍ずつ増えていくのとまったく同じ仕組みで、基準が 10 から 2 に変わっただけです。

二進数 → 十進数の変換

たとえば二進数 1011 を十進数に変換してみます。各桁の「重み × ビット」を足し合わせるだけです。

桁の位置	重み	ビット	寄与
一番右	1	1	1
右から 2 番目	2	1	2
右から 3 番目	4	0	0
左端（4 番目）	8	1	8

合計すると 8 + 0 + 2 + 1 = 11。というわけで、二進数 1011 は十進数で 11 です。

十進数 → 二進数の変換

逆に、十進数 13 を二進数に変換してみましょう。方法は簡単で、2 で割った余りを下から順に並べるだけです。

1. 13 ÷ 2 = 6 余り 1
2. 6 ÷ 2 = 3 余り 0
3. 3 ÷ 2 = 1 余り 1
4. 1 ÷ 2 = 0 余り 1

割り切れなくなる（商が 0 になる）まで繰り返して、余りを下から順に読み上げると 1101。というわけで、十進数 13 は二進数で 1101 です。

ビット演算

プログラミングでは、二進数の各桁（= ビット）に対して直接演算を行うことがあります。これをビット演算と呼びます。C++ では次の演算子が用意されています。

演算	演算子	意味
AND	&	両方が 1 のときだけ 1
OR	|	どちらかが 1 なら 1
XOR	^	違うときだけ 1
NOT	~	0 と 1 を反転
左シフト	<<	ビットを左にずらす
右シフト	>>	ビットを右にずらす

AND（&）、OR（|）、XOR（^）

この 3 つは、2 つの数の同じ桁同士を見比べて、新しいビットを作る演算です。

  1100          1100          1100
& 1010        | 1010        ^ 1010
------        ------        ------
  1000          1110          0110
  (AND)         (OR)          (XOR)

それぞれの使いどころを簡単にまとめておきます。

• AND (&): 「特定のビットが立っているかを調べる」ときに使う。たとえば x & (1 << 3) は、x の右から 4 桁目のビットが 1 かどうかを判定する定番イディオム。
• OR (|): 「特定のビットを立てる」ときに使う。x | (1 << 3) で、x の右から 4 桁目を強制的に 1 にできる。
• XOR (^): 「特定のビットを反転させる」ときに使う。同じ値を 2 回 XOR すると元に戻る、という面白い性質もある。

左シフト・右シフト

<< と >> は、ビットを指定した数だけ横にずらす演算です。

• x << n : x のビットを n だけ左にずらす（＝ x × 2ⁿ と同じ）
• x >> n : x のビットを n だけ右にずらす（＝ x ÷ 2ⁿ と同じ、切り捨て）

0011 << 1 = 0110    (3 × 2 = 6)
0011 << 2 = 1100    (3 × 4 = 12)
1100 >> 1 = 0110    (12 ÷ 2 = 6)
1100 >> 2 = 0011    (12 ÷ 4 = 3)

特に 1 << n は「2 の n 乗」を意味する競プロでの超定番イディオムです。bit 全探索などで本当によく出てくるので、形で覚えてしまいましょう。

式	二進数表記	十進数
1 << 0	0001	1
1 << 1	0010	2
1 << 2	0100	4
1 << 3	1000	8
1 << N	右から N+1 桁目だけ 1	2ᴺ

プログラミングでの活用例

bit 全探索

N 個のものから「選ぶ／選ばない」の組み合わせをすべて試したいとき、整数を二進数として扱うと、2ᴺ 通りをきれいに列挙できます。

for (int bit = 0; bit < (1 << N); bit++) { // 0 〜 2^N - 1
    for (int i = 0; i < N; i++) {
        if (bit & (1 << i)) { // i 番目のビットが立っていれば選ぶ
            // i 番目を「選ぶ」ときの処理
        }
    }
}

ここで出てくる (1 << N)、bit & (1 << i) は、どちらもこの記事で解説したビット演算です。二進数を理解していれば、このコードが「2ᴺ 通りのパターンを順に試している」という意味がスッと読み取れます。

詳しい使い方は 全探索とは の「bit 全探索」のセクションをご覧ください。

フラグ管理

「N 個の機能の on/off 状態」などを 1 つの整数で管理するテクニックもあります。各ビットを 1 つのフラグとして使えば、32 個（int）や 64 個（long long）のフラグを整数 1 つにまとめることができます。メモリ効率が良いので、競プロでもよく使われる書き方です。

まとめ

二進数のポイントをもう一度整理しておきましょう。

• 二進数は 0 と 1 だけで数を表す方法。コンピュータはすべて二進数で動いている
• 十進数との変換は「重み（1, 2, 4, 8, ...）を足し合わせる」または「2 で割った余りを下から並べる」
• C++ では &（AND）・|（OR）・^（XOR）・~（NOT）・<<（左シフト）・>>（右シフト）のビット演算子が使える
• 1 << n は 2 の n 乗を意味する超定番イディオム
• bit 全探索などの競プロ頻出テクニックで、二進数の理解が直接役に立つ

二進数は一見とっつきにくく見えますが、仕組みが分かれば「ただの別の数の書き方」にすぎません。一度なじんでしまえば、bit 全探索のような強力なテクニックも自然に使いこなせるようになります。

次に読む記事

• 全探索とは — 二進数を活用する bit 全探索が登場します
• 二分探索とは — 同じ「二」がつくアルゴリズム。混同しないように整理しておきましょう
• 競技プログラミングの始め方 — そもそもプログラミングで何をやるのか知りたい方へ