এই সমস্যাতে, আমাদের দুটি পূর্ণসংখ্যা a এবং b দেওয়া আছে। এবং আমাদের কাজ হলো a থেকে b পর্যন্ত রেঞ্জের বিটওয়াইজ OR (|) বের করা। অর্থাৎ a | a+1 | a+2 | … b-1 | b-এর মান বের করতে হবে।
উদাহরণ দিয়ে বুঝি,
ইনপুট − a = 3 , b = 8
আউটপুট − 15
ব্যাখ্যা − 3 | 4 | 5 | 6 | 7 | 8 = 15
সমস্যা সমাধানের জন্য, একটি সহজ সমাধান হচ্ছে a থেকে শুরু করে b পর্যন্ত এক এক করে বাড়িয়ে বিটওয়াইজ OR করা।
আরো দক্ষ সমাধান,
এটি একটি আরও দক্ষ সমাধান, যা নিচের ধাপগুলো দিয়ে করা যায় −
স্টেপ ১ − a এবং b-এর জন্য MSB বিট বের করুন, বলুন এগুলো MSBa এবং MSBb।
স্টেপ ২ − চেক করুন MSBa এবং MSBb সমান কিনা।
স্টেপ ২.১ − যদি MSBa এবং MSBb সমান হয়। করুন,
স্টেপ ২.১.১ − রেজাল্টের MSB ১ সেট করুন।
স্টেপ ২.১.২ − a এবং b থেকে MSB বিয়োগ করুন যা a এবং b-এর নতুন মান হবে। স্টেপ ১-এ যান।
স্টেপ ২.২ − যদি MSBa এবং MSBb সমান না হয়। করুন,
স্টেপ ২.২.১ − রেজাল্টের ০ থেকে max(MSBa, MSBb) পর্যন্ত সব বিট ১ সেট করুন।
স্টেপ ৩ − রেজাল্ট প্রিন্ট করুন।
এখন, উপরের অ্যালগরিদমটি কাজ করছে কিনা দেখা যাক −
উদাহরণ − a = 3 এবং b = 8।
সমাধান −
স্টেপ ১ − MSBa = 1 ; MSBb = 3
স্টেপ ২ − MSBa != MSBb, রেজাল্টের বিট পজিশন ৩ থেকে ০ পর্যন্ত সব বিট ১ সেট করুন। result = (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
