#1 変数を覗いてみよう(8)
(2000年2月22日 初版)
1.8 コンピュータの計算原理
デジタルとは論理のことです。論理で演算を行うのがコンピュータです。
1.8.1 整数の演算は、すべて加算でできる
負の整数は、2の補数を使ってあらわします。従って、整数の減算は引かれる方の数
の2の補数との和を取ることで加算に置き換わります。つまり2つの整数a、bの減算
は、
a − b = a + (〜b+1),
となります。
同様に、整数の乗算や除算は共に、加算であらわすことができます。掛け算は、10
進数では掛け算の九九の規則が必要ですが、2進数では「1×1=1」だけが演算規則
です。これは任意のビットパターン **** (各*は0か1)の整数について、
**** × 1 = ****,
**** × 10 = ****0, (1ビット左シフト)
**** × 100 = *****00, (2ビット左シフト)
というように桁移動(シフト)を意味します。つまり掛け算は、「左シフトと足し算」
であらわされます。例を示すと、
45の2進数表現=101101,
5の2進数表現=101,
の掛け算は次のように計算されます。
[10進数] [2進数]
45 101101
× 5 × 101
--------- ------------
225 101101
+ 101101 (2ビット左シフト)
-------------
11100001
これを、プログラムでシミュレートしてみましょう。
// lst01_09.cpp
// 整数の掛け算のシミュレーション
#include <iostream.h>
int main()
{
int a,b;
cout << "掛け算する2つの整数を入力してください:";
cin >> a >> b;
cout << a << " * " << b << " = " << ( a * b ) << endl;
int sum = 0;
int size = sizeof(int)*8;
for(int i = 0; i < size; i++)
if( (b >> i) & 1 ) sum += ( a << i );
cout << "2進数での計算結果: " << sum << endl;
return 0;
}
|
[実行結果] ソースプログラム ( lst01_09.cpp ) |
掛け算する2つの整数を入力してください:12 31
12 * 31 = 372
2進数での計算結果: 372
|
掛け算「a×b」で、forループを使ってbの各ビットを走査します。ビットが1の桁で
は、次のif文
if( (b >> i) & 1 ) sum += ( a << i );
の条件が真となり、aを桁移動して和を取ります。これが2進数の掛け算です。
[演習問題1.9] このプログラムで、負の数を入力したら正しい結果になるか。
同様に割り算は、「左シフトと引き算」であらわされます。45÷5=9では
[10進数] [2進数]
9 1001
------- ---------
5 ) 45 101 ) 101101
45 101 (3ビット左シフト)
------ --------
0 01
--------
10
--------
101
101
-------
0
となります。引き算は足し算で置き換えられるので、割り算も「左シフトと足し算」で
あらわされることになります。
[演習問題1.10] 整数の割り算を、足し算とシフト演算を使って計算する
アルゴリズムを考えなさい。
以上より、四則演算で基本となるのは加算(足し算)です。そしてこの加算は、論理
規則で表現できます。
1.8.2 論理で演算を行う
論理学では、「この命題は真である」とか「偽である」といった文(命題)の真偽を
問題にします。基本となる論理規則そのものは、日常言語で使われているものです。
例えば、次の文
チャックは丸い頭の男の子で、そして
スヌーピーという名のビーグル犬を飼っている。
チャールズ・シュルツの「ピーナッツ」の読者はチャックが、チャーリー・ブラウンで
あると理解します。この文は2つの文
A:チャックは丸い頭の男の子である。
B:チャックは、スヌーピーという名のビーグル犬を飼っている。
から成り立ち、これらは結合子「そして(AND)」で結びつけられています。結合子
は、文に働いて新たに文を生み出す文法上の道具です。わたしたちが普段使う言語では、
述べられている文がすべて「真である」と解釈します。結合子「そして(AND)」の
役割はAとBが共に正しい場合を意味します。
論理学では、文AとBの真偽の組み合わせを分析します。つまりAとBの真偽、4つ
の組み合わせに対する結合子「そして(AND)」の働きはどうなるか?。この真偽の
関係を示すのが真理値表で、次のようになります。真を1、偽を0で表しています。
A | B | A AND B
|
0 | 0 | 0
|
0 | 1 | 0
|
1 | 0 | 0
|
1 | 1 | 1
|
これが論理規則、論理積(AND)です。
[注]このページを書く前ですが、チャールズ・シュルツ氏が亡くなりました。
さよなら、チャーリー・ブラウン、サリー、ライナス、ルーシー、シュロー
ダー、そしてペパーミント・パティ、マーシー、.....、スヌーピーとウッド
ストック。
2つ目の論理規則は、「または(OR)」という結合子で結ばれる文です。次の文、
チームが試合で負けるときは
チャックが打たれるか、またはルーシーがフライを捕れないときだ。
では、論理和(OR)が結合子として使われています。
チャーリー・ブラウンは野球チームの監督兼ピッチャーです。よく打たれます。いつ
もは凄まじい迫力のルーシー・ヴァンペルトは、このときばかりは何の役にもたちませ
ん。これを真理値表で表すと、
A:チャックが打たれる。
B:ルーシーがフライを捕れない。
A | B | A OR B
|
0 | 0 | 0
|
0 | 1 | 1
|
1 | 0 | 1
|
1 | 1 | 1
|
つまり、試合で負けるのは「チャックが打たれる」ときと、「ルーシーがフライを捕れ
ないとき」のどちらか一方の場合、さらに両方が原因で負けるときもあります。
3番目は、「ない(NOT)」つまり否定です。例えば次の文、
ライナスが、毛布を手放すことはない。
は、次のようになります。
A:ライナスは、毛布を手放す。
以上の3つを基本演算といいます。つまり、「そして(AND)」、「または(OR
)」および「ない(NOT)」です。この規則は、ビット論理演算と同じです。
記号論理学や電子回路理論では、これらをそれぞれ独自の記号で表しますが、ここで
はC/C++のビット論理演算子の記号を使うことにします。つまり、
&(AND)、|(OR)および、〜(NOT)
です。
論理和「または(OR)」では、「A | B」はAB共に真の場合は真となりま
す。しかし、これが不都合(不合理)な状況もあります。
スヌーピーは弁護士であるとき、または外科医であるときがある。
「ピーナッツ」ではしばしば弁護士や、外科医姿のスヌーピーが登場します。でも、彼
が変装するのはどちらか一方で、同時に現れることはありません。この様な状況を表す
のが、排他的論理和(XOR)です。
A | B | A XOR B
|
0 | 0 | 0
|
0 | 1 | 1
|
1 | 0 | 1
|
1 | 1 | 0
|
これが、C/C++のビット論理演算子^にあたります。
[注]排他的論理和(EXclusive OR)のことをXOR以外に、EORや
EXORなどと表すこともあります。回路理論ではEORがよく使われ
ます。
排他的論理和(XOR)は、論理積(AND)、論理和(OR)および否定(NOT)
を使ってあらわすこともできます。次の関係式が成り立ちます。
A^B = (〜A&B)|(A&〜B),
これを日常言語で表現すると、
スヌーピーは弁護士でなくて、かつ外科医であるときがあり、
または
外科医でなくて、かつ弁護士であるときがある。
「そして(AND)」と同じ意味で、「かつ」も結合子として使われます。
しかし、日常言語による置き換えには無理があります。論理の組み合わせを考えると
きには、代数的に行うのが普通です。上の論理式は、真理値表を使って容易に確かめる
ことができます。
A | B | 〜A | 〜B | 〜A&B | A&〜B | (〜A&B)|(A&〜B)
|
0 | 0 | 1 | 1 | 0 | 0 | 0
|
0 | 1 | 1 | 0 | 1 | 0 | 1
|
1 | 0 | 0 | 1 | 0 | 1 | 1
|
1 | 1 | 0 | 0 | 0 | 0 | 0
|
論理演算の代数をブール代数といいます。代数を使うことで、論理関係を見通しよく
扱えます。例えば、論理積(&)、論理和(|)および否定(〜)の3つを基本演算と
述べました。しかしこのことは、すべての論理規則を表現するのに必要な最小のセット
を意味するのではありません。本当に基本となる演算はもっと少なくて済みます。
例を示すと、ブール代数の定理の一つ、ド・モルガンの法則から次の式が導かれま
す。
A&B = 〜(〜A|〜B),
A|B = 〜(〜A&〜B),
これらの論理式は、論理積(&)は、論理和(|)と否定(〜)を使って表せることを
意味します。同じく、論理和(|)は、論理積(&)と否定(〜)を使って表せます。
つまり、2つの演算規則があれば済みます(本当は1つの規則だけですべての論理規則
を表現できます)。
[注]この事実は、2つのことを示唆します。1つは論理の根本原理は
単純であるとこと。つまりコンピュータの原理は難しくないというこ
と。そして2つ目は、私達が持っている論理規則の数はあまりにも少
ないので、世の中のすべての問題を解くには論理だけでは困難である
ことです。これはゲーデルの不完全性定理、チューリング・マシンの
停止問題として知られています。
[演習問題1.11] ド・モルガンの法則(de Morgan's law)とは、次の論理式です。
〜(A&B) = 〜A|〜B,
〜(A|B) = 〜A&〜B,
これらが成り立つことを、真理値表を使って確かめなさい。
歴史的には、19世紀半ばにイギリスのジョージ・ブール(George Boole)が、真を
1偽を0と表すことで論理学を代数学に焼き直します。記号論理学(形式論理学)の発
展期です。それから約100年後の20世紀になって、アメリカのクロード・シャノン
( C. E. Shannon)がこのブール代数をリレーを使ったスイッチ回路に応用します。
真と偽の2価論理は、電子回路のオン、オフとうまく対応します。つまり、以前に見た
ように、
「論理積(AND)は直列スイッチ回路」で「論理和(OR)は並列スイッチ回路」
です。論理がどのように計算と結びつくかを次に見てゆきます。
1.8.3 ゲート
論理演算を電子回路で表すために、下の図のような2つの入力線A,Bと、1つの出
力線Cを持つブラックボックスを考えます。
入力線には電圧の高低で区別される2種類の信号が入ります。高い電圧信号(例えば5
ボルト)を「1」、低い電圧信号(0ボルト)を「0」とすると、入力線A,Bに入る
信号0と1の組み合わせによって、出力線Cから0または1の信号が出てきます。
論理積(AND)演算を行うには、ブラックボックスの中に2つの直列スイッチがあ
り、入力信号によってスイッチをオン /オフするように素子をつくることでできます。
これがAND回路です。また、2つの並列スイッチからなる素子では論理和(OR)演
算を行うOR回路となります。論理回路は、入力信号の状態によって出力が定まるゲー
ト(門)の役目をしますので、ゲート(gate)と呼びます。例えば、ANDゲート、
ORゲート、NOTゲートなどといいます。このとき、ゲートのスイッチをオン /オフ
しているのはトランジスタです。コンピュータとは、この様な単純なトランジスタ・ス
イッチ回路の集まりです。
1.8.4 加算器のシミュレーション
ゲートを組み合わせて、2進数の加算を行う回路を設計してみましょう。1ビットの
足し算では「1+1=10」と桁上げが生じるので、単ビット加算器をつくるには2ビ
ット分の出力を考慮する必要があります。そこで、次のような2つの出力線を持つブラ
ックボックスを考えます。
出力線Sは和の結果(1桁目)を表し、出力線Cは桁上がりのビットを表します。
1ビットの足し算の真理値表は、次のようになります。
A | B | C | S
|
0 | 0 | 0 | 0
|
0 | 1 | 0 | 1
|
1 | 0 | 0 | 1
|
1 | 1 | 1 | 0
|
出力線SとCを別々に見ます。すると1桁目のビットSでは、AとBのどちらか一方だ
けが1のときSは1となります。これはXORゲートの真理値表と一致します。また、
桁上がりの出力線Cはまさに、ANDゲートです。つまり、単ビット加算器は次のよう
な回路になります。
これは半加算器といわれるものです。実際には、下の桁からの桁上げも考慮した組み合
わせ回路(全加算器といいます)を設計する必要があります。
では、この加算器をプログラムでシミュレートしてみましょう。加算器には桁上げを
扱うために2つの出力線を用意しました。プログラムでも同じように、和の結果と桁上
がりとを別々に計算します。
2つの整数xとyの足し算を次のように求めます。2つの整数型の変数sとcを用意
して、和の結果をsに納め、桁上げの結果をcに納めます。つまり、
s = x ^ y; // 和(排他的論理和)
c = (x & y) << 1; // 桁上げビット(論理積と左シフト)
cの値は桁上がりを意味するので1ビット左シフトしておく必要があります。
再び、和sに桁上がり分の数cを加えます。この足し算でも桁上がりが生じますので
前回と同じように分けて計算します。この操作を桁上がりがなくなるまで繰り返し行う
ことで加算が完了します。プログラムは、次のようになります。
// lst01_10.cpp
// 整数加算器のシミュレーション
#include <iostream.h>
int adder(int, int); // 加算器関数
int main()
{
int a,b;
cout << "足し算する2つの整数を入力してください:";
cin >> a >> b;
cout << a << " + " << b << " = " << ( a + b ) << endl;
cout << "加算器シミュレーションの結果: " << adder(a,b) << endl;
return 0;
}
// 加算器関数
int adder(int x, int y)
{
int s, c;
do{
s = x ^ y; // 和(排他的論理和)
c = (x & y) << 1; // 桁上げビット(論理積と左シフト)
x = s; y = c;
} while( y != 0 );
return x;
} |
[実行結果] ソースプログラム ( lst01_10.cpp ) |
足し算する2つの整数を入力してください:13 17
13 + 17 = 30
加算器シミュレーションの結果: 30
|
[演習問題1.12] このプログラムで、負の数を入力したら正しい結果になるか。
| 目次 | 前のページ |
Copyright(c) 2000 Yamada, K