二進数の乗算 binary multiply
2020-09-03
こんにちは、0371です。
今回は、二進数の乗算を加算とビット演算によって導き出す方法について書いていきます。
基本情報技術者試験のアルゴリズムの問題集から、擬似言語の問題を実際の言語でプログラミングしてみました。
二進数の乗算を加算とシフト演算で導き出す方法 とは？
演算結果に0を格納しておく。
乗数（右辺）が0ではない限り、以下の二つの手順を繰り返す。
- 数の最下位桁が1なら、非乗数（左辺）を演算結果に加算する。
- 非乗数(右辺)を左へ1ビット論理シフトし、乗数（左辺）を右へ1ビット論理シフトする。
コード
今回は、Integer.toBinaryString();を使用して、整数値を二進数に変換して表示することを行っています。
言語はJavaです。
二進数の乗算を加算とシフト演算で導き出すプログラム
Main.java
public class Main {
public static void main(String[] args) {
int num1 = 4;
int num2 = 10;
int answer = num1*num2;
int binAnswer = binMul(num1, num2);
System.out.println("binAnswer: "+binAnswer);
System.out.println(num1+" * "+num2+" = "+(answer));
if(binAnswer == answer) {
System.out.println("演算結果が一致しています。");
} else {
System.out.println("演算結果が一致しませんでした。");
}
}
private static int binMul(int num1, int num2) {
int ans = 0;
int count = 1;
String num1bin = Integer.toBinaryString(num1); // 二進数に変換
String num2bin = Integer.toBinaryString(num2);
String ansbin = Integer.toBinaryString(ans);
System.out.println("num1: "+num1);
System.out.println("num2: "+num2);
System.out.println("num1のビット列: "+num1bin);
System.out.println("num2のビット列: "+num2bin);
System.out.println("ansのビット列: "+ansbin);
System.out.println();
if(num2 == 0) {
System.out.println("num2が0なので、左へシフトができません。");
System.out.println("ループを開始せずにansを返却します。");
System.out.println();
}
while(num2 != 0) { // num2が左へシフトできなくなるまでループ
System.out.println((count++)+"回目のループ");
if((num2 & 1) == 1) {
System.out.println("num2の最下位桁が1なので、ansにnum1を加算します。");
ans = ans + num1;
binPrint(num1, num2, ans, num1bin, num2bin, ansbin);
}
num1 = num1 << 1;
num2 = num2 >> 1;
System.out.println("num1を右へ、num2を左へシフトさせます。");
binPrint(num1, num2, ans, num1bin, num2bin, ansbin);
System.out.println();
}
return ans; // ビット演算によって求まったansを返却する。
}
// 確認用のメソッド
private static void binPrint(int num1, int num2, int ans, String num1bin, String num2bin, String ansbin) {
num1bin = Integer.toBinaryString(num1);
num2bin = Integer.toBinaryString(num2);
ansbin = Integer.toBinaryString(ans);
System.out.println(num1bin);
System.out.println(num2bin);
System.out.println("------------");
System.out.println(ansbin);
System.out.println();
}
}
確認なしverはこちら
public class Main {
public static void main(String[] args) {
int num1 = 4;
int num2 = 10;
int binAnswer = binMul(num1, num2);
System.out.println("binAnswer: "+binAnswer);
}
private static int binMul(int num1, int num2) {
int ans = 0;
while(num2 != 0) {
if((num2 & 1) == 1) {
ans = ans + num1;
}
num1 = num1 << 1;
num2 = num2 >> 1;
}
return ans;
}
}
binMul()メソッドの中で行っているループの内容は以下の通りです。
num2の最下位桁が1の場合に、ansにnum1のビット列を加算- その後、
num1を右へ、num2を左へ1ずつシフト num2が左へシフトできなくなった場合、戻り値としてansを返却
確認ありverで、何度か実行した結果は以下の通りです。
整列前の配列: [5, 3, 8, 4, 9]
------
num1: 2
num2: 5
num1のビット列: 10
num2のビット列: 101
ansのビット列: 0
1回目のループ
num2の最下位桁が1なので、ansにnum1を加算します。
10
101
------------
10
num1を右へ、num2を左へシフトさせます。
100
10
------------
10
2回目のループ
num1を右へ、num2を左へシフトさせます。
1000
1
------------
10
3回目のループ
num2の最下位桁が1なので、ansにnum1を加算します。
1000
1
------------
1010
num1を右へ、num2を左へシフトさせます。
10000
0
------------
1010
binAnswer: 10
2 * 5 = 10
演算結果が一致しています。
num1: 0
num2: 5
num1のビット列: 0
num2のビット列: 101
ansのビット列: 0
1回目のループ
num2の最下位桁が1なので、ansにnum1を加算します。
0
101
------------
0
num1を右へ、num2を左へシフトさせます。
0
10
------------
0
2回目のループ
num1を右へ、num2を左へシフトさせます。
0
1
------------
0
3回目のループ
num2の最下位桁が1なので、ansにnum1を加算します。
0
1
------------
0
num1を右へ、num2を左へシフトさせます。
0
0
------------
0
binAnswer: 0
0 * 5 = 0
演算結果が一致しています。
num1: 2
num2: 0
num1のビット列: 10
num2のビット列: 0
ansのビット列: 0
num2が0なので、左へシフトができません。
ループを開始せずにansを返却します。
binAnswer: 0
2 * 0 = 0
演算結果が一致しています。
成功していますね。
今日の一言
たまにビットの計算をする問題が出てくるので、しっかり押さえておこう。