基本情報技術者試験 PCの算術演算の理解

イントロダクション

前回は2進数の変換、補数表現について学習しました。

今回は、PCが行う算術演算を理解します。
こちらのサイトの説明も参考にしました。

PCの演算前提

  1. PCは減算処理をしない、加算のみで計算する
  2. 乗算・除算に関しては、シフト演算を行う

PCの加算・減算

==加算==
加算に関しては、単純に足し算を行う、認識でよい認識ですので割愛します。詳細は前回の記事を参照ください。

==減算==
減算は「補数」を使用して減算式を加算式に変換して実行します。

4 - 3 = 1

上の式は、下のように変換します。

4 + (-3) = 1

変換するときに「補数」を使用します。正確にはビット反転した値 + 1の値を使用します。※「補数」という表現がわかりずらく、ややこしいのでここでは具体的な表現にしたいのです。

計算方法としては、下のようになります。

10進数表現 2進数表現(8bit)
4 00000100
3 00000011
-3 00000011
①00000011 => 3

②11111100 => ビット反転後の値

当然のように、①と②を合算し、1を加算すると桁が1つ繰り上がります。この時の②+1の値を「2進数における2の補数」と呼びます。

具体的には、以下のようになります。

Step1: 4 - 3 = 1

Step2: 4 + (-3) = 1

Step3:(00000100) - (00000011) = (00000001)

Step4:(00000100) + (11111100 + 1) = (00000001)

Step5: (00000100) + (11111101) = ()

わかりずらいので、縦に並べます。

   (00000100)
+ (11111101)
=(100000001)※繰り上がって9ビットになる

8バイトで計算をしているので、あふれた分を無視して残ったのが(00000001)=1となり、「4-3=1」という計算ができました。

乗算と除算

乗算・除算は、ビットシフトしますが、左へのビットシフトは乗算、右へのビットシフトは除算になります。まとめると下の表のようになります。

元の数 乗算(2ビット左シフト) 除算(2ビット右シフト)
4 00000100 -> 00010000 00000100 -> 00000001
3 00000011 -> 00001100 00000011 -> 00000000 ... 11
  1. 4の2乗=2ビット左シフト
  2. 4の1/2乗=2ビット右シフト
  3. 3の2乗=2ビット左シフト
  4. 3の1/2乗=2ビット右シフト

つまるところは、数値2のX乗といった形の演算が基本になります。

通常の掛け算と割り算

参考サイトはこちらです。

掛け算の場合

2のN乗の形で値を変換してから合計します。
例1:<3 x 4の場合>(4ビットで考えます)

  1. 2進数に変換する
  2. A「3 = 0011」 の B「4倍 = 0100」掛け算をする
  3. A「0011」とB「0100」の掛け算=A x「2の2乗 + 0の1乗 + 0の0乗」※右から2の1乗、2乗 … となる。
  4. 「0011を2ビット左シフト -> 1100」+「0の3乗なので何もしない」「2の2乗=4」「0の1乗なので何もしない」「0の0乗なので何もしない」※右から2の1乗、2乗 … となる。
  5. 「1100」+「0」+「0」=「12」+「0」+「0」=「12」

例2:<2 x 7の場合>(4ビットで考えます)

  1. 2進数に変換する
  2. 「2 = 0010」 の 「7倍 = 0111」掛け算をする
  3. 「0010」の掛け算=「0の3乗(何もない)」 + 「2の2乗(2ビットシフト)」 + 「2の1乗(1ビットシフト)」 + 「2の0乗(シフトしない)」
  4. 「1000」+「0100」+「0010」=「8」+「4」+「2」=「14」

ビットシフトには2種類あります。

  1. 論理シフト(符号なしデータ)
    =左にあふれた分は無視
    、右にあふれた分はあまりとして使用する

  2. 算術シフト(符号付きデータ)
    =符号ビットの部分はそのままにしておく

Javaで理解する

2進数の加算減算に関しては、前回やったので割愛します。

今回は、乗算・除算を行います。
上記の理論を実装すると下のようになります。

/**
 * 2進数の掛け算をおこなう。
 * @param num1 2進数のバイト
 * @param num2 2進数のバイト
 * @return 計算結果
 */
public int binaryMultiply(byte num1, byte num2) {
    // ①掛け算を行う
    String numSt1 = Integer.toBinaryString(num1);
    String numSt2 = Integer.toBinaryString(num2);
    System.out.print("num1: " + numSt1);
    System.out.println("num2: " + numSt2);

    char[] num2Ch = numSt2.toCharArray();

    int ans = 0;
    int len = num2Ch.length;
    for (int i = 0; i < len; i++) {
        int tmp = 0;
        // ビットがっていたらビットシフトして合算する
        if (num2Ch[i] == '1') {
            // シフトする数
            int shift = (len - i) -1;
            tmp = num1 << shift;
            System.out.println("シフト:" + shift + " 値: " + tmp);
        }
        ans += tmp;
    }
    return ans;
}

プログラムを書いて動かしてみた結果

A * B => Aの値をBのビットの立っている「桁-1」乗した値を合算する

2 * 7ならば、2の2ビットシフトした値 + 2の1ビットシフトした値 + 2の0ビットシフトした値が答え

という認識にかわりました。

演算誤差

今までの計算を行った時に、データの範囲が4ビットで考えたり、8ビットで考えたりしましたが、PCの演算でも同じことが起こります。
計算をしたとき、8ビットで計算しているのに、9ビット目に桁が繰り上がったり、割り算をしたときに桁が繰り下がったりすることがあります。※ビットシフトすると桁落ちします。

そうすると誤差が起きます。桁が繰り上がってデータが無視される状態をオーバーフロー逆をアンダーフローといいます。

論理演算

参考サイトはこちらです。

結論から記載すると以下のようになります。

A B 論理積 AND 論理和 OR A の否定 NOT 排他的論理和 XOR 否定論理積 NAND 否定論理和 NOR
0 0 0 0 1 0 1 1
0 1 0 1 1 1 1 0
1 0 0 1 0 1 1 0
1 1 1 1 0 0 0 0
  • ANDは、入力の少なくとも1つが「0」のとき、出力は「0」になる。
  • NANDは、入力の少なくとも1つが「0」のとき、出力は「1」になる。
  • ORは、入力の少なくとも1つが「1」のとき、出力は「1」になる。
  • NORは、入力の少なくとも1つが「1」のとき、出力は「0」になる。

しかし、こんなものを覚える気はありません。では、何を理解するのか?

ポイント

以下のように考えたときに、演算の結果がTrue(1)かFalse(0)になるか?というところです。

1 = true

上の表は、A 演算 B = 答えのような形で表にしています。例えば、

A = 0, B = 0の場合 -> A and B = 0;
A = 0, B = 1の場合 -> A and B = 0;
A = 1, B = 1の場合 -> A and B = 0;

というような答えが出ます。その説明のために、下のような図が使われます。

ビットマスク演算

どうやら、ネットワーク通信時に使用することが多いようです。参考サイトはこちらです。

ネットワークで使用するIPアドレスに対してアクセスのコントロールを行うためのACL(アクセスコントロールリスト)を見るとわかりやすいと思います。

早い話が、0とか1をまとめて変更するのにビットマスク演算を使用します。

そして、演算に関しては、次のような形です。
<例1>
1バイト:

00100101

00100101

を計算して、ビットの立っているところをコントロールしようというものです。

各ビットに対してANDとか、ORの計算をするだけです。
特に難しく考える必要はないようです。

基本情報試験のほうで論理回路の問題が出ますので、これを理解しておくとあと、が楽になりそうです。

Javaプログラムで何かしらの実装することもないと思ったので、今回はこの辺で。。。

試験問題を作成しました。PDFを切り貼りしてます。

でわでわ。。。