इस समस्या में, हमें एक संख्या N दी गई है। हमारा कार्य संख्या के दाएं सबसे सेट बिट का इंडेक्स प्रिंट करना है।
समस्या को समझने के लिए एक उदाहरण लेते हैं,
इनपुट - 4
आउटपुट - 3
व्याख्या - 4 का बाइनरी 100 है, दाएं सबसे सेट बिट का इंडेक्स 3 है।
इस समस्या को हल करने के लिए, एक सरल समाधान संख्या को तब तक शिफ्ट करना होगा जब तक सेट बिट न मिल जाए लेकिन अगर संख्या बड़ी है तो इसमें बहुत गणना लग सकती है।
एक अधिक कुशल समाधान बूलियन बीजगणित का उपयोग करना होगा। इसके लिए हम पहले संख्या के 2 के पूरक की गणना करेंगे, यह संख्या के सभी बिट्स को फ्लिप कर देगा और पहले सेट बिट को वैसे ही छोड़ देगा। फिर हम संख्या और उसके 2 के पूरक का बिटवाइज़ AND निकालेंगे। इसका परिणाम केवल एक सेट बिट वाली संख्या होगी और वह स्थिति जो हम चाहते हैं। समाधान संख्या के log2 + 1 द्वारा दिया जाएगा।
यह समझने में थोड़ा जटिल लगता है, आइए इस विधि का उपयोग करके एक उदाहरण हल करें।
N = 10, बाइनरी = 1010 2 का पूरक, 0101 1010 & 0101 = 0010 log2(2) = 1 1+1 = 2 जो दिया गया इंडेक्स है।
उदाहरण
हमारे समाधान के कार्यान्वयन को दर्शाने वाला प्रोग्राम,
#include <iostream>
#include <math.h>
using namespace std;
void rightSetBit(int N) {
int bitIndex = log2(N & -N) + 1;
cout << bitIndex;
}
int main() {
int N = 10;
cout << "संख्या " << N << " का दाएं सबसे सेट बिट है: ";
rightSetBit(N);
return 0;
}
आउटपुट
संख्या 10 का दाएं सबसे सेट बिट है: 2
