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

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

00000000000000000000000000100011। तो दो लगातार 1s इंडेक्स 31 पर मौजूद हैं, इसलिए उत्तर 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