del.dvi

「論理回路」ノート (2013 年度, c

関西学院大学 石浦 菜岐佐)

http://ist.ksc.kwansei.ac.jp/∼ishiura/lc/

1

数の表現法

♣ 2進数, 8 進数, 16 進数とその

相互変換

♣ 2 進数と

10

進数

の相互変換 ♣

符号付き

整数と

負の数

の表現法 (特に

2

の補数

表現)

1.1

2

進, 8 進, 16 進

10進数 (decimal) 119210= 1 × 103+ 1 × 102+ 9 × 101+ 2 × 100 (an−1an−2· · ·a1a0)10= n−1 X i=0

a

_i

_·

₁₀

i

8 進数 (octal) 7108= 7 × 82+ 1 × 81+ 0 × 80= 45610 (an−1an−2· · ·a1a0)8= n−1 X i=0

a

_i

_·

₈

i

2 進数 (binary) 11102= 1 × 23+ 1 × 22+ 1 × 21+ 0 × 20= 1410 (an−1an−2· · ·a1a0)2= n−1 X i=0

a

_i

_·

₂

i

2進数の 1 桁をビット (

bit

)と呼ぶ 16進数 (

hexadecimal

) 0, 1, 2, 3, 4, 5, 6, 7, 8, 9,

A

,

B

,

C

,

D

,

E

,

F

, 10, 11, 12, 13, · · · AE8616=

10

×

16

3

+

14

×

16

2

+ 8 ×

16

1

+ 6 ×

16

0

=

44678

₁₀ (an−1an−2· · ·a1a0)16= n−1 X i=0

a

_i

_·

₁₆

i

r進数 一般に (an−1an−2· · ·a1a0)r= n−1 X i=0

a

_i

_{· r}

i

この r を

基数

(

radix

)という

【性質 1.1】n ビットの (符号無し) 2 進数で表現できる数 x の範囲は次の通り. 範囲 n

0

≤x ≤ n z }| { 111111 · · · 112 (

2

n

−

1

) 4 0 ≤x ≤ 4 z }| { 11112 (

15

10) 8 0 ≤x ≤ 8 z }| { 111111112 (

255

10) 16 0 ≤x ≤ 16 z }| { 111111 · · · 112 (65, 53510) 32 0 ≤x ≤ 32 z }| { 111111 · · · 112 (4, 294, 967, 29510) 練習 1.1 空欄を埋めよ 10進数 2進数 8進数 16 進数 5

101

5

5

7

111

7

7

8

1000

10

8

13

1101

15

D 15

1111

17

F

16

10000

20

10

31

11111

37

1F

32

100000

40

20

1.2

2

進, 8 進, 16 進の相互変換

• 8 進数 8 = 23 _{より, 8 進数の 1 桁は 2 進数で}

3

_桁 25738=

010 101 111 011

₂= 101011110112 11011010011112=

1 101 101 001 111

₂=

15517

₈ • 16進数 16 = 24_{より, 16 進数の 1 桁は 2 進数で}

4

_桁 7A6D16=

0111 1010 0110 1101

₂= 1111010011011012 111011010011112=

11 1011 0100 1111

₂=

3B4F

₁₆ 10進/16 進 2 進 0 0000 1 0001 2 0010 3 0011 10進/16 進 2 進 4 0100 5 0101 6 0110 7 0111 10進 16 進 2 進 8 8 1000 9 9 1001 10 A 1010 11 B 1011 10進 16 進 2進 12 C 1100 13 D 1101 14 E 1110 15 F 1111 • 8 進表現や 16 進表現は,

数

の表現に限らず, ビット列 (0 と 1 の系列) をコンパクトに表すために用い られる. 例) ”KGU” という文字列の計算機内部表現 → 01001011 01000111 010101012 →

4B4755

16 練習 1.2 空欄を埋めよ 2進数 8進数 16進数 10110101

265

B

5

11010111110

3276

6BE

101000111111

5077

A3F

1.3

2

進数から 10 進数への変換

例題 1.1 2 進数 1101012 を 10 進数に直せ. [方法 1] 定義どおりに計算 1101012 = 1 × 25+ 1 × 24+ 0 × 23+ 1 × 22+ 0 × 21+ 1 × 20 = 32 + 16 + 4 + 1 = 53 [方法 2] 筆算による方法

2

6

12

26

52

1 1 0 1 0 1 · · ·与えられた 2 進数 1

3

6

13

26

53

×2 + ×2 + ×2 + ×2 + ×2 + 練習 1.3 2 進数 1110110112 を筆算により 10 進数に直せ.

bababababababababababababababababababababab

筆算の原理 • 10進数の最下位に 0 を付け加えると数値は 10 倍になるが, 2 進数の最下位に 0 を付け加えること は, 数値を 2 倍することに相当する. 従って, 例えば 1102= 610であることが計算できていたとす ると, 1102 に 0 を付け加えた 11002 は, 6 × 2 = 12 を表す. また, 1102 に 1 を付け加えた 11012 は, 11002+ 1なので, 6 × 2 + 1 = 13 を表す. 11002 = 1102×2 + 0 = 12 11012 = 1102×2 + 1 = 13 • これを利用すれば, 2 進数を上位ビットから順に 10 進数に変換していくことができる. 1101012 の例では, 次のようになる. 12 = 1 112 = 12×2 + 1 = 3 1102 = 112×2 + 0 = 6 11012 = 1102×2 + 1 = 13 110102 = 11012×2 + 0 = 26 1101012 = 110102×2 + 1 = 53 このように, これまでに得られている値を 2 倍し, 最下位桁の値を足す, という操作の繰り返しに より, 2 進数を 10 進数に変換できる. これを計算しやすい形にしたのが, 上記の筆算である. • ちなみに, これは次式を内側から順に計算していくことに相当する. (a5a4a3a2a1a0)2 = a5×25+ a4×24+ a3×23+ a2×22+ a1×2 + a0 = (((((a5) × 2 + a4) × 2 + a3) × 2 + a2) × 2 + a1) × 2 + a0 このような計算法はホーナーの方法 (Horner’s rule) として知られている.

1.4

10

進数から 2 進数への変換

例題 1.2 10 進数の 53 の 2 進数に直せ. [方法 1] 定義どおりに分解する n 0 1 2 3 4 5 6 7 · · · 2n 1 2 4 8 16 32 64 128 · · · 53 = 32 +

21

= 32 + 16 +

5

= 32 + 16 + 4 +

1

=

2

5

+

2

4

+

2

2

+

2

0

=

110101

2 [方法 2] 筆算による方法

0

1

3

6

13

26

53

1

1

0

1

0

1

· · ·(答え) 余り ÷2 余り ÷2 余り ÷2 余り ÷2 余り ÷2 余り ÷2 練習 1.4 10 進数 39710を筆算により 2 進数に直せ.

bababababababababababababababababababababab

筆算の原理 • 偶数を 2 進数で表すとその最下位ビットは必ず 0 になる. また, このときの最下位ビットの 0 を 除去すると, 数値を 2 で割ったことになる. 610= 1102 → 112= 310 同様に, 奇数を 2 進数で表すとその最下位ビットは必ず 1 になる. また, このときの最下位ビット の 1 を除去すると, 数値を 2 で割っ (て端数は切り捨て) たことになる. 710= 1112 → 112= 310 • これを利用すると, 2 での割算の繰り返しにより, 2 進数表現を下位から順に求めることができる. 53/2 =26 · · · 1 → 53 = ?????12 ????? は 26 の 2 進表現 26/2 =13 · · · 0 → 53 = ????012 ???? は 13 の 2 進表現 13/2 = 6 · · · 1 → 53 = ???1012 ??? は 6 の 2 進表現 6/2 = 3 · · · 0 → 53 = ??01012 ?? は 3 の 2 進表現 3/2 = 1 · · · 1 → 53 = ?101012 ? は 1 の 2 進表現 1/2 = 0 · · · 1 → 53 = 1101012 • これは下記の式変形によって, a0, a1, · · · , a6 を順に求めていくことに相当する. (a5a4a3a2a1a0)2 = a5×25+ a4×24+ a3×23+ a2×22+ a1×2 + a0 = (((((a5) × 2 + a4) × 2 + a3) × 2 + a2) × 2 + a1) × 2 + a0

1.5

2

進数の加減乗除算

☆ 2 進数の加減乗除算 10 進数と同様の筆算で行える. (特に難しくないので, 紹介にとどめる) • 加算 (0) (1) (0) … 桁上がり (carry) 1 0 1 1 … (1110) +) 0 0 1 0 … (210) 1 1 0 1 … (1310) • 減算 (1) (1) (0) … 桁下がり (borrow) 1 0 0 1 … (910) −) 0 0 1 0 … (210) 0 1 1 1 … (710) • 乗算 1 0 0 1 … (910) ×) 1 0 1 1 … (1110) 1 0 0 1 1 0 0 1 0 0 0 0 +) 1 0 0 1 1 1 0 0 0 1 1 … (9910) • 除算 1 1 … (商 310) (除数 310)… 1 1 ) 1 0 1 1 … (被除数 1110) 1 1 1 0 1 1 1 1 0 … (剰余 210)

1.6

符号付き整数—負の数の表現

1.6.1 符号無し整数と符号付き整数 符号無し整数 …

非負整数

の表現だけ考えたもの nビットの 2 進数では 0 から

2

n

−

1

までの整数が表現可能 符号付き整数 … 負の数も含めた整数の表現を考えたもの ☆ 「−」(マイナス) を付けるだけではなく, いろいろな方法がある. 1.6.2 補数 • 1の補数 (

one’s complement

) ビット列 x の 1 の補数とは, x の各ビットを

反転

させたもの (0 を 1 に, 1 を 0 にする) 例) 00010101 の 1 の補数は

11101010

• 2の補数 (

two’s complement

) ビット列 x の 2 の補数とは, x の「1 の補数」に 1 を足したもの1 例) 01110110 の 1 の補数は 10001001. よって 2 の補数はこれに 1 を足して

10001010

. 1.6.3 符号付き整数の表現法 「符号付きの整数」の代表的な 3 つの表現法 (1)

符号

/

絶対値表現

(

sign magnitude

) 符号と絶対値の組合せで表す nビットの場合, 最上位ビットが符号ビットで, 下位 n − 1 ビットが絶対値 符号は, プラスが

0

で, マイナスが

1

例) 6 ビットで表現する場合 6 → 000110 −6 →

100110

(2)

1

の補数表現

(one’s complement) −xの表現に x の「1 の補数」を用いる 例) 6 ビットで表現する場合 6 → 000110 −6 →

111001

(3)

2

の補数表現

(two’s complement) −xの表現に x の「2 の補数」を用いる 例) 6 ビットで表現する場合 6 → 000110 −6 →

111010

練習 1.5 空欄を埋めよ 4桁 (n = 4) の場合 x 符号/絶対値表現 1 の補数表現 2 の補数表現 7 0111 0111 0111 6 0110 0110 0110 5 0101 0101 0101 4 0100 0100 0100 3 0011 0011 0011 2 0010 0010 0010 1 0001 0001 0001 0 0000 0000 0000 −1

1001

1110

1111

−2

1010

1101

1110

−3

1011

1100

1101

−4

1100

1011

1100

−5

1101

1010

1011

−6

1110

1001

1010

−7

1111

1000

1001

−8 — — 1000 【注】1.6.2節の定義では, −8の2の補数表現(1000)を求めることができない. ここには囲み「2の補数の正体」の厳密な定義を用いる必要がある. ☆ いずれの表現も

最上位ビット

が符号ビットの役割を果たす (正のとき

0

,負のとき

1

)

bababababababababababababababababababababab

2の補数表現の正体 2の補数表現の直観的な意味 10進数で言えば, −1 を 9999 で, −2 を 9998 で, …, −10 を 9990 で表していると考えれば 良い. 2の補数表現の正式な定義 nビットで表現された数 x の 2 の補数は, 2n −xの 2 進表現と定義される (1 n z }| { 00 · · · 002−x). 例えば, 4 ビットの数 0001 の 2 の補数は 10000 − 0001 = 1111. 同様に 0010 の 2 の補数は 10000 − 0010 = 1110 1の補数表現の正式な定義 nビットで表現された数 x の 1 の補数は, 2n −1 − xの 2 進表現 ( n z }| { 11 · · · 112−x). 2 の補数表示が「1 の補数表示に 1 を足したもの」となるのは, この定義を見れば自明.

1.7

2

の補数表現

1.7.1 負の数の 2 進/10 進変換 例題 1.3 次の 10 進数の 2 進表現 (5 ビットの 2 の補数表現とする) を求めよ. (1) −1310 1310 の 2 進表現 01101 の 2 の補数を求めればよい. 01101 反転−→

10010

−→+1

10011

… (答え) (2) −110 110の 2 進表現 00001 の 2 の補数を求めればよい. 00001 反転−→

11110

−→+1

11111

… (答え) (3) 1310 正の数 (で絶対値が 4 ビットで表現可能) なので, そのまま 2 進数にすればよい. 1310 =

01101

… (答え) 練習 1.6 次の 10 進数の 2 進表現 (5 ビットの 2 の補数表現とする) を求めよ. (1) −1010 (2) 710 【性質 1.2】x の 2 の補数のそのまた 2 の補数は x である. 例) x = 011012の補数−→

10011

2の補数−→

01101

例題 1.4 2 の補数表現の 2 進数 11010 を 10 進数に直せ. 最上位ビットが 1 なので負の数と分かる. 2 の補数をとると

00110

2

が得られるが, これは 10 進数で は

6

. 従って, 与えられた数は

−6

とわかる. 練習 1.7 2 の補数表現の 2 進数 11110 を 10 進数に直せ.

bababababababababababababababababababababab

2の補数表現のもう一つの顔と 例題 1.4 の別解 2の補数表示は, 「最上位ビット (符号ビット) だけ 負 の重みが付いた 2 進数表現」でもある. 例) 11010 = 1 × (−16) + 1 × 8 + 0 × 4 + 1 × 2 + 0 × 1 = −6 2の補数表示の 2 進数と 10 進数の相互変換は, この性質を用いて行うこともできる. 筆算も可能. 最上位ビットだけ 1 の代わりに −1 とすればよい. −2 −2 −4 −6 −1 1 0 1 0 −1 −1 −2 −3 −6

1.7.2 2の補数表現で表現できる数の範囲 【性質 1.3】2 の補数表現を用いた場合, n ビットで表現できる数 x の範囲は次の通り. n 範囲 n n z }| { 1000000 · · · 002 (

−2

n

₋₁

) ≤ x ≤ n z }| { 0111111 · · · 112 (

2

n

₋₁

−

1

) 4 4 z }| { 10002 (

−

8

10) ≤ x ≤ 4 z }| { 01112 (

7

10) 6 6 z }| { 1000002 (

−32

10) ≤ x ≤ 6 z }| { 0111112 (

31

10) 8 8 z }| { 100000002 (

−128

10) ≤ x ≤ 8 z }| { 011111112 (

127

10) 16 16 z }| { 10000 · · · 002 (−32, 76810) ≤ x ≤ 16 z }| { 01111 · · · 112 (32, 76710) 32 32 z }| { 1000000 · · · 002 (−2, 147, 483, 64810) ≤ x ≤ 32 z }| { 0111111 · · · 112 (2, 147, 483, 64710)

bababababababababababababababababababababab

負数の加算と減算—2 の補数表現が使われるワケ • 通常, 負の数の加算を行うためには減算が必要になる. ところが, 2 の補数表現法では, 負の数に対 しても加算がそのまま行なえる. (ただし, 加算の際に生じる最上位桁からの繰り上がりは無視す る). −2 + 3 = 1110 + 0011 = 0001 = 1 (5桁目への繰上りは無視) −7 + 3 = 1001 + 0011 = 1100 = −4 ☆ これは, 10 進数で考えると, −2 + 3 = 9998 + 0003 = 0001 −7 + 3 = 9993 + 0003 = 9996 = −4 と計算していることに相当する • 減算は補数の加算に帰着できる 5 − 3 = 5 + (−3) = 0101 + 1101 = 0010 • このように, 2 の補数表現を用いれば全ての減算は加算に帰着できる. つまり, 減算が不要になって しまうので, 加算器とは別に減算器を作らなくてもよい. これが計算機内部での数表現に 2 の補数 表現がよく用いられる理由の一つである.

練習問題の解答例

練習 1.1 10進数 2進数 8 進数 16 進数 5 101 5 5 7 111 7 7 8 1000 10 8 13 1101 15 D 15 1111 17 F 16 10000 20 10 31 11111 37 1F 32 100000 40 20 練習 1.2 2進数 8 進数 16 進数 10110101 265 B5 11010111110 3276 6BE 101000111111 5077 A3F 練習 1.3 1110110112= 47510 2 6 14 28 58 118 236 474 1 1 1 0 1 1 0 1 1 1 3 7 14 29 59 118 237 475 練習 1.4 39710= 1100011012 0 1 3 6 12 24 49 99 198 397 1 1 0 0 0 1 1 0 1 練習 1.5 4桁 (n = 4) の場合 x 符号/絶対値 1 の補数 2 の補数 −1 1001 1110 1111 −2 1010 1101 1110 −3 1011 1100 1101 −4 1100 1011 1100 −5 1101 1010 1011 −6 1110 1001 1010 −7 1111 1000 1001 −8 — — 1000

練習 1.6 (1) 1010 の 2 進表現 01010 の 2 の補数を求めると, 10110 (2) 正の数 710 はそのまま 2 進表現にして, 00111 練習 1.7 2の補数をとると 000102 が得られるがこれは 10 進数では 2. 従って, 与えられた数は −210 である. Nagisa ISHIURA