Web Analytics Made Easy - StatCounter

工業大学生ももやまのうさぎ塾

うさぎでもわかるをモットーに大学レベルの数学・情報科目をわかりやすく解説!

計算機システム1総復習 Part01 データ表現編(主に2進数の練習問題)

こんにちは、ももやまです。

今回は計算機の基礎について理解できているか、2進数を中心とした模擬問題を行基本変形サークルさん [ @kit_matrix ] さんに許可をいただき、こちらのサイトで解説を作成しました。ありがとうございます…!

急いで解答・解説を打ち込んだのでミスがあるかもしれません。
その際にはコメントなどでお知らせいただけたらありがたいです!

 

 

問題と解説、配点(私が独自に設定・100点満点)を載せています。

ぜひ1回自分で解いてから解説を見ることをおすすめします。

第1問.2進数→10進数の変換

つぎの2進数を10進数に変換しなさい。

なお、可読性のため3桁ごとに微妙な隙間を入れているが、特に気にする必要はない。気にしたら負けだ。
(配点   8)

(1) 11 111 100 011b
(2) 1011.0101b

 

☆解説☆

10進数→2進数の変換問題です。

それぞれの桁が2の何乗になるかを意識してときましょう。

(1) [4点]

解答:2019

f:id:momoyama1192:20190702190942g:plain

\[ \begin{align*} &
2^{10} + 2^{9} + 2^8 + 2^7 + 2^6 + 2^5 + 2^1 + 2^0 \\ = &
1024 + 512 + 256 + 128 + 64 + 32 + 2 + 1 = 2019
\end{align*} \]

(2) [4点]

解答:11.3125

f:id:momoyama1192:20190702190946g:plain

\[ \begin{align*} &
2^3 + 2^1 + 2^0 + 2^{-2} + 2^{-4} \\ = &
8 + 2 + 1 + \frac{1}{4} + \frac{1}{16} \\ = & 11 + \frac{5}{16} = 11.3125
\end{align*} \]

 

第2問.10進数→2進数の変換

つぎの10進数を2進数に変換しなさい。
なお、循環小数となる場合は、 0.\dot{0}01\dot{1} のように書くこと。
(配点   8)

(1) 52 
(2) 4.8 

 

☆解説☆

2進数→10進数の変換問題です。

計算後に2進数→10進数に再び直して合っているか確認することをおすすめします。

(1) [4点]

解答:110 100b

計算過程を載せておきます。

f:id:momoyama1192:20190702190950g:plain

(2) [4点]

解答: 100.\dot{1}10\dot{0}_b 

整数部と小数部を分けて計算し、最後に足すのがよい。
整数部は4なので、2進数にすると100bとなる。

 

小数部は、つぎのような筆算をすると、1100で無限ループすることがわかる。

f:id:momoyama1192:20190702190954g:plain

よって、答えは  100.\dot{1}10\dot{0}_b となる。

 

 

第3問.2進数の演算

つぎの演算の結果を求めなさい。
ただし、2進数同士の計算の結果は2進数で、16進数同士の計算の結果は16進数で記すこと。
(配点  15)

(1) 111 101 010 111b + 11 110 010 110b
(2)  10 000 100 011b × 10 111b 
(3) ABh + CDh

 

☆解説☆

筆算をして求めればよい。
繰り上げの計算で特に間違えやすいので気をつけましょう。

(1) [5点]

解答:1 011 011 101 101b

10進数だと:3927 + 1942 = 5869 相当の計算

f:id:momoyama1192:20190702190958g:plain

(2) [5点]

解答:101 111 100 100 101b

10進数だと:1059 × 23 = 24357 相当の計算

f:id:momoyama1192:20190702191002g:plain

別解 ちょっと賢いかもしれないやり方

10 000 100 011b × (11 000b - 1b) として計算
10 000 100 011b × 11 000b - 10 000 100 011b ×1b の計算となる 

 

10 000 100 011b × 11 000b の計算部分

f:id:momoyama1192:20190702191006g:plain

 

乗算結果から 10 000 100 011b を引く部分

f:id:momoyama1192:20190702191011g:plain

(3) [5点]

解答:178h

10進数だと:171 + 205 = 376 相当の計

f:id:momoyama1192:20190702191015g:plain

 

ここまでの計算方法などはこちらのサイトにまとめているので、もしわからなければこちらをご覧ください。

www.momoyama-usagi.com

 

第4問.2の補数表現の足し算

つぎの計算を4bitの2の補数表現で行う過程を示し、結果を10進数で答えなさい。
(配点  16)

(1)  5 + 7
(2) -5 + 7 
(3)  5 -  7
(4) -5 - 7

 

☆解説☆

それぞれ各4点、合計16点。
4点の配分は、2進数の計算結果に2点、10進数に直す部分に2点。

それぞれを4bitの2の補数で計算し、計算後に10進数に戻す操作をすればよい。
-8~7までの4bitの2の補数表現をすべて書き出し、解くのも手。

2進 10進 2進 10進
0000 0 1000 -8
0001 1 1001 -7
0010 2 1010 -6
0011 3 1011 -5
0100 4 1100 -4
0101 5 1101 -3
0110 6 1110 -2
0111 7 1111 -1

0111 までは1ずつ増えていき、1000で-8になって、また1ずつ増えていくことを考えたら書くのはそこまで大変ではないかも…?

f:id:momoyama1192:20190702191539g:plainとなる。

 

2の補数などについてイマイチ理解できていないなと思った方は、こちらのサイトをご覧ください。

www.momoyama-usagi.com

第5問.固定小数点表記・浮動小数点表記

10進法で -0.7 と表される数を8桁(8ビット)の2進数で表現することを考える。このとき、以下の文章の空欄にあてはまる語句や数値をそれぞれ答えなさい。
(配点  24)

 

(1) まず、最下位ビットから4桁を小数部、その上位3桁を整数部としてそれぞれ絶対値表現し、最上位ビット(MSB)を符号部(正は0、負は1)とする固定小数点表記で表現することを考える。ただし、小数第5位以降は切り捨てる。このとき、符号部は2進数で【 あ 】、整数部は2進数で【 い 】、小数部は2進数で【 う 】となる。また、これによって表される実際の数値 -0.7 との誤差を10進数で表現すると【 え 】となる。

 

(2) つぎに、最下位ビットから2桁を指数部(2の補数表現)、その上位3桁を仮数部(ケチ表現+絶対値表現)、最上位ビット(MSB)を符号部(正は0、負は1)とする浮動小数点表記で表すことを考える。ただし、仮数部は表現できない部分を切り捨てる。このとき、符号部は2進数で【 お 】、仮数部は2進数で【 か 】、指数部は2進数で【 き 】となる。また、これによって表される数と実際の数値 -0.7 との誤差を10進数で計算すると【 く 】となる。

(ケチ表現 → 1.XXX の 1 を省略)

 

(3) このように、数値の切り捨てなどによって生じる誤差を【 け 】という。

 

 

☆解答☆

あ:1 [2点]
い:000 [3点]
う:1011 [3点]
え:0.0125 (1/80) [3点]
お:1 [2点]
か:011 [3点]
き:11 [3点]
く:0.0125 (1/80) [3点]
け:丸め誤差 [3点]

 

まずは、0.7を2進数になおしておく。\[ 0.7 = 2^{-1} + 2^{-3} + 2^{-4} + 2^{-5} + \cdots \] となる。

 

f:id:momoyama1192:20190702203503g:plain

(1)

固定小数点表記で-0.7を表す方法についての問題。

符号部:-0.7は負なので1。
整数部:10進数で0なので2進数だと3桁で000。
小数部:0.7を小数第4位まで2進数表記すればよい。計算の結果、0.1011なので小数部は1011となる。

0.1011を10進数に戻すと、\[ \frac{1}{2} + \frac{1}{8} + \frac{1}{16} = \frac{11}{16} \]となる。よって、誤差は\[ \frac{7}{10} - \frac{11}{16}  = \frac{56}{80} - \frac{55}{80} = \frac{1}{80} = 0.0125 \]

となり、誤差は0.0125となる。

(2)

浮動小数点表記で-0.7を表す方法についての問題。

符号部:-0.7は負なので1。

仮数部と指数部を計算する前に、0.7を指数表記(1.XXX × 2のべき乗に正規化)する。

\[ 0.7 = 2^{-1} + 2^{-3} + 2^{-4} + 2^{-5} = 2^{-1} (2^0 +  2^{-2} + 2^{-3} + 2^{-4} )\]となる。

すると、 1.011_b \times 2^{-1} と表される。

仮数部:1.011bのケチ表現なので011
指数部:-1を2桁の2の補数で表すと11

 

 1.011_b \times 2^{-1} を10進数に戻すと、\[ 2^{-1} (2^0 +  2^{-2} + 2^{-3}) = \frac{1}{2} + \frac{1}{8} + \frac{1}{16} = \frac{11}{16}\]となる。よって誤差は \[ \frac{7}{10} - \frac{11}{16} = \frac{1}{80} \]より誤差は0.0125となる。

同じ誤差でも浮動小数点のほうがより少ない桁数で表現できるでしょ!!

 

(3)

このような誤差のことを丸め誤差といいます。
なお、この誤差は浮動小数点表記でも固定小数点表記でも両方発生します。

 

苦手だった人はこちらで復習をしましょう。

www.momoyama-usagi.com

 

第6問.正誤問題

つぎの①~⑧の文章がそれぞれ正しければ○、誤っていれば×を答えなさい。
(配点  16)

 

① D/A 変換の D,A とはそれぞれデジタル、アナログのことを指す。

② 浮動小数点表現では、数直線上において表現できる小数の密度は均一である。

③ 一般に、画像や音は離散化(標本化・量子化)してから符号化する。

④ データ転送中に誤りを訂正できるような符号化の実現は不可能である。

⑤ ある漢字(例えば行列の「行」)を表す2進数は、文字コードごとに異なる可能性がある。

⑥ ASCIIコードとは、制御文字・大小英字・その他記号を含む7bitの文字コードである。

⑦ -5 を2の補数表現を用いて2進数で表現する場合、最低でも3bit必要である

⑧ n bitの2の補数表現を用いると、同じ数であっても複数の表し方で表現できるような数が存在する。

 

解説 [2点× 8 = 16点]

① 解答:○

Digital / Analog 変換の頭文字を取って D/A 変換と呼ばれます。

 

② 解答:×

浮動小数点は 1.XXX × 2のべき乗 で表現する小数点でしたね。
この場合、2のべき乗部分が大きくなればなるほど低密度でしか表されなくなります。なので、表現できる小数の密度は均一ではありません(均一なのは固定小数点表現です。)。

 

③ 解答:○

文章そのままですね。

画像や音のデータは、一旦0,1のデータに離散化してから、符号化(圧縮)を行います。

圧縮された画像としては、jpegなどが、圧縮された音声としては mp3 などがあります。

 

④ 解答:×

ちゃんとあります。(これ×にしたらこの研究してる人に怒られそうですね() )

大学の情報理論などで詳しく習うと思うので興味ある人は調べてみてください。

 

⑤ 解答:○

例えば、UnicodeやShift JISなどで異なります。
そのため、文字化けの原因となっています。

 

⑥ 解答:○

制御文字・大小英字(大文字小文字合わせて52個)・その他記号でだいたい128個に収まりそうですよね。

また、C言語などのchar型は、文字に変換する際にASCIIコードが使われています。

char型は1バイト(8bit)で、この整数部分だけが使われていると覚えれば7bitであることがわかりますね。

 

⑦ 解答:×

(絶対値の)5を2進数に直すと101である。2の補数にすると011となる。これに符号部を足すため、最低4ビット必要。

よって×。

 

別解

3ビットの2の補数表現で表される数  x の範囲は  -4 \leqq x \leqq 3 である。

しかし5は範囲に入っていないため×となる。

 

⑧ 解答:×

2の補数を用いた場合は、それぞれの2進数に対応する10進数は必ず1つしかない。

絶対値+符号の方法で2進数を表した場合は0が000…0と100…0の2パターン存在する。

 

第7問.総括問題

次の問いに答えなさい。
(配点  13)

(1)  n bitの2の補数表現で表せる数の範囲を答えなさい。

(2) 一般に、浮動小数点で正の数の総和を取るときは、大きい数から足していくべきか、小さい数から足していくべきか、それとも明確な順序関係は存在しないか。

この中から該当するものを1つ選び、理由とともに答えなさい。

 

(3) 先日の行基本変形サークルが実施した「線形代数1 本番レベル模試」では、95人の受験者がいた。このテストは100点満点であり、0点から100点までの点数を取ったものが存在した。さてここで95人の本番レベル模試の得点の総和を求めたい。

このとき、各々の点数がどうであれ、正しく総和を求めるためには最低でも何ビットの2の補数表現で計算する必要があるか。また、そのビット数の2の補数表現ではあと何人増えても総和を正しく計算できるか。

 

☆解説☆

(1) [4点:下限値と上限値それぞれ2点ずつ]

解答: -2^{n-1} \sim 2^{n-1} - 1

正の数+0、負の数はそれぞれ半数ずつ存在する。なので、範囲は \[ -2^{n-1} \sim 2^{n-1} - 1\] となる(正の数は0を抜くことに注意)。

もちろん数を  x とおいて、  -2^{n-1} \leqq x \leqq 2^{n-1} - 1 と答えるのもOK。ただし、 \lt ではないので注意。

 

(2) [5点:選択肢に2点・理由に3点]

解答:小さい数から足していくべき

理由:大きい数から正の数の総和を足していくと、総和に対し、足されていく数が(総和に比べて)非常に小さくなるため、情報落ちが発生してしまう。一方小さい数から総和を足していくと、総和に対し、足されていく数は非常に小さくならないため、小さい数から足していくのがよい。

(ポイント:大きい数から加算すると情報落ちが起こることに触れていればOK、大きい数から足さると情報落ちが起こる理由について書いてなければ1点減点。)

 

ちなみに情報落ちは固定小数点表現では発生しません。参考までにどうぞ。
(桁落ちも固定小数点表現では発生しません。)

(3) [4点:2点×2]

解答:15bit必要、あと68人増えてもOK

(1) 点数が最大になる場合は全員が満点(100点)をとった場合。

そのときの合計点は  95 \times 100 = 9500 となる。

つぎに9500より大きくて、もっとも小さい  2^n n の値を考える。
 2^{13} = 8192 2^{14} = 16384 なので、\[2^{13}  \leqq 9500 < 2^{14}\] となる。よって  n = 14

今回は2の補数表現なので正負を表す1ビットが更に必要。

よって答えは最低15bit必要。

15ビットの場合、合計が16384未満であれば正しく総和が計算できる。
まずは、あと何点増えても(1)のbit数のままで計算ができるかを求める。

現在の想定される最大の合計点は9500なので、増えてもいい点数は  16383 - 9500 = 6884 と計算できる。

各個人の点数の最大値は100点なので、あと68人受験者が増えても(6800点プラス)必ず合計点が正しく計算できることがわかる。

 

情報落ちなどの誤差についてもしわからないことがあればこちらをご覧ください。
試験によく出ます。

www.momoyama-usagi.com

さいごに

今回は、計算機の基礎について理解できているかどうかの行基本変形サークルのチェックテスト(本番レベル模試)の解説を作成しました。

 

2進数や16進数の計算に慣れている人は少ないと思うので、計算ミスに注意しましょう。

桁落ち・情報落ち・丸め誤差などの誤差についても説明できるように…!

今回は桁落ちについての問題はなかったので桁落ちについては各自で調べておきましょう!