บทนำ
กำหนดตัวเลขสองตัวเป็นสตริงบाइनนารี (Binary String) ภารกิจของเราคือหาผลคูณของตัวเลขเหล่านั้นอย่างรวดเร็วและมีประสิทธิภาพ
ใช้กลยุทธ์ Divide and Conquer (แบ่งและเอาชนะ) สามารถแก้ปัญหาได้อย่างมีประสิทธิภาพ เราจะแบ่งตัวเลขออกเป็นสองครึ่ง
ให้ Xleft และ Xright เป็นสองส่วนของตัวเลขแรก X และ Yleft, Yright เป็นสองส่วนของตัวเลขที่สอง Y ดังนั้นผลคูณ:
เพื่อให้ง่ายขึ้น สามารถดำเนินการนี้ได้:
อินพุตและเอาต์พุต
Input: สองตัวเลขบाइनนารี: 1101 และ 0111 Output: ผลลัพธ์คือ: 91
อัลกอริทึม
addBitString(num1, num2)
Input: สองตัวเลขที่จะบวก
Output: ผลลัพธ์หลังการบวก
Begin
ปรับความยาว num1 และ num2
length := ความยาวของ num1
carry := 0
for i := length -1 down to 0, do
num1Bit := num1[i]
num2Bit := num2[i]
sum := num1Bit XOR num2Bit XOR carry
finalSum := sum + finalSum
carry := (num1Bit AND num2Bit) OR (num2Bit AND carry) OR (num1Bit AND carry)
done
if carry ≠ 0, then
finalSum := 1 + finalSum
return finalSum
End
multiply(num1, num2)
Input: สองตัวเลขที่จะคูณ
Output: ผลลัพธ์หลังการคูณ
Begin
ปรับความยาว num1 และ num2
length := ความยาวของ num1
if n = 0, then
return 0
if n = 1, then
return (num1[0] * num2[0])
firstHalf := n/2
secondHalf := (n - firstHalf)
n1Left := substring ของ (0 ถึง firstHalf) จาก num1
n1Right := substring ของ (firstHalf ถึง secondHalf) จาก num1
n2Left := substring ของ (0 ถึง firstHalf) จาก num2
n2Right := substring ของ (firstHalf ถึง secondHalf) จาก num2
p1 := multiply(n1Left, n2Left)
p2 := multiply(n1Right, n2Right)
add1 := addBitString(n1Left, n1Right)
add2 := addBitString(n2Left, n2Right)
p3 := multiply(add1, add2)
mask1 := shift 1 ไปซ้าย 2*secondHalf bits
mask2 := shift 1 ไปซ้าย secondHalf bits
return P1*mask2 + (p3 - p1 - p2)*mask2 + p2
End
ตัวอย่างโค้ด (C++)
#include <iostream>
using namespace std;
int lengthAdjust(string &num1, string &num2) {
// ปรับความยาวสตริงบाइनนารีและส่งคืนความยาว
int len1 = num1.size();
int len2 = num2.size();
if (len1 < len2) {
for (int i = 0; i < len2 - len1; i++)
num1 = '0' + num1; // เพิ่ม 0 หน้าสตริงแรก
} else if (len1 > len2) {
for (int i = 0; i < len1 - len2; i++)
num2 = '0' + num2; // เพิ่ม 0 หน้าสตริงที่สอง
}
return num1.size();
}
string addBitStrings(string num1, string num2) {
string finalSum;
int length = lengthAdjust(num1, num2); // ปรับและอัปเดตความยาวตัวเลขและเก็บความยาว
int carry = 0; // Initialize carry
for (int i = length-1; i >= 0; i--) {
int num1Bit = num1[i] - '0';
int num2Bit = num2[i] - '0';
int sum = (num1Bit ^ num2Bit ^ carry) + '0'; // เรารู้ว่า sum = A XOR B XOR C
finalSum = (char)sum + finalSum;
// carry = (A AND B) OR (B AND C) OR (C AND A)
carry = (num1Bit & num2Bit) | (num2Bit & carry) | (num1Bit & carry);
}
if (carry) // เมื่อมี carry
finalSum = '1' + finalSum; // เพิ่ม carry เป็น MSB
return finalSum;
}
long int multiply(string num1, string num2) {
int n = lengthAdjust(num1, num2); // หาความยาวหลังปรับแล้ว
if (n == 0) // เมื่อสตริงยาว 0 คืนค่า 0
return 0;
if (n == 1) // ทำการคูณ single bit
return (num1[0] - '0') * (num2[0] - '0');
int firstHalf = n/2; // ช่วงครึ่งแรก
int secondHalf = (n - firstHalf); // ช่วงครึ่งหลัง
string num1Left = num1.substr(0, firstHalf); // ครึ่งแรกของตัวเลข 1
string num1Right = num1.substr(firstHalf, secondHalf); // ครึ่งหลังของตัวเลข 1
string num2Left = num2.substr(0, firstHalf);
string num2Right = num2.substr(firstHalf, secondHalf);
// หาการคูณซ้าย-ขวา และคูณหลังจากบวกส่วนซ้ายและขวา
long int P1 = multiply(num1Left, num2Left);
long int P2 = multiply(num1Right, num2Right);
long int P3 = multiply(addBitStrings(num1Left, num1Right), addBitStrings(num2Left, num2Right));
return P1*(1<<(2*secondHalf)) + (P3 - P1 - P2)*(1<> num1;
cout << "Enter Second number in Binary: "; cin >> num2;
cout << "The result is: " << multiply(num1, num2);
}
ผลลัพธ์
Enter First number in Binary: 1101 Enter Second number in Binary: 0111 The result is: 91
