コンピューターは数値をどう表現しているのか (1) でコンピューターにおける算術演算を解説したので,本記事では関連した練習問題を取り扱います
基本問題
Problem 1
\(a\) を正の整数とし, \(b = a^2\) とする. \(a\) の2進数で表したとき,\(n\) bitであるとすると,このときの \(b\) は何 bitか?
符号なし整数の減算
Problem 2
符号なし整数として \(5\text{ED}4_{(16)} - 07\text{A}4_{(16)}\) を計算し,答えを16進数・2進数・10進数で示せ.
Problem 3
符号なし整数として \(4365_{(8)} - 3412_{(8)}\) を計算し,答えを8進数・2進数・10進数で示せ.
符号付き整数の減算
符号付き整数の減算 \(A - B\) は,\(A + (-B)\) に置き換えて加算で計算します.\(-B\) の作り方と,最上位からあふれた桁上げの扱いが方式によって異なります.
| 方式 | \(-B\) の作り方 | 最上位からの桁上げ |
|---|---|---|
| 2の補数 | 全ビットを反転して \(+1\) | 捨てる |
| 1の補数 | 全ビットを反転するだけ | 最下位に足し戻す(循環桁上げ) |
2の補数による減算
Problem 4
16ビットの2の補数表現で \(5\text{ED}4_{(16)} - 07\text{A}4_{(16)}\) を計算せよ.計算の過程を2進数で示し,答えを16進数・10進数でも示せ.
Problem 5
16ビットの2の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数で示し,答えを8進数・10進数でも示せ.
1の補数による減算
Problem 6
16ビットの1の補数表現で \(5\text{ED}4_{(16)} - 07\text{A}4_{(16)}\) を計算せよ.計算の過程を2進数で示し,答えを16進数・10進数でも示せ.
Problem 7
16ビットの1の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数で示し,答えを8進数・10進数でも示せ.
オーバーフローとアンダーフロー
ここまでの問題では,結果が表せる範囲に収まっていました.この節では,ビット幅を小さくしたときに結果が範囲からはみ出すかどうかを調べます.
Definition 1 整数演算のオーバーフローとアンダーフロー
- 演算の正しい結果が,\(n\) ビットで表せる範囲の上限を超えることを オーバーフロー という
- 演算の正しい結果が,\(n\) ビットで表せる範囲の下限を下回ることを,整数の文脈では アンダーフロー(負のオーバーフロー)と呼ぶことがある
- 表せる範囲は,符号なし整数なら \(0\) 〜 \(2^n - 1\),2の補数表現なら \(-2^{n-1}\) 〜 \(2^{n-1} - 1\),1の補数表現なら \(-(2^{n-1} - 1)\) 〜 \(2^{n-1} - 1\) とする
加算器での検出方法
減算 \(A - B\) を \(A + (\bar{B} + 1)\) として加算器で計算するとき,はみ出しは次のように検出できます.
- 符号なし:最上位から桁上げが出ないとき,借りが生じている.つまり \(A < B\) で,結果は下限 \(0\) を下回る(アンダーフロー)
- 符号付き:「正 − 負 = 負」または「負 − 正 = 正」と符号が変わったとき,範囲をはみ出している.回路の上では,符号ビットへの桁上げ入力と,符号ビットからの桁上げ出力が一致しないことで検出する
Problem 8
12ビットの符号なし整数として \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数でも示し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ.
Problem 9
\(4365_{(8)}\) と \(3412_{(8)}\) を,12ビットの符号付き整数とみなす.このとき,
- 2の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
- 1の補数表現で \(4365_{(8)} - 3412_{(8)}\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
Problem 10
12ビットの2の補数 \(4365_{(8)}\),\(3412_{(8)}\) が,16ビットに符号拡張した形式で格納されている.このとき \(4365_{(8)} - 3412_{(8)}\) を計算せよ.計算の過程を2進数で示し,答えを10進数でも示せ.
Problem 11
10進数の \(185\) と \(122\) について,
- 8ビットの符号なし整数として \(185 - 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
- 8ビットの符号付き整数(2の補数表現)として \(185 - 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
Problem 12
10進数の \(185\) と \(122\) について,
- 8ビットの符号なし整数として \(185 + 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
- 8ビットの符号付き整数(2の補数表現)として \(185 + 122\) を計算し,オーバーフロー・アンダーフローが発生するかを理由とともに答えよ
論理演算
Problem 13
\(m\) を正の整数とする.次の2つが同値であることを示せ.
- すべての非負整数 \(x\) に対して \(x \mathbin{\mathrm{AND}} (m-1) = x \bmod m\)
- \(m\) は 2 のべき乗である(ある整数 \(k \ge 0\) で \(m = 2^k\))