離散数学

ねらい

コンピュータが数をどのように表し、どのように計算しているかを学びます。このレッスンを終えると、2進数と10進数を相互に変換でき、負の数や小数の表し方、計算で生じる誤差、集合と論理演算の基本を説明できるようになります。

基数：コンピュータは2進数で数を扱う

私たちがふだん使う数は10進数です。0から9までの10種類の数字を使い、10集まると桁が上がります。この「何種類の数字で桁を上げるか」を基数といいます。10進数の基数は10です。

コンピュータの回路は、電気が流れているか流れていないかの2つの状態しか区別できません。そこで、0と1の2種類だけで数を表す2進数が使われます。2進数の基数は2です。ただし、2進数は桁数が長くなって人間には読みづらいため、プログラムの世界では8進数や16進数もよく使われます。16進数は0から9の数字とAからFの文字で16種類を表します。

2進数から10進数への変換

2進数の各桁は、右から順に1、2、4、8のように「2の累乗」の重みを持ちます。2進数の1011を10進数に変換してみましょう。

重みが8の桁と2の桁と1の桁に1が立っているので、8と2と1を足して11になります。2進数の1011は10進数の11です。

10進数から2進数への変換

10進数を2進数に変換するには、2で割った余りを下の桁から並べます。10進数の13を変換してみましょう。

1. 13を2で割ると、商が6で余りが1です。
2. 6を2で割ると、商が3で余りが0です。
3. 3を2で割ると、商が1で余りが1です。
4. 1を2で割ると、商が0で余りが1です。

余りを最後から逆にたどると1101です。10進数の13は2進数の1101になります。

動かして確かめる

2進数の桁をオン/オフして合計を確かめるか、10進数を2で割り続けて2進数を作るか、 向きを切り替えて試してみましょう。

16進数への変換

16進数は、2進数4桁をまとめて1桁で表せるため、2進数より短く書けます。2進数と16進数の対応は次のとおりです。

2進数を16進数に変換するには、右から4桁ずつ区切って、それぞれを表の対応で置き換えます。2進数の10110110を変換してみましょう。

1. 右から4桁ずつ区切ると、1011と0110になります。
2. 1011は表からB、0110は表から6です。

2進数の10110110は、16進数のB6になります。

16進数から10進数への変換は、2進数と同じく桁の重みを使います。16進数の各桁は、右から順に1、16、256のように「16の累乗」の重みを持ちます。16進数のB6を10進数に変換してみましょう。

1. Bは10進数で11なので、16の位は11×16＝176です。
2. 6は1の位なので、そのまま6です。

176と6を足して、16進数のB6は10進数の182になります。

数値の表現：負の数と小数

負の数は補数で表す

コンピュータにはマイナスの記号がありません。そこで、負の数は補数という考え方で表します。2進数で使われるのは「2の補数」で、次の手順で作ります。

1. もとの数の各ビットの0と1を反転します。
2. 反転した結果に1を加えます。

8ビットで5は00000101です。各ビットを反転すると11111010になり、1を加えると11111011になります。これがマイナス5の表現です。補数を使うと、引き算を足し算の回路だけで実現できます。5からマイナス5を足すと、結果の下位8ビットがちょうど00000000になることが、この表現のうまさです。

小数は固定小数点数か浮動小数点数で表す

小数の表し方には2つの方式があります。

1. 固定小数点数は、小数点の位置をあらかじめ決めて表す方式です。仕組みが単純ですが、表せる数の範囲が狭くなります。
2. 浮動小数点数は、数を「仮数」と「指数」に分けて表す方式です。10進数でいえば「1.25かける10の3乗」のように、仮数（1.25）と指数（3）の組で数を表します。小さい数から大きい数まで幅広く表せます。ビット数の少ない形式を単精度浮動小数点数、多い形式を倍精度浮動小数点数といいます。

このほか、10進数の各桁を4ビットの2進数で表すBCD（2進化10進）という表現もあり、桁数が決まった金額計算などで使われます。

算術演算と精度：計算には誤差がつきもの

シフト演算

2進数の各ビットを左右にずらす操作をシフト演算といいます。左に1ビットシフトすると値は2倍に、右に1ビットシフトすると値は2分の1になります。たとえば00000110（10進数の6）を左に1ビットシフトすると00001100（10進数の12）になります。シフトには、空いた桁に0を詰める論理シフトと、符号ビットを保ったままずらす算術シフトがあります。

誤差の種類

浮動小数点数はビット数が有限なので、すべての実数を正確には表せません。冒頭のストーリーで先輩が言った「浮動小数点数の誤差」は、ここから生まれます。試験でよく問われる誤差は次の4つです。

また、演算結果が表現できる範囲の上限を超えることをオーバーフロー（あふれ）、下限より小さくなり表現できないことをアンダーフローといいます。

集合と命題：ものの集まりを図で考える

集合は「ものの集まり」を表す考え方で、条件で絞り込む処理やデータベースの検索の土台になります。2つの集合AとBに対して、次の言葉を押さえましょう。

1. 和集合は、AとBの少なくとも一方に属する要素の集まりです。
2. 積集合は、AとBの両方に属する要素の集まりです。
3. 補集合は、Aに属さない要素の集まりです。
4. 部分集合は、ある集合の要素がすべて別の集合にも属している関係です。

これらの関係は、円を重ねて描くベン図で視覚的に表せます。和集合と積集合は円の重なりのどこを指すかで区別でき、補集合は全体集合の中でAを除いた部分、部分集合はAの円がBの円に完全に収まる形で表せます。また、「真」か「偽」かがはっきり決まる文を命題といいます。「10は偶数である」は真の命題、「10は奇数である」は偽の命題です。

論理演算：0と1の世界の計算ルール

コンピュータの判断は、真（1）と偽（0）を組み合わせる論理演算でできています。基本の演算は次のとおりです。入力AとBのすべての組合せに対する結果を並べた表を真理値表といいます。

1. 論理積（AND）は、両方が1のときだけ1になります。
2. 論理和（OR）は、少なくとも一方が1なら1になります。
3. 排他的論理和（XOR）は、2つの値が異なるときだけ1になります。
4. 否定（NOT）は、1つの入力の0と1を反転します。

論理積の結果を否定したものを否定論理積、論理和の結果を否定したものを否定論理和といいます。

ド・モルガンの法則

否定と論理積・論理和のあいだには、ド・モルガンの法則という重要な関係があります。言葉で書くと次の2つです。

1. 「AとBの論理積」の否定は、「Aの否定」と「Bの否定」の論理和に等しくなります。
2. 「AとBの論理和」の否定は、「Aの否定」と「Bの否定」の論理積に等しくなります。

「会員であり、かつ20歳以上」の否定が「会員でない、または20歳未満」になる、と具体例で覚えると忘れません。プログラムの条件式を書き換えるときに頻繁に使います。

例題

次の問いに答えてください。

問1 2進数の1100を10進数に変換してください。

問2 10進数の9を4ビットの2進数で表したうえで、その2の補数を求めてください。

解答と解説

問1の答えは12です。1100は重みが8の桁と4の桁に1が立っているので、8と4を足して12になります。

問2について、10進数の9は2進数で1001です。各ビットを反転すると0110になり、1を加えると0111になります。よって2の補数は0111です。

応用

本試験を意識した問題を解いてみましょう。

問 値がほぼ等しい2つの浮動小数点数の引き算を行ったところ、結果の有効な桁数が大きく減ってしまいました。この現象を表す用語はどれでしょうか。次の中から選んでください。

1. 桁落ち
2. 情報落ち
3. 丸め誤差
4. オーバーフロー

解答と解説

答えは1の桁落ちです。ほぼ等しい数どうしの引き算では、上位の桁が打ち消し合って有効数字が大きく減ります。これを桁落ちといいます。情報落ちは、絶対値の大きい数と小さい数の足し算で小さい数が結果に反映されない現象なので、引き算で桁数が減る本問には当てはまりません。丸め誤差は表せない細かい部分を丸めることで生じる差であり、桁数が大きく減る現象そのものではありません。オーバーフローは演算結果が表現できる範囲を超えることなので、これも本問の現象とは異なります。