ค้นหา 1s ต่อเนื่องของความยาว>=n ในการแทนค่าเลขฐานสองของตัวเลขใน C++

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

00000000000000000000000000100011 ดังนั้น 1 วินาทีติดต่อกันจึงปรากฏที่ดัชนี 31 ดังนั้นคำตอบคือ 31

เพื่อแก้ปัญหานี้ เราต้องหาจำนวนศูนย์นำหน้า และจากการนับนั้น เราจะพยายามหาเลข 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