C++ में किसी संख्या के द्विआधारी प्रतिनिधित्व में लगातार 1s लंबाई>=n खोजें

मान लीजिए, हमारे पास दो पूर्णांक x और n हैं, हमारा कार्य 1s (32-बिट बाइनरी) की पहली क्रमागत धारा की खोज करना है जो n के मान से अधिक या उसके बराबर है लंबाई में और अपनी स्थिति वापस कर दें। यदि ऐसी कोई स्ट्रिंग मौजूद नहीं है, तो -1 लौटाएं। उदाहरण के लिए, यदि x =35, और n =2, तो परिणाम 31 होगा। 32-बिट पूर्णांक में 35 का द्विआधारी प्रतिनिधित्व इस प्रकार है -

000000000000000000000000100111. तो सूचकांक 31 पर लगातार दो 1s मौजूद हैं, इसलिए उत्तर 31 है।

इस समस्या को हल करने के लिए, हमें अग्रणी शून्यों की संख्या ज्ञात करनी होगी और उस गणना से हम क्रमागत 1s ज्ञात करने का प्रयास करेंगे। आइए एक बेहतर विचार प्राप्त करने के लिए उदाहरण देखें।

उदाहरण

#include<iostream>
using namespace std;
int leadingZeroCount(int x) {
   unsigned y;
   int n;
   n = 32;
   for(int i = 16; i > 1; i = i/2 ){
      y = x >> i;
      if(y != 0){
         n -= i;
         x = y;
      }
   }
   y = x >> 1;
   if (y != 0)
      return n - 2;
   return n - x;
}
int consecutiveOnePosition(unsigned x, int n) {
   int k, p;
   p = 0;
   while (x != 0) {
      k = leadingZeroCount(x);
      x = x << k;
      p = p + k;
      k = leadingZeroCount(~x);
      if (k >= n)
         return p + 1;
      x = x << k;
      p = p + k;
   }
   return -1;
}
int main() {
   int x = 35;
   int n = 2;
   cout << "Consecutive 1s of length " << n << " is starting from index: " << consecutiveOnePosition(x, n);
}

आउटपुट

Consecutive 1s of length 2 is starting from index: 31