イントロダクション
前回は2進数の変換、補数表現について学習しました。
今回は、PCが行う算術演算を理解します。
こちらのサイトの説明も参考にしました。
PCの演算前提
- PCは減算処理をしない、加算のみで計算する
- 乗算・除算に関しては、シフト演算を行う
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 |
- 4の2乗=2ビット左シフト
- 4の1/2乗=2ビット右シフト
- 3の2乗=2ビット左シフト
- 3の1/2乗=2ビット右シフト
つまるところは、数値2のX乗といった形の演算が基本になります。
通常の掛け算と割り算
参考サイトはこちらです。
掛け算の場合
2のN乗の形で値を変換してから合計します。
例1:<3 x 4の場合>(4ビットで考えます)
- 2進数に変換する
- A「3 = 0011」 の B「4倍 = 0100」掛け算をする
- A「0011」とB「0100」の掛け算=A x「2の2乗 + 0の1乗 + 0の0乗」※右から2の1乗、2乗 … となる。
- 「0011を2ビット左シフト -> 1100」+「0の3乗なので何もしない」「2の2乗=4」「0の1乗なので何もしない」「0の0乗なので何もしない」※右から2の1乗、2乗 … となる。
- 「1100」+「0」+「0」=「12」+「0」+「0」=「12」
例2:<2 x 7の場合>(4ビットで考えます)
- 2進数に変換する
- 「2 = 0010」 の 「7倍 = 0111」掛け算をする
- 「0010」の掛け算=「0の3乗(何もない)」 + 「2の2乗(2ビットシフト)」 + 「2の1乗(1ビットシフト)」 + 「2の0乗(シフトしない)」
- 「1000」+「0100」+「0010」=「8」+「4」+「2」=「14」
ビットシフトには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を切り貼りしてます。
でわでわ。。。