ビットの論理と文字コード

論理演算は、入力の組合せをぜんぶ書き出した表でいちどに確かめられる。これを 真理値表 と呼ぶよ。

入力が2つなら、組合せは 0 0 0 1 1 0 1 1 の4通りだけ。この4行を上から下まで埋めれば、その演算の性質は言い尽くせる。

論理積は、いちばん下の 1 1 の行だけが 1 になる。論理和は、いちばん上の 0 0 の行だけが 0 で、あとは全部 1 だよ。

覚え方はひとつでいい。論理積は厳しくて、論理和はゆるい。論理積は全員が 1 でないと 1 を出さないし、論理和は1つでも 1 があれば 1 を出してしまう。

この「厳しい・ゆるい」は逆からも使える。論理和の答えが 1 で、片方が 0 だと分かっているなら、残る片方は必ず 1。論理積の答えが 1 なら、両方とも 1。表を全部埋めなくても、そこだけで答えが決まる問題があるよ。

ここでもう1つ、&& にも || にも当てはまらない演算を覚える。排他的論理和（XOR）だよ。

これは「どちらか一方だけ が 1 のとき 1」という演算。両方 1 のときは 0 になるところが論理和との違いで、そこが「排他的」という名前の意味だよ。

言いかえると、2つが違えば 1、同じなら 0。値をくらべて「違う？」と聞いているだけとも読める。JavaScript には専用の演算子がないけれど、a !== b がやっていることに近い。

この性質のおかげで XOR には便利な使い道がある。1 と XOR したところは反転し、0 と XOR したところは変わらないんだ。だから「ここだけ反転させたい」ときの道具になる。同じ相手ともう1回 XOR すれば元に戻るよ。

4つの演算は、2つの丸が重なった図（ベン図）でも整理できる。丸 A と丸 B を少し重ねて描いてみよう。

• 論理積 … 2つの丸が 重なった部分だけ
• 論理和 … 2つの丸を 合わせた全体
• 否定 … 丸の 外側
• 排他的論理和 … 合わせた全体から、重なった部分を 取り除いたところ

真理値表は行を数えるための道具、ベン図は関係をひと目で見るための道具だよ。同じことを2通りで見ているだけなので、どちらか得意なほうで思い出せれば十分。

排他的論理和がなぜ「論理和から重なりを引いたもの」になるのか、真理値表の 1 1 の行と見くらべておこう。ここが 0 なのが、まさに「重なりを取り除いた」に対応しているよ。

実際のコンピュータでは、1ビットだけを相手にすることはほとんどない。8ビットや16ビットのビット列どうしで演算するよ。

やり方はかんたんで、同じ位置の桁だけを見て、桁ごとに独立して計算する。足し算のような桁上がりはいっさい起きない。ここが算数の足し算と決定的に違うところだよ。

10110011 と 00001111 で3つの演算を並べてみよう。いちばん右の桁から順に、上下の1ビットずつをくらべていくだけだ。

ビット列は16進数で書かれることが多い。16進数の1桁 = 4ビットなので、0F は 00001111、F0 は 11110000、FF は 11111111、7F は 01111111 だよ。この4つは丸暗記しておくと試験が速い。

ビット演算のいちばんの使いどころが マスク処理 だよ。ほしい桁だけに手を入れて、ほかの桁はさわらないためのやり方。相手のビット列（マスク）で、どの桁を狙うかを指定する。

• 取り出す・残す … AND。マスクが 1 の桁はそのまま残り、0 の桁は 0 に消える
• 立てる（1 にする） … OR。マスクが 1 の桁が 1 になり、0 の桁はそのまま
• 反転する … XOR。マスクが 1 の桁だけが反転し、0 の桁はそのまま

見分け方は、AND は消す方向、OR は立てる方向、XOR は反転。3つとも「マスクが 0 の桁は放っておく」のが共通で、AND だけは逆に「マスクが 1 の桁を放っておく」と読むと分かりやすいよ。

試験でよく出るのがこの言い換えだ。「下位4ビットを取り出す」は 0F との AND、「全ビットを反転する」は FF との XOR、「最上位1ビットを 0 にして残りを得る」は 7F との AND。求められている操作から、演算とマスクの2つを同時に決めるのがコツだよ。

もう1つの道具が シフト演算。ビット列をまるごと左右にずらすだけの操作だよ。あいた桁には 0 が入り、はみ出した桁は捨てられる。

ここで大事なのは、シフトが掛け算と割り算になることだ。2進数は1桁ごとに重みが2倍なので、

• 左に1ビット … 値が 2倍
• 右に1ビット … 値が 1/2（あまりは切り捨て）

nビットずらせば 2 の n 乗ぶんだよ。左に4ビットで16倍、右に4ビットで1/16。掛け算より速いので、実際のプログラムでも使われる。

16進数と組み合わせると、もっと便利な読み方ができる。16進数の1桁は4ビットなので、4ビットのシフトは16進数の1桁ぶんの移動になる。3A7F を右に4ビットずらせば 03A7 になるということだね。

あいた桁につねに 0 を入れるものを 論理シフト と呼ぶよ。符号を考えて別のものを入れる 算術シフト もあるけれど、符号の話は前のレッスンの持ち場なので、ここでは論理シフトだけ押さえておこう。

論理式を書きかえるための決まりごとが ド・モルガンの法則 だよ。ひとことで言うと、否定を内側に配ると、AND と OR が入れかわる。

• NOT(A AND B) = (NOT A) OR (NOT B)
• NOT(A OR B) = (NOT A) AND (NOT B)

言葉で確かめると納得しやすい。「A と B の両方ではない」は、「A でないか、B でないか、どちらかだ」と同じことだよね。ひとつでも欠けていれば「両方」は成り立たないからだ。

逆向きも同じ。「A も B もどちらでもない」は、「A でなくて、かつ B でもない」と同じ。

見分け方は3か所を同時に変えること。外側の否定を外し、内側の2つに否定を付け、真ん中の演算を入れかえる。3つのうち1つ忘れると別の式になってしまうので、選択肢にはその「1つ忘れた形」がちゃんと用意されているよ。

もう1つ、否定を2回かけると元に戻ることも一緒に覚えよう。NOT(NOT A) = A だ。ド・モルガンで式を動かすと NOT(NOT ...) の形がよく出てくるので、その場で消していけるよ。

ここまでの演算を、そのまま電子部品にしたものが ゲート だよ。論理回路はこのゲートを組み合わせて作る。

基本になるのは4つ。AND ゲート、OR ゲート、NOT ゲート、XOR ゲート。入力の線が左から入って、出力の線が右へ出ていくだけの部品だと思えばいい。

これに、否定を後ろにくっつけたものがある。NAND は NOT(A AND B)、NOR は NOT(A OR B) だよ。名前は AND / OR の頭に N（Not）を付けただけ。真理値表は AND / OR の結果を上下にそっくり裏返した形になる。

おもしろいのは、NAND だけあれば全部のゲートが作れることだよ。たとえば同じ入力を両方につなぐと A NAND A = NOT(A AND A) = NOT A になって、NOT ゲートのかわりになる。ここからド・モルガンの法則を使えば AND も OR も組み立てられる。だから実際の IC は NAND を並べて作られていることが多いんだ。

NAND を並べた回路を読むときは、ド・モルガンで否定を追い出すのが定石。NOT(NOT(A・B) AND NOT(C・D)) のような式は、法則を1回当てるだけで A・B ＋ C・D まで一気にほどけるよ。

ゲートを2つ組むだけで、1桁の2進数の足し算が作れる。これが 半加算器 だよ。

1桁どうしの足し算を書き出してみよう。0+0=0、0+1=1、1+0=1、そして 1+1=10。最後だけ2桁になって、桁上げが出るところが肝心だ。

答えを2つに分けて考える。和の1桁目と、桁上げだよ。

• 和の1桁目 … 0 1 1 0 の並び。これは XOR の真理値表そのまま
• 桁上げ … 0 0 0 1 の並び。これは AND の真理値表そのまま

つまり、x と y を XOR ゲートと AND ゲートの両方に入れて、XOR の出力を和、AND の出力を桁上げにすればいい。和が XOR、桁上げが AND — この対応だけ覚えておけば足りるよ。

なお半加算器は、下の桁からの桁上げを受け取れない。だから2桁目より上ではそのまま使えず、桁上げの入力も持つ 全加算器 を使う。全加算器は半加算器を2つ組んで作るよ。

コンピュータの中身はビットしかないので、文字にも番号を決めておく必要がある。その取り決めが 文字コード だよ。

いちばん古くて基本になるのが ASCII。英数字と記号を 7ビット（128通り）で表す。A が 65、a が 97 で、そこからアルファベット順に1ずつ増えていく決まりだよ。

日本語は128通りでは足りないので、1文字に2バイトを使う方式が作られた。シフト JIS と EUC（EUC-JP）がそれで、どちらも同じ日本語を表すのに別々の番号を割り振っている。同じ文書を違う方式で読むと文字化けするのは、この食い違いのせいだよ。

方式が分かれてしまった反省から、世界中の文字を1つの番号表にまとめようとして作られたのが Unicode だ。

ここで区別したいのが、Unicode と UTF-8 の関係。Unicode は番号の表そのもので、UTF-8 はその番号をバイト列に書き表すやり方だよ。UTF-8 は文字によって 1〜4バイトと長さを変え、しかも ASCII の範囲は ASCII とまったく同じバイトになるように作られている。だから英数字だけの古いファイルは、そのまま UTF-8 として読めるんだ。

データは通信や記憶のとちゅうで化けることがある。壊れたことに気づくための仕組みが 誤り検出 だよ。共通の考え方は、本体から計算した余分な値を一緒に持たせておいて、受け取った側で計算しなおすこと。

パリティビット はいちばん単純で、1 の個数が偶数（または奇数）になるように1ビット足す。1ビットが化ければ個数の偶奇が変わるので気づけるけれど、2ビットが同時に化けると偶奇が戻ってしまい見逃す。それに、どの桁が化けたかは分からないので訂正できない。ここが試験でいちばん問われるところだよ。

奇数パリティと偶数パリティは「1 の個数をどちらにそろえるか」という取り決めの違いだけで、検出できる力はまったく同じ。ここを差があるように書いた選択肢が出るので気をつけよう。

1文字ごとに縦方向で付けるのを 垂直パリティ、ブロック全体に横方向で付けるのを 水平パリティ と呼ぶ。両方を組み合わせると、化けた桁が縦横の交点で特定できるので、1ビットの誤りなら訂正までできるよ。

残る3つも並べておこう。チェックディジット はコードの各桁から計算した検査数字を末尾に足すやり方で、打ちまちがいを見つける。ハミング符号 は検査ビットを複数持たせて、1ビットの誤りを訂正でき、2ビットの誤りを検出できる。CRC は、ビット列を決めた 生成多項式で割った余りを付けて送り、受信側で同じ式で割り切れるかを見る。連続してまとめて化ける誤りに強く、通信で広く使われているよ。