概要

情報技術の基礎として理解しておきたい離散数学のうち、基数変換、補数表現、小数表現、数値誤差、集合演算を整理する。

離散数学は、計算機が数値や論理をどのように扱うかを理解するための土台となる。
特に、\(2\) 進数、補数、浮動小数点数の誤差は、計算問題だけでなくプログラムの挙動を理解するうえでも重要となる。

この記事で扱うこと

• \(10\) 進数、\(2\) 進数、\(16\) 進数の基本的な基数変換。
• 補数を使って負の数や減算を扱う考え方。
• 固定小数点数、浮動小数点数、正規化の違い。
• 丸め誤差、桁落ち、情報落ちなどの数値誤差。
• 和集合、積集合、補集合、差集合、対称差集合の意味。

理解しておきたい要点

基数変換

基数変換とは、ある基数で表された数を、別の基数の表現へ変換することを指す。
基数は、桁上がりする基準となる数で、\(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}\)

• 例 \(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}\)

• 例 \(3\) : 小数の基数変換 \(10\) → \(2\)

  \((0.75)_{10}\) の基数を \(2\) に変換する。
  小数部の変換では、小数部分に変換先の基数を掛け、得られた整数部を上から順に読む。

  \(0.75 \times 2 = 1.50\) → 整数部 \(1\)
  \(0.50 \times 2 = 1.00\) → 整数部 \(1\)
  → 得られた整数部を上から順に並べて \((0.11)_{2}\)

• 例 \(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} } \]

補数表現（負の数の表現）

• 補数表現
  補数とは、決められた基数と桁数の範囲で、対象の数に加えると桁上がりする最小の数を指す。

  \(n\) 桁の \(r\) 進数で数 \(x\) を考える場合、補数は次のように表せる。

  \[ {\small r^{n} - x } \]

  • 例 \(1\) : \(2\) 桁の \(10\) 進数 \((55)_{10}\) の補数。

    \[ {\small 10^{2} - 55 = 45 } \]

  • 例 \(2\) : \(8\) 桁の \(2\) 進数 \((00001101)_{2}\) の補数。

    \(2\) 進数では、全ビットを反転して \(1\) を加えると \(2\) の補数になる。

    \[ {\small 00001101 \rightarrow 11110010 \rightarrow 11110011 } \]

• 補数表現するメリット
  補数を使うと、減算を加算として扱える。
  コンピュータ内部では、引き算専用の仕組みを用意するより、補数を使って加算として扱う方が都合がよい。

  • 例 \(1\) : \((25)_{10} - (13)_{10}\) を \(2\) 桁の \(10\) 進数で考える。

    \[ {\small 25 - 13 = 25 + (-13) } \]

    \(-13\) を \(2\) 桁の \(10\) 進数の補数で表すと、\(100 - 13 = 87\) となる。

    \[ {\small 25 + 87 = 112 } \]

    \(2\) 桁の範囲で見るため、上位の桁上がりを捨てると \(12\) となる。

  • 例 \(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\) ビットの範囲で見るため、桁あふれした先頭の \(1\) を捨てる。

    \[ {\small (00001011)_{2} = (11)_{10} } \]

小数表現

• 固定小数点数表現
  小数点の位置を固定して数値を表す方式。
  表せる範囲は限られるが、考え方は直感的で分かりやすい。

• 浮動小数点数表現
  数値を仮数部と指数部に分けて表す方式。
  固定小数点数より広い範囲の数値を扱える。

  例えば、\(5.2 \times 10^{-4}\) の場合、\(5.2\) が仮数部、\(-4\) が指数部にあたる。

• 小数表現の正規化
  正規化とは、仮数部と指数部の形を一定のルールにそろえることを指す。
  どの形を正規化とするかは、問題文の条件や浮動小数点形式によって異なる。

  • 例 \(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\) に変換する。

    \[ {\small (0.4)_{10} = (0.01100110011001100110\ldots)_{2} } \]
    \[ {\small = (0.\dot{0110})_{2} } \]

    \(0.4\) は \(2\) 進数では有限桁で表せないため、途中で丸めると誤差が発生する。

数値演算の誤差

• 丸め誤差
  指定された桁数で数値を扱うために、四捨五入、切捨て、切上げなどで下位の桁を削ることによって生じる誤差。

• 桁落ち
  ほぼ等しい値同士を引き算したとき、有効桁数が大きく減ってしまうことで生じる誤差。

  • 例 : 有効桁数が小数点以下 \(7\) 桁となる条件下で \(\sqrt{999} - \sqrt{997}\) を計算する。

    \[ {\small \sqrt{999} \fallingdotseq 31.60696125 } \]
    \[ {\small \sqrt{997} \fallingdotseq 31.57530680 } \]

    これらを丸めて計算すると、丸め誤差を含んだ値同士を引くことになる。

    \[ {\small 31.60696 - 31.57531 = 0.03165 } \]

    近い値同士の差を取るため、有効な桁が減り、桁落ちが発生する。

• 情報落ち
  極端に大きい数値と小さい数値を加算したとき、小さい数値が有効桁数の範囲に収まらず、結果に反映されないことを指す。

  • 例 : 有効桁数 \(6\) 桁で \((256.789)_{10} + (0.00011)_{10}\) を計算する。

    \[ {\small 256.789 + 0.00011 = 256.78911 } \]

    ただし、有効桁数 \(6\) 桁では \(256.789\) までしか保持できないため、\(0.00011\) の影響が消える。

• 打切り誤差
  無限級数や繰り返し計算を、有限回で打ち切ることによって発生する誤差。

• オーバーフロー
  演算結果が、あらかじめ用意された表現範囲の上限を超えてしまう状態。

• アンダーフロー
  演算結果が小さくなりすぎて、浮動小数点数で表現できる下限を下回ってしまう状態。

集合

集合演算は、論理演算と対応させると理解しやすい。
この分野では、集合記号と論理演算の対応を整理しておきたい。

• 和集合
  少なくともどちらか一方に含まれる要素の集合。
  論理演算では OR に対応する。
  表現記号：\(OR\)、\(+\)、\(\cup\)、\(∨\)

• 積集合
  両方に共通して含まれる要素の集合。
  論理演算では AND に対応する。
  表現記号：\(AND\)、\(・\)、\(\cap\)、\(∧\)

• 補集合
  ある集合に含まれない要素の集合。
  論理演算では NOT に対応する。
  表現記号：\(NOT\)、\(\overline{A}\)

• 差集合
  ある集合から、別の集合に含まれる要素を取り除いた集合。
  表現記号：\(-\)

• 対称差集合
  どちらか一方にだけ含まれる要素の集合。
  論理演算では XOR に対応する。
  表現記号：\(XOR\)、\(⊕\)、\(△\)

違いを整理する

実務とのつながり

• 基数変換
  IPアドレス、文字コード、ビット演算、ファイル形式の理解で必要になる。

• 補数表現
  整数型の負数表現や、オーバーフローの挙動を理解する手がかりになる。

• 小数表現と誤差
  金額計算、統計処理、機械学習などで、浮動小数点数の丸め誤差を意識する必要がある。

• 集合演算
  データ抽出条件、検索条件、SQL の集合演算や論理条件の理解につながる。

まとめ

• 基数変換では、整数部は割り算の余り、小数部は掛け算の整数部を使って変換する。
• 補数表現を使うと、負の数や減算を加算として扱える。
• 浮動小数点数は広い範囲を扱える一方で、丸め誤差や桁落ちなどに注意が必要となる。
• 集合演算は、OR、AND、NOT、XOR などの論理演算と対応して理解すると整理しやすい。

参考文献

• 瀬戸 美月（\(2020\)）『徹底攻略 応用情報技術者教科書』株式会社インプレス