バイオ情報科学

補数
bの補数
bn-x
n:桁数、b:基数
253(10進数)の10の補数は、1000-253=747
110(2進数)の2の補数は、2進数の1000-110=10
n
b -1-x
b-1の補数
253(10進数)の9の補数は、1000-253-1=746
110(2進数)の1の補数は、1000-110-1=001
問題
a)
b)
c)
d)
以下を求めよ。
4651の10の補数
4651の9の補数
110101(2進数)の2の補数
110101(2進数)の1の補数
1
解答
a) 10000-4651=5349
b) 5349-1 = 5348
c) 右の計算
001011
d) 001011-1 = 001010
これは元の 110101の
反転になっている。
問題
a)
b)
c)
d)
4651の10の補数
4651の9の補数
110101(2進数)の2の補数
110101(2進数)の1の補数
1000000
- 110101
--------001011
2
補数 その2
問題よりわかるように、
ビット反転とは、
1と0の入れ替え
1の補数: ビット反転になっている。
2の補数: 1の補数に1を加える。
2n-1-x
2n-1は1がn個並んでいる。
n=4の時、24-1=1111 これからxを引くと、
反転したことになる。
3
引き算をコンピュータで実行
するには。
方法1
方法2
符号ビットを用意する。
補数(ほすう)を使う。
bの補数
n:桁数、b:基数
bn-x
2の補数 ビットを反転して、1加える。
110(2進数)の2の補数は、10
もしビット数が3つだとすると、
1000-110 = 010
2の補数をとることが、マイナスに相当する。
a-bの代わりに、bの補数をaに加える。
符号ビットがなくても表現できる。
問題 11100-111(2進数)を、
a) 直接、筆算をして求めよ。
b) 111の「2の補数」を求めて11100に加えよ。
4
解答
a)
b)
問題 11100-111(2進数)を、
a) 直接、筆算をして求めよ。
b) 111の「2の補数」を求めて11100に加えよ。
11100
- 111
----00101
00111のビット反転は11000
これに1を加えると11001
これが00111の2の補数。
11100に加える。
5ビットだとすると、00101
11100
+11001
----100101
5
ビット
binary digitの略。2進数の桁数。
binary=2進数の
digit=桁
1ビット(2進数1桁)で表せる数は、0と1の2個
問1 次のビットで表せる数を全て書け。何個あるか。
a) 2ビット b) 3ビット c) 4ビット
問2
8ビットで何個の数を表せるか。
理由も説明せよ。
6
バイト
8ビットをまとめて1バイト(byte)と呼ぶ。
現在のコンピュータの多くは32ビット
または64ビットである。
(2進数32桁または64桁で数を表す。)
7
論理演算
8
論理回路
基本回路
A
B
OR
論理和
f  A B
f  A B
f
A
B
f
AND
論理積
f  A B
f  A B
A
f
NOT
否定
f A
問題1 上記3つの回路において、A, Bが
1(真)、0(偽)の値をとる時のfの値を表にせよ。
(真理値表と言う。)
問題2 次の論理式に対応する論理回路を、
3つの基本回路を使って書け。真理値表も書け。
a)
b)
c)
f  A B
f  A B
A
0
0
1
1
B
0
1
0
1
f  A B  A B
f
9
補足:論理和と論理積
f  A B
A
B
f  A B
A
f A
B
A
ここも含むことに注意。
日常会話では、
「りんごまたはみかん」は片方だけ。
「Coffee or tea?」と聞かれたら片方を選ぶことを
期待されている。
論理学では、「または」は両方の場合を含む。
10
問題1の解答
AND
OR
A
0
0
1
1
B
0
1
0
1
f
0
1
1
1
A
0
0
1
1
B
0
1
0
1
NOT
f
0
0
0
1
A
f
0
1
1
0
11
問題2の解答
NAND
NOR
A
0
0
1
1
B
0
1
0
1
f
1
0
0
0
A
0
0
1
1
B
0
1
0
1
f
1
1
1
0
XOR
A
0
0
1
1
B
0
1
0
1
A
B
1
1
0
0
1
0
1
0
A •B A•B
0
1
0
0
0
0
1
0
A•B+ A•B
0
1
1
0
12
論理回路
NOR, NAND, XORは次のような回路記号を
使うことが多い。
A
B
f
NOR
A
A
B
f
NAND
f
B
XOR
exclusive OR
AとBが違う時のみ
真になる。
13
半加算回路
A, Bはそれぞれ0または1をとるとする。
A+Bの加算結果S(1ビット)と桁上がりCを得る
回路を作りたい。
問題1、A, Bの値に対して、S, Cの値を表にせよ。
問題2 問題1の結果を使って、論理回路で書け。
桁上がりとは。
10進数の場合、
10進数の加算の例
5
+ 9
---14
1が桁上がり
4が加算結果(1桁)
14
半加算回路の解答
A
0
0
1
1
B
0
1
0
1
S
0
1
1
0
C
0
0
0
1
A
S
B
XOR
exclusive OR
A
B
C
AND
15
全加算回路
A, Bはそれぞれ0または1をとるとする。
下位桁からの繰り上がりをC1とする。(0または1)
A+B+C1の加算結果S(1ビット)と桁上がりC2を得る
回路を作りたい。
問題1、A, B、C1の値に対して、S, C2の値を表にせよ。
問題2 問題1の結果を使って、論理回路で書け。
16
問題1の解答
A
0
0
0
1
0
1
1
1
B
0
0
1
0
1
0
1
1
C1
0
1
0
0
1
1
0
1
S
0
1
1
1
0
0
0
1
C2
0
0
0
0
1
1
1
1
17
問題2の解答: Sの図
A
0
0
0
1
0
1
1
1
B
0
0
1
0
1
0
1
1
C1
0
1
0
0
1
1
0
1
S
0
1
1
1
0
0
0
1
C2
0
0
0
0
1
1
1
1
D=AxorB DxorC1
0
0
0
1
1
1
1
1
1
0
1
0
0
0
0
1
A
B
S
C1

 

S  ABC  ABC  ABC  ABC  A B  AB C  AB  A B C
D  A B  A B  A xor B D  AB  A B
を用いると、
S  DC  D C  D xor C   A xor B xor C 
18
図の注意
AND, OR, NAND, NOR, XORなどは、入力は2つ。
3入力にはできない。
だめな例
A
B
C
f
A
B
C
f
図の注意2
論理回路の素子は同じ大きさ。線を曲げて調節する。
だめな例
A
B
C1
S
A
B
C1
S
問題2の解答続き: C2
A
0
0
0
1
0
1
1
1
B
0
0
1
0
1
0
1
1
C1
0
1
0
0
1
1
0
1
S
0
1
1
1
0
0
0
1
C2
0
0
0
0
1
1
1
1
A BC  A BC  AB C  ABC 

 A B  A B C  AB(C  C )
  A xor B  C  AB
A
B
C2
A
B
C1
21
問題2の解答続き: C2
A
B
D
A
B
C1
C2
E
A
+ B
--D E
F
D: A+Bの桁上がり(半加算)
E: A+B(1桁) (半加算)
F: 「A+B」の1桁め+C1 の桁上がり
C2: D or F
(DとFは同時には1にならない。)
E
+ C1
---F S
D
F
+
---C2
22
解答続き
C2の検算
A
B
A
B
C1
A
0
0
0
1
0
1
1
1
B
0
0
1
0
1
0
1
1
C1
0
1
0
0
1
1
0
1
S
0
1
1
1
0
0
0
1
C2
0
0
0
0
1
1
1
1
D
0
0
0
0
0
0
1
1
E
0
0
1
1
1
1
0
0
F
0
0
0
0
1
1
0
0
D
C2
E
F
DorF
0
0
0
0
1
1
1
1
23
問題2: C2の別解
A
B
D
B
C
E
C
A
F
G
H
A
0
0
0
1
0
1
1
1
B
0
0
1
0
1
0
1
1
C
0
1
0
0
1
1
0
1
D
0
0
0
0
0
0
1
1
E
0
0
0
0
1
0
0
1
F
0
0
0
0
0
1
0
1
G
0
0
0
0
1
0
1
1
H
0
0
0
0
1
1
1
1
24
問題2: C2の別解:論理式で書いてみる
A
B
D
B
C
E
C
A
F
G
H
AB  BC  AC  AB(C  C )  ( A  A) BC  A( B  B)C
 ABC  ABC  ABC  ABC  ABC  ABC
 ABC  ABC  ABC  ABC
これは最初の解答と同じ論理式。
25