দুটি সংখ্যা বাইনারি স্ট্রিং হিসেবে দেওয়া আছে, আমাদের কাজ সেই সংখ্যাগুলোর গুণফল বের করা দ্রুত এবং কার্যকর পদ্ধতিতে।
ডিভাইড অ্যান্ড কনকার কৌশল ব্যবহার করে, আমরা সমস্যাটি খুব কার্যকরভাবে সমাধান করতে পারি। আমরা সংখ্যাগুলো দুটি ভাগে ভাগ করব।
Xleft এবং Xright প্রথম সংখ্যা X-এর দুটি অংশ, এবং Yleft, Yright দ্বিতীয় সংখ্যা Y-এর দুটি অংশ। তাই গুণফল;
সহজ করতে, আমরা এই অপারেশন করতে পারি
ইনপুট এবং আউটপুট
ইনপুট: দুটি বাইনারি সংখ্যা: 1101 এবং 0111 আউটপুট: ফলাফলটি হল: ৯১
অ্যালগরিদম
addBitString(num1, num2)
ইনপুট: যোগ করার জন্য দুটি সংখ্যা।
আউটপুট: যোগফলের ফলাফল।
শুরু
num1 এবং num2-এর দৈর্ঘ্য সমান করুন
length := num1-এর দৈর্ঘ্য
carry := 0
i := length -1 থেকে 0 পর্যন্ত নিচের দিকে, করুন
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)
শেষ
যদি carry ≠ 0, তবে
finalSum := 1 + finalSum
finalSum ফেরত দিন
শেষmultiply(num1, num2)
ইনপুট: গুণ করার জন্য দুটি সংখ্যা।
আউটপুট: গুণনের ফলাফল।
শুরু
num1 এবং num2-এর দৈর্ঘ্য সমান করুন
length := num1-এর দৈর্ঘ্য
যদি n = 0, তবে
0 ফেরত দিন
যদি n = 1, তবে
(num1[0] * num2[0]) ফেরত দিন
firstHalf := n/2
secondHalf := (n - firstHalf)
n1Left := num1-এর (0 থেকে firstHalf) সাবস্ট্রিং
n1Right := num1-এর (firstHalf থেকে secondHalf) সাবস্ট্রিং
n2Left := num2-এর (0 থেকে firstHalf) সাবস্ট্রিং
n2Right := num2-এর (firstHalf থেকে secondHalf) সাবস্ট্রিং
p1 := multiply(n1Left, n2Left)
p2 := multiply(n1Right, n2Right)
add1 := addBitString(n1Left, n1Right)
add2 := addBitString(n2Left, n2Right)
p3 := multiply(add1, add2)
mask1 := 1 কে ২*secondHalf বিট বামে শিফট করুন
mask2 := 1 কে secondHalf বিট বামে শিফট করুন
P1*mask2 + (p3 – p1 – p2)*mask2 + p2 ফেরত দিন
শেষউদাহরণ
#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; //প্রথম স্ট্রিংয়ে ০ যোগ করুন } else if (len1 > len2) { for (int i = 0 ; i < len1 - len2 ; i++) num2 = '0' + num2; //দ্বিতীয় স্ট্রিংয়ে ০ যোগ করুন } return num1.size(); } string addBitStrings(string num1, string num2) { string finalSum; int length = lengthAdjust(num1, num2); //দৈর্ঘ্য সমান করুন এবং আপডেট করুন এবং দৈর্ঘ্য সংরক্ষণ করুন int carry = 0; //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; //ক্যারি = (A AND B) OR (B AND C) OR (C AND A) carry = (num1Bit&num2Bit) | (num2Bit&carry) | (num1Bit&carry); } if (carry) //যখন ক্যারি থাকে finalSum = '1' + finalSum; //ক্যারি MSB হিসেবে যোগ করুন return finalSum; } long int multiply(string num1, string num2) { int n = lengthAdjust(num1, num2); //সমান করার পর দৈর্ঘ্য বের করুন if (n == 0) //যখন ০ দৈর্ঘ্যের স্ট্রিং, ০ ফেরত দিন return 0; if (n == 1) return (num1[0] - '0')*(num2[0] - '0'); //সিঙ্গেল বিট গুণন করুন int firstHalf = n/2; //প্রথম অর্ধেক রেঞ্জ int secondHalf = (n-firstHalf); //দ্বিতীয় অর্ধেক রেঞ্জ string num1Left = num1.substr(0, firstHalf); //সংখ্যা ১-এর প্রথম অর্ধেক string num1Right = num1.substr(firstHalf, secondHalf); //সংখ্যা ১-এর দ্বিতীয় অর্ধেক 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<<secondHalf) + P2; } int main() { string num1, num2; cout << "Enter First number in Binary: "; cin >>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
