หา 1 ติดต่อกันความยาว >= n ในการแทนค่าบاينารีของจำนวนใน C++

สมมติว่าเรามีจำนวนเต็มสองจำนวน x และ n งานของเราคือค้นหาสตรีม 1 ติดต่อกันแรก (32-bit binary) ซึ่งมีความยาวมากกว่าหรือเท่ากับค่า n และคืนค่าตำแหน่งของมัน หากไม่มีสตรีมดังกล่าว ให้คืนค่า -1 ตัวอย่างเช่น ถ้า x = 35 และ n = 2 ผลลัพธ์จะเป็น 31 การแทนค่าบายนารีของ 35 ในจำนวนเต็ม 32-bit เป็นดังนี้:

00000000000000000000000000100011 ดังนั้น 1 ติดต่อกัน 2 ตัวอยู่ที่ดัชนี 31 ดังนั้นคำตอบคือ 31

เพื่อแก้ปัญหานี้ เราต้องหาจำนวนศูนย์นำหน้า (Leading Zeros) และจากจำนวนนั้น เราจะพยายามหา 1 ติดต่อกัน ให้ดูตัวอย่างเพื่อเข้าใจดีขึ้น

ตัวอย่าง

#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