#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の桁で は、次のifif( (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 
これが論理規則、論理積(AND)です。
[]このページを書く前ですが、チャールズ・シュルツ氏が亡くなりました。 さよなら、チャーリー・ブラウン、サリー、ライナス、ルーシー、シュロー ダー、そしてペパーミント・パティ、マーシー、.....、スヌーピーとウッド ストック。
 2つ目の論理規則は、「または(OR)」という結合子で結ばれる文です。次の文、
チームが試合で負けるときは チャックが打たれるか、またはルーシーがフライを捕れないときだ。
では、論理和(OR)が結合子として使われています。  チャーリー・ブラウンは野球チームの監督兼ピッチャーです。よく打たれます。いつ もは凄まじい迫力のルーシー・ヴァンペルトは、このときばかりは何の役にもたちませ ん。これを真理値表で表すと、 A:チャックが打たれる。 B:ルーシーがフライを捕れない。
  A    B   A OR B 
つまり、試合で負けるのは「チャックが打たれる」ときと、「ルーシーがフライを捕れ ないとき」のどちらか一方の場合、さらに両方が原因で負けるときもあります。  3番目は、「ない(NOT)」つまり否定です。例えば次の文、
ライナスが、毛布を手放すことはない
は、次のようになります。 A:ライナスは、毛布を手放す。
  A   NOT A 
 以上の3つを基本演算といいます。つまり、「そして(AND)」、「または(OR )」および「ない(NOT)」です。この規則は、ビット論理演算と同じです。  記号論理学や電子回路理論では、これらをそれぞれ独自の記号で表しますが、ここで はC/C++のビット論理演算子の記号を使うことにします。つまり、
&(AND)、|(OR)および、〜(NOT)
です。  論理和「または(OR)」では、「A | B」はAB共に真の場合は真となりま す。しかし、これが不都合(不合理)な状況もあります。
スヌーピーは弁護士であるとき、または外科医であるときがある。
「ピーナッツ」ではしばしば弁護士や、外科医姿のスヌーピーが登場します。でも、彼 が変装するのはどちらか一方で、同時に現れることはありません。この様な状況を表す のが、排他的論理和(XOR)です。
  A    B   A XOR B 
これが、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) 
 論理演算の代数をブール代数といいます。代数を使うことで、論理関係を見通しよく 扱えます。例えば、論理積(&)、論理和(|)および否定(〜)の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  
出力線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