इस समस्या में, हमें दो पूर्णांक मान 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 ढूंढना है।
अधिक प्रभावी समाधान,
यह एक अधिक प्रभावी समाधान है, जिसे निम्न का उपयोग करके किया जा सकता है -
चरण 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 से max(MSBa, MSBb) तक के सभी बिट्स सेट करें।
चरण 3 - परिणाम प्रिंट करें।
अब, आइए उपरोक्त एल्गोरिदम को कार्य करते हुए देखें -
उदाहरण - a = 3 और b = 8।
समाधान -
चरण1 - MSBa = 1 ; MSBb = 3
चरण2 - MSBa != MSBb, परिणाम के बिट स्थिति 3 से बिट स्थिति 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 CalcBitwiseORRange( 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 << "रेंज " << a << " से " << b << " तक सभी पूर्णांकों का बिटवाइज OR (|) " << CalcBitwiseORRange(a, b);
return 0;
}
आउटपुट
रेंज 3 से 8 तक सभी पूर्णांकों का बिटवाइज OR (|) 15