概要
情報技術の基礎として理解しておきたい離散数学のうち、基数変換、補数表現、小数表現、数値誤差、集合演算を整理する。
離散数学は、計算機が数値や論理をどのように扱うかを理解するための土台となる。
基数変換で桁を取り出す順序、補数で減算を加算に置き換えられる理由、有限桁で計算すると誤差が生じる仕組みを具体例から確認する。集合演算は、同じ要素に異なる条件を適用して結果を比較する。
この記事の構成
- 基数変換
整数部と小数部で桁を取り出す順序が異なる理由と、変換結果の検算方法を確認。 - 補数表現（負の数の表現）
ビット反転と加算で補数を作る理由、桁上がりの扱い、負の結果の読み方を整理。 - 小数表現
固定小数点数と浮動小数点数の表し方、正規化の条件を確認。 - 基数変換の誤差
有限小数になる場合と循環小数になる場合を、変換手順と分母から比較。 - 数値演算の誤差
丸め誤差・桁落ち・情報落ちの違いと、式の変形による桁落ちの軽減を確認。 - 集合
具体的な要素を使い、集合演算と AND・OR・NOT・XOR の対応を比較。
基数変換
基数変換とは、ある基数で表された数を、別の基数の表現へ変換することを指す。
基数は、桁上がりする基準となる数で、\(2\) 進数なら \(2\)、\(10\) 進数なら \(10\)、\(16\) 進数なら \(16\) となる。
-
例 \(1\) : 整数の基数変換 \(10\) → \(2\)
\((25)_{10}\) の基数を \(2\) に変換。
整数部の変換では、変換元の数を変換先の基数で割り、余りを下から上へ読む。\(25 \div 2 = 12 \) 余り \( 1 \)
\(12 \div 2 = 6 \) 余り \( 0 \)
\(6 \div 2 = 3 \) 余り \( 0 \)
\(3 \div 2 = 1 \) 余り \( 1 \)
\(1 \div 2 = 0 \) 余り \( 1 \)
→ 最後の剰余から順に並べて \((11001)_{2}\)最初の割り算は \(25 = 2 \times 12 + 1\) と書ける。\(2 \times 12\) は \(2\) の倍数なので、余りの \(1\) が \(2^0\) の桁を決める。
次に商の \(12\) を割ると \(12 = 2 \times 6 + 0\) となり、これを代入すると次のようになる。\[ {\small 25 = 2(2 \times 6 + 0) + 1 = 2^2 \times 6 + 2 \times 0 + 1 } \]\(2\) 回目の余りは \(2^1\) の桁に対応する。同じ操作で下位の桁から順に求まるため、通常の表記では余りを逆順に並べる。
検算すると、次のように元の値に戻る。\[ {\small 1 \times 2^4 + 1 \times 2^3 + 1 \times 2^0 = 16 + 8 + 1 = 25 } \] -
例 \(2\) : 整数の基数変換 \(10\) → \(16\)
\((555)_{10}\) の基数を \(16\) に変換。
\(16\) 進数では、\(10\) から \(15\) までを \(A\) から \(F\) で表す。\(555 \div 16 = 34 \) 余り \( 11(B) \)
\(34 \div 16 = 2 \) 余り \( 2 \)
\(2 \div 16 = 0 \) 余り \( 2 \)
→ 最後の剰余から順に並べて \((22B)_{16}\)\(16\) 進数でも余りは下位の桁から求まる。検算は次のとおり。
\[ {\small 2 \times 16^2 + 2 \times 16 + 11 = 512 + 32 + 11 = 555 } \] -
例 \(3\) : 小数の基数変換 \(10\) → \(2\)
\((0.75)_{10}\) の基数を \(2\) に変換。
小数部の変換では、小数部分に変換先の基数を掛け、得られた整数部を上から順に読む。\(0.75 \times 2 = 1.50\) → 整数部 \(1\)
\(0.50 \times 2 = 1.00\) → 整数部 \(1\)
→ 得られた整数部を上から順に並べて \((0.11)_{2}\)小数部に \(2\) を掛けると、\(2^{-1}\) の桁が整数部へ移る。整数部の \(1\) を取り除き、残った \(0.50\) に再び \(2\) を掛けることで、次の桁を取り出せる。
小数点に近い桁から求まるため、整数部の変換と違って順序を逆にしない。検算は次のとおり。\[ {\small (0.11)_2 = 1 \times 2^{-1} + 1 \times 2^{-2} = 0.5 + 0.25 = 0.75 } \]残りの小数部が \(0\) になれば変換は終了する。\(0\) にならない場合の扱いは、後の「基数変換の誤差」で確認する。
-
例 \(4\) : 小数を含む基数変換 \(2\) → \(10\)
\((110.01)_{2}\) の基数を \(10\) に変換。
各桁に基数のべき乗を掛け、その総和を求める。\[ {\small (110.01)_{2} = 1 \times 2^{2} + 1 \times 2^{1} + 0 \times 2^{0} + 0 \times 2^{-1} + 1 \times 2^{-2} } \]\[ {\small = 4 + 2 + 0 + 0 + 0.25 = (6.25)_{10} } \]
補数表現（負の数の表現）
-
補数表現
ここでは、固定した桁数における \(r\) の補数（基数の補数） を扱う。
基数 \(r\) は \(2\) 以上の整数、桁数 \(n\) は正の整数とする。\(n\) 桁の \(r\) 進数で整数 \(x\) が \(0 \leq x < r^n\) を満たすとき、\(x\) の \(r\) の補数は \((-x) \bmod r^n\) で表される。ここで \(\bmod r^n\) は、\(r^n\) で割ったときの \(0\) 以上 \(r^n\) 未満の余りを求める操作を表す。\(0 < x < r^n\) の場合は、次の式で求められる。\(x = 0\) の場合は \(0\) とする。
\[ {\small r^{n} - x } \]-
例 \(1\) : \(2\) 桁の \(10\) 進数 \((55)_{10}\) の \(10\) の補数。
\[ {\small 10^{2} - 55 = 45 } \] -
例 \(2\) : \(8\) 桁の \(2\) 進数 \((00001101)_{2}\) の \(2\) の補数。
\(2\) 進数では、全ビットを反転したものが \(1\) の補数で、さらに \(1\) を加えると \(2\) の補数になる。
\[ {\small 00001101 \rightarrow 11110010 \rightarrow 11110011 } \]元のビット列と反転したビット列を足すと、各桁が \(1\) になり、\((11111111)_2 = 255\) となる。そのため、反転した値は \(255 - 13 = 242\) であり、さらに \(1\) を足すと \(256 - 13 = 243\) になる。
同様に、\(n\) ビットの反転は \(2^n - 1 - x\)、そこに \(1\) を足すと \(2^n - x\) になる。\(x = 0\) の場合も、下位 \(n\) ビットだけを残せば \(0\) となる。
-
-
補数表現するメリット
補数を使うと、減算を加算として扱える。
コンピュータ内部では、引き算専用の仕組みを用意するより、補数を使って加算として扱う方が都合がよい。-
例 \(1\) : \((25)_{10} - (13)_{10}\) を \(2\) 桁の \(10\) 進数で考える。
\[ {\small 25 - 13 = 25 + (-13) } \]\(-13\) を \(2\) 桁の \(10\) 進数の補数で表すと、\(100 - 13 = 87\) となる。
\[ {\small 25 + 87 = 112 } \]\(2\) 桁の範囲で見るため、上位の桁上がりを捨てると \(12\) となる。
桁上がりを捨てられる理由は、式を変形すると分かる。
\[ {\small 25 + (100 - 13) = 100 + (25 - 13) } \]補数を加えた結果は求めたい差より \(100\) 大きいが、下位 \(2\) 桁を残すとその \(100\) が取り除かれる。
-
例 \(2\) : \((25)_{10} - (14)_{10}\) を \(8\) ビットの \(2\) 進数で考える。
\[ {\small 25 = (00011001)_{2} } \]\[ {\small 14 = (00001110)_{2} } \]\(14\) の \(2\) の補数は \((11110010)_{2}\) となる。
\[ {\small (00011001)_{2} + (11110010)_{2} = (100001011)_{2} } \]\(8\) ビットの範囲で見るため、\(9\) ビット目に桁上がりした先頭の \(1\) を捨てる。
\[ {\small (00001011)_{2} = (11)_{10} } \]同じ計算を \(10\) 進数で確かめる。
\[ {\small 25 + (256 - 14) = 256 + 11 = 267 } \]下位 \(8\) ビットを残すことは、\(2^8 = 256\) で割った余りを求めることに相当する。そのため、余分な \(256\) が取り除かれ、差の \(11\) が残る。
-
負の結果の読み方と、桁上がりとの区別
\(8\) ビットの \(2\) の補数表現では、整数を \(-128\) から \(127\) まで表せる。最上位ビットが \(0\) なら符号なし整数と同じ値、\(1\) なら符号なし整数として読んだ値から \(256\) を引いた値として解釈する。例えば、逆向きの \(14 - 25\) は、\(25\) の補数 \(256 - 25 = 231\) を使って \(14 + 231 = 245\) となる。保存されるビット列は \(11110101\) で、符号付きの値は \(245 - 256 = -11\) となる。
この場合、\(9\) ビット目への桁上がりはないが、同じ加算の仕組みで負の差を表せる。一方、\(127 + 1\) の結果 \(128\) は、この符号付きの範囲を超える。下位 \(8\) ビットの \(10000000\) を同じ規則で読むと \(-128\) となり、数学的な和を表せない。
これが符号付き整数のオーバーフローであり、最上位からの桁上がりの有無とは別に確認する必要がある。
-
小数表現
-
固定小数点数表現
小数点の位置を固定して数値を表す方式。
表せる範囲は限られるが、考え方は直感的で分かりやすい。 -
浮動小数点数表現
数値を仮数部と指数部に分けて表す方式。
固定小数点数より広い範囲の数値を扱える。例えば、\(5.2 \times 10^{-4}\) の場合、\(5.2\) が仮数部、\(-4\) が指数部にあたる。
ただし、仮数部の桁数にも限りがある。広い範囲の値を扱えることと、その範囲のすべての値を正確に表せることは異なる。
-
小数表現の正規化
正規化とは、仮数部と指数部の形を一定のルールにそろえることを指す。
代表的には、仮数部を \(1 \leq |m| < r\) にそろえる形式と、\(1/r \leq |m| < 1\) にそろえる形式がある。どの形を正規化とするかは、問題文の条件や浮動小数点形式によって異なる。-
例 \(1\) : \((0.00052)_{10}\) を正規化する。
\[ {\small (0.00052)_{10} = 5.2 \times 10^{-4} } \]この場合、\(5.2\) が仮数部、\(-4\) が指数部となる。
\[ {\small (0.00052)_{10} = 0.52 \times 10^{-3} } \]このような表し方もできるため、このテーマでは「仮数部をどの範囲に収めるか」という条件を確認する必要がある。
-
例 \(2\) : \((0.011)_{2}\) を正規化する。
\[ {\small (0.011)_{2} = (1.1)_{2} \times 2^{-2} } \]\[ {\small (0.011)_{2} = (0.11)_{2} \times 2^{-1} } \]どちらも値は同じだが、正規化の形式は条件によって変わる。
-
基数変換の誤差
-
小数の基数変換による誤差
\(10\) 進数では有限小数として表せる値でも、\(2\) 進数では循環小数になる場合がある。
コンピュータは多くの場合、浮動小数点数を \(2\) 進数で扱うため、期待した計算結果とわずかにずれることがある。-
例 : \((0.4)_{10}\) の基数を \(2\) に変換。
小数部に \(2\) を掛け、整数部を順に取り出す。
\(0.4 \times 2 = 0.8\) → 整数部 \(0\)、残り \(0.8\)
\(0.8 \times 2 = 1.6\) → 整数部 \(1\)、残り \(0.6\)
\(0.6 \times 2 = 1.2\) → 整数部 \(1\)、残り \(0.2\)
\(0.2 \times 2 = 0.4\) → 整数部 \(0\)、残り \(0.4\)残りの小数部が最初の \(0.4\) に戻るため、同じ手順が繰り返される。取り出す数字も \(0110\) の繰り返しになる。
\[ {\small (0.4)_{10} = (0.01100110011001100110\ldots)_{2} } \]\[ {\small = (0.\overline{0110})_{2} } \]無限に続く表現自体は元の \(0.4\) と等しい。誤差が生じるのは、保存できる有限の桁数に合わせて丸めるときである。
-
-
有限小数になるかを分母で判定
\(0.75 = 3/4\) の分母は \(4 = 2^2\) なので、\(2\) 進数の小数点以下 \(2\) 桁で表せる。一方、\(0.4 = 2/5\) の分母には \(5\) が残る。\(2\) 進数で小数点以下を \(n\) 桁まで使った数は、整数を \(2^n\) で割った形に書ける。そのため、約分後の分母に含まれる素因数は \(2\) だけになる。
逆に、約分後の分母が \(2\) のべき乗なら、その桁数までの有限小数で表せる。\(2/5\) はこの条件を満たさないため、\(2\) 進数では有限小数にならない。この判定は有限の \(2\) 進小数として表せるかを調べるものであり、特定の浮動小数点形式に収まるかは、仮数部の桁数と指数の範囲も確認する必要がある。
数値演算の誤差
-
丸め誤差
指定された桁数で数値を扱うために、四捨五入、切捨て、切上げなどで下位の桁を削ることによって生じる誤差。 -
桁落ち
ほぼ等しい値同士を引き算すると、上位の桁が相殺され、結果の有効な桁数が減る現象。
入力値に丸め誤差が含まれる場合、その誤差が小さな差に対して相対的に大きく影響する。-
例 : 各平方根を有効数字 \(7\) 桁に丸めて、\(\sqrt{999} - \sqrt{997}\) を計算。
ここでは、平方根と各演算の結果を \(10\) 進の有効数字 \(7\) 桁で四捨五入するものとする。実際の \(2\) 進浮動小数点形式とは桁数や丸め方を区別した、比較用の計算である。
\[ {\small \sqrt{999} \fallingdotseq 31.60696125 } \]\[ {\small \sqrt{997} \fallingdotseq 31.57530680 } \]これらを丸めて計算すると、丸め誤差を含んだ値同士を引くことになる。
\[ {\small 31.60696 - 31.57531 = 0.03165 } \]この引き算自体は、丸めた \(2\) 数の差を正確に求めている。しかし、平方根を丸めたときの誤差が残り、小さな差の精度に影響する。
-
近い値の引き算を避ける変形
\(\sqrt{999} + \sqrt{997}\) は \(0\) ではないので、この値をそれ自身で割った比は \(1\) になる。元の式にその比を掛けても値は変わらない。\[ {\small \sqrt{999} - \sqrt{997} = \frac{(\sqrt{999} - \sqrt{997})(\sqrt{999} + \sqrt{997})}{\sqrt{999} + \sqrt{997}} } \]\[ {\small = \frac{999 - 997}{\sqrt{999} + \sqrt{997}} = \frac{2}{\sqrt{999} + \sqrt{997}} } \]同じ有効数字 \(7\) 桁の条件で分母を計算する。
\[ {\small 31.60696 + 31.57531 = 63.18227 } \]\(2 \div 63.18227\) を丸めた結果は \(0.03165445\) となる。
計算方法 結果 平方根同士を直接引く（有効数字 \(7\) 桁） \(0.03165\) 式を変形して計算（有効数字 \(7\) 桁） \(0.03165445\) 高精度で計算した参考値 \(0.031654450864\ldots\) 変形後は、丸めた平方根同士の引き算を避けられるため、この例では誤差の影響が小さくなる。式が数学的に等しくても、有限桁での計算結果は計算の順序によって変わり得る。
-
-
情報落ち
極端に大きい数値と小さい数値を加算したとき、小さい数値が有効桁数の範囲に収まらず、結果に反映されないことを指す。-
例 : 有効桁数 \(6\) 桁で \((256.789)_{10} + (0.00011)_{10}\) を計算。
\[ {\small 256.789 + 0.00011 = 256.78911 } \]ただし、有効桁数 \(6\) 桁では \(256.789\) までしか保持できないため、\(0.00011\) の影響が消える。
\(0.00011\) 自体は有効数字 \(2\) 桁で表せる。単独で表せないほど小さいのではなく、大きい値と足し合わせた結果にその桁が残らない点が情報落ちの特徴となる。
-
-
打切り誤差
無限級数や繰り返し計算を、有限回で打ち切ることによって発生する誤差。 -
オーバーフロー
演算結果が、データ形式で表現できる数値の範囲を超えてしまう状態。 -
アンダーフロー
演算結果の絶対値が非常に小さくなり、正規化数として表現できる最小値を下回る状態。
IEEE 754 では、直ちに \(0\) になるとは限らず、サブノーマル数（非正規化数）として表現される場合がある。
集合
要素が集合に属するかどうかを命題として見ると、集合演算と論理演算の対応を整理しやすい。
ここでは、全体集合を \(U = \{1, 2, 3, 4, 5, 6\}\)、その部分集合を \(A = \{1, 2, 3\}\)、\(B = \{3, 4\}\) とする。以下では \(x \in U\) を前提に集合記号と対応する論理条件を示す。
-
和集合
少なくともどちらか一方に含まれる要素の集合。
集合記号：\(A \cup B\)
\(x \in A \cup B\) は、\(x \in A\) または \(x \in B\)（OR）に対応。 -
積集合
両方に共通して含まれる要素の集合。
集合記号：\(A \cap B\)
\(x \in A \cap B\) は、\(x \in A\) かつ \(x \in B\)（AND）に対応。 -
補集合
全体集合 \(U\) のうち、集合 \(A\) に含まれない要素の集合。
集合記号：\(A^c = U \setminus A\)
\(x \in A^c\) は、\(x \in A\) ではないこと（NOT）に対応。 -
差集合
集合 \(A\) から、集合 \(B\) に含まれる要素を取り除いた集合。
集合記号：\(A \setminus B\)
\(x \in A \setminus B\) は、\(x \in A\) かつ \(x \notin B\) に対応。 -
対称差集合
どちらか一方にだけ含まれる要素の集合。
集合記号：\(A \triangle B\)
\(x \in A \triangle B\) は、\(x\) がどちらか一方だけに属すること（XOR）に対応。
上の \(A\)、\(B\)、\(U\) に各演算を適用すると結果は次のようになる。
| 演算 | 結果 | 要素の選び方 |
|---|---|---|
| 和集合 \(A \cup B\) | \(\{1, 2, 3, 4\}\) | どちらかに含まれる要素を集め、重複は数えない |
| 積集合 \(A \cap B\) | \(\{3\}\) | 両方に含まれる要素だけを残す |
| 補集合 \(A^c\) | \(\{4, 5, 6\}\) | \(U\) から \(A\) の要素を除く |
| 差集合 \(A \setminus B\) | \(\{1, 2\}\) | \(A\) から、\(B\) にも含まれる \(3\) を除く |
| 対称差集合 \(A \triangle B\) | \(\{1, 2, 4\}\) | 両方に含まれる \(3\) を除き、片方だけの要素を集める |
例えば \(x = 3\) は両方に含まれるため、OR と AND は真、XOR は偽となる。\(x = 1\) は \(A\) だけに含まれるため、OR と XOR は真、AND は偽となる。
OR の「または」は両方に含まれる場合も含み、XOR は含まない。また、差集合は順序によって変わり、\(B \setminus A = \{4\}\) となる。補集合は、どの集合を全体集合 \(U\) とするかによって変わる。
まとめ
- 基数変換では、整数部は下位の桁から、小数部は小数点に近い桁から求まる。各桁の重みを使って元の値に戻すと検算できる。
- 補数は、決められた桁数で減算を加算に置き換える仕組み。桁上がりを捨てる操作と符号付き整数の範囲を超えるオーバーフローは区別する。
- 固定小数点数は小数点の位置を固定し、浮動小数点数は仮数部と指数部に分けて表す。正規化では、その表現を一定の形式にそろえる。
- 小数を有限桁に丸めると誤差が生じることがある。近い値の減算では入力値の誤差が目立つため、同値な式への変形で影響を軽減できる場合がある。
- 情報落ちは小さい値が演算結果へ反映されない現象、アンダーフローは結果の絶対値が正規化数の範囲の下限を下回る現象。
- 集合演算は要素が条件を満たすかで判断できる。OR は両方に含まれる要素も含み、XOR は片方だけに含まれる要素を選ぶ。