এই সমস্যায়, আমাদের দুটি পূর্ণসংখ্যার মান দেওয়া হয়েছে a এবং b। এবং আমাদের কাজ হল a থেকে b পর্যন্ত রেঞ্জের bitwise OR (|) খুঁজে বের করা। এর মানে আমাদের একটি | এর মান খুঁজে বের করতে হবে a+1 | a+2 | … খ-1 | খ.
সমস্যাটি বোঝার জন্য একটি উদাহরণ দেওয়া যাক,
ইনপুট − a =3 , b =8
আউটপুট − 15
ব্যাখ্যা −3 | 4 | 5 | 6 | 7 | 8 =15
সমস্যাটি সমাধানের জন্য, একটি সহজ সমাধান হল একটি থেকে শুরু করে বিট-ওয়াইজ OR সব সংখ্যার একটি থেকে b বাড়িয়ে।
আরও কার্যকর সমাধান,
এটি একটি আরও কার্যকর সমাধান, এটি −
ব্যবহার করে করা যেতে পারেধাপ 1 − a এবং b উভয়ের জন্য MSB বিট খুঁজুন, আসুন তাদের MSBA এবং MSBb বলি।
ধাপ 2 − MSBA MSBb-এর সমান কিনা তা পরীক্ষা করুন।
ধাপ 2.1৷ − যদি MSBA এবং MSBb সমান হয়। করুন,
ধাপ 2.1.1৷ - ফলাফলের MSB 1 হিসাবে সেট করুন।
ধাপ 2.1.2৷ − a এবং b থেকে MSB বিয়োগ করুন যা a এবং b এর জন্য নতুন মান হবে। ধাপ 1 এ যান।
ধাপ 2.2৷ − যদি MSBA এবং MSBb সমান হয়। করুন,
ধাপ 2.2.1৷ − ফলাফলের 0 থেকে সর্বোচ্চ (MSBA, MSBb) পর্যন্ত সমস্ত বিট সেট করুন৷
ধাপ 3 - প্রিন্ট ফলাফল।
এখন, কাজ করার ক্ষেত্রে উপরের অ্যালগরিদমটি দেখা যাক -
উদাহরণ − a =3 এবং b =8।
সমাধান −
পদক্ষেপ1 − MSBA =1; MSBb =3
ধাপ ২ − MSBa !=MSBb, ফলাফলের বিট অবস্থান 0 থেকে বিট অবস্থান 0 থেকে 1 পর্যন্ত সমস্ত বিট সেট করুন। ফলাফল =(1111)2 =15।
উদাহরণ
এখন, সমস্যা সমাধানের কোডটি দেখি,
#include <iostream>
using namespace std;
int FindpositionMSB(long long int n){
int MSBval = -1;
while (n) {
n = n>>1;
MSBval++;
}
return MSBval;
}
long int CalcBitwiseORRaneg( long int a, long int b) {
long int result = 0;
int msba = FindpositionMSB(a);
int msbb = FindpositionMSB(b);
while (msba == msbb) {
long int value = (1 << msba);
result += value;
a -= value;
b -= value;
msba = FindpositionMSB(a);
msbb = FindpositionMSB(b);
}
msba = max(msba, msbb);
for (int i = msba; i >= 0; i--) {
long int res_val = (1<<i);
result += res_val;
}
return result;
}
int main() {
long int a = 3, b = 8;
cout<<"The bitwise OR (|) of all integers in the range from "<<a<<" to "<<b<<" is "<<CalcBitwiseORRaneg(a, b);
return 0;
} আউটপুট
The bitwise OR (|) of all integers in the range from 3 to 8 is 15
