Tìm 1s liên tiếp có độ dài> =n trong biểu diễn nhị phân của một số trong C ++

Giả sử, chúng ta có hai số nguyên x và n, nhiệm vụ của chúng ta là tìm kiếm dòng 1s liên tiếp đầu tiên (nhị phân 32 bit) lớn hơn hoặc bằng giá trị của n theo chiều dài và trả lại vị trí của nó. Nếu không có chuỗi nào như vậy tồn tại, thì trả về -1. Ví dụ:nếu x =35 và n =2, thì kết quả sẽ là 31. Biểu diễn nhị phân của 35 trong một số nguyên 32 bit giống như -

00000000000000000000000000100011. Vậy hai số 1 liên tiếp có mặt ở chỉ số 31 nên đáp số là 31.

Để giải quyết vấn đề này, chúng ta phải tìm số lượng các số 0 ở đầu và từ số đó, chúng ta sẽ cố gắng tìm các số 1 liên tiếp. Hãy cùng chúng tôi xem ví dụ để hiểu rõ hơn.

Ví dụ

#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);
}

Đầu ra

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