確認問題

以下にすらすら答えられる人は読まなくても大丈夫。
・10進数の0.375を2進数に直せ。
・10進数の0.375を浮動小数点の方式で表せ。このとき浮動小数点の全体は32bitで表し、仮数部を7bitで表すものとする。
・論理シフトの算術シフトの違いは何か。「～を考慮すること」という形式で答えよ。
・2進数の1-1100100を10進数に直せ。
・桁溢れ誤差、丸め誤差、打ち切り誤差、桁落ち、情報落ち、を全て説明せよ。
・ド・モルガンの法則を説明せよ。
・カルノー図法を説明せよ。

基数変換

0.375 を２進数に変換する際、整数になるまで２倍を繰り返す。
0.375→0.75→1.5→3 = 2進数で11 → 3回2をかけたので3つ位を戻して 0.011。

１の補数と２の補数

１の補数：和が桁の最大値となる数。１０進数で言うと9999 を作るイメージ
２の補数：和が桁の繰上りとなる数。１０進数で言うと10000 を作るイメージ
２の補数はその数に対する負の数となっている。

正規化と浮動小数点

正規化は最上位の数を０以外の値にすること。例えば0.002を0.2×10^-2 とするように。
浮動小数点とは、数値を指数部と仮数部に分けて表す方式。
例えば10進数の 0.375 = 2進数の 0.011 → 0.11 × 2^-1 と正規化して、仮数部の符号、指数部の値、仮数部の値に分割する。このとき仮数部は0.11を、指数部は2^-1を指す。
32bitの場合、それが1bit, 7bit, 24bit と分けたり、1bit, 8bit, 23bit と分けたりする。
0.11 × 10^-1 の場合、仮数部の符号は正(1)、指数部は-1 なので7bitの場合 1111111。仮数部の値は11 なので、24bitの場合は 11と0が22個つく。
つまり 0.375 = 0.11 × 10^-1 = [1 - 1111111 - 11000…] となる。

シフト演算

論理シフト

符号を考慮せずに行うシフト演算のこと。
２進数なので、×２は左に１bitズラし、÷２は右に１bitズラす。
このとき、桁あふれ(オーバーフロー)が起こるのは、
・bitで表せる最大数を超過する　例：1110(14)×２=1100（12）
・余りが出る　例：0011(3)÷２＝0001(1)

算術シフト

先頭を符号bitとして計算する手法。
例：1-1100100（-28）を４倍 ⇒ 1-0010000（-112）
　※先頭の符号と同じ数が溢れる場合はOK
例：1-1100100（-28）を÷４ ⇒ 1-1111001（-7）
　※先頭の符号と同じ数で埋める
算術シフトにおいて桁あふれ(オーバーフロー)が起こるのは、
・左シフトにて、先頭の符号と異なる数が溢れる
　→例：1-001（－７）×２＝1-010（ー６）
・余りが出る　例：1-001（ー７）÷２＝1-000（ー８）

補足：1-1100100 は１０進数でいくつか？
負の数の特徴は「絶対値と２の補数の関係にある」ことなので、２の補数を計算して、そこにマイナスをつけるのがよい。
２の補数＝１の補数＋１＝0-0011011 + 1 = 0-0011100＝16+8+4=28
そのため、1-1100100 はマイナス２８とわかる。

誤差

誤差のまとめ

誤差の起こる原因は大きく２つある。
　１，データ型で扱える範囲に限りがあること
　２，そもそも２進数で扱えない値であること（例：無限小数）
まず数値計算をする。計算を途中で打ち切れば「打ち切り誤差」。
計算の結果、絶対値が大きすぎる場合は桁溢れ（オーバーフロー）。
計算の結果、絶対値が小さすぎる場合は桁溢れ（アンダーフロー）。
計算は出来たが、データ型に入りきらない場合は「丸め誤差」。
計算は出来たが、有効桁数が減って信頼度が下がると「桁落ち」。
計算は出来たが、（数値同士の絶対値に大きな差があり）計算前と値が変わらない場合は「情報落ち」。

桁溢れ誤差

オーバーフローとアンダーフローがある。
オーバーフローとは、正負どちらかの方向に対して絶対値の最大値を超過すること。例えば８bitで正負の整数を表す場合、128以上もしくは-129 は表せない。
アンダーフローとは絶対値の最小値を下回り、浮動小数点のbit数で扱いきれない範囲の数となること。
0.0000…1 となったら「こんなもん０や！」となる。
つまり「そのデータ型では扱えない数値」を扱おうとした際の誤差。

丸め誤差

表現不可能な範囲について、四捨五入することで値が切り捨てられること。
0.1234567890123…となる値を0.1234 としたり。

打ち切り誤差

計算処理を途中で打ち切ることで発生する誤差。
無限小数が 1.33333…と続くのを「４桁目で終わりにしよ」など。

丸め誤差と打ち切り誤差の違い

計算が終わっていれば丸め誤差、計算が終わっていなければ打ち切り誤差。

桁落ち

絶対値がほぼ等しい数値の差を計算した場合に、有効な桁数が大きく減ることがある。
例：0.223×10^4 - 0.221×10^4 = 0.002×10^4 = 0.200 × 10^2
このとき「0.200」の右２桁は追加されたものであり信憑性に欠ける。

情報落ち

例えば 0.1111×10^4＋ 0.1111×10^-4＝0.111100001111×10^4
これを正規化すると 0.1111×10^4 となるので、足した値は無視されている。

論理演算、集合

必要最低限のキーワード（説明簡略）

・空集合
・和集合(OR)、差集合(ー)、積集合(AND)、補集合(not)、対称差集合(EOR, XOR)
・論理和(OR)、論理積(AND)、否定(NOT)、排他的論理和(EOR、XOR)
・ド・モルガンの法則：集合AおよびBのそれぞれの補集合について、ANDの否定形とOR、ORの否定形とANDが成り立つこと。

カルノー図法

複雑な論理式の共通項を探す手法。
例えば論理式「(notA・Ｂ)＋(Ａ・notＢ)＋(notＡ・notＢ)」は要するに「not(Ａ・Ｂ)」なのだが、これを視覚的に解決する。
論理式の３つの項を図に起こすと下記のようになる。

$$
\begin{array}{|c|c|c|} \hline
A｜B & 0 & 1 \\ \hline
0 & 1 & 1 \\ \hline
1 & 1 & 0 \\ \hline
\end{array}
$$

このとき、notＡ（Ａ＝０のとき）、notＢ（Ｂ＝０のとき）がすべて「１」となっていることに着目して、上記の３項からなる論理式を「notＡ＋notＢ」とすれば、論理式が簡潔になる。
応用版は下記のカルノー図。

$$
\begin{array}{|c|c|c|c|c|} \hline
AB｜CD & 00 & 01 & 11 & 10 \\ \hline
00 & 1 & 0 & 0 & 1 \\ \hline
01 & 0 & 1 & 1 & 0 \\ \hline
11 & 0 & 1 & 1 & 0 \\ \hline
10 & 0 & 0 & 0 & 0 \\ \hline
\end{array}
$$