C++에서 숫자의 이진 표현에서 길이>=n의 연속적인 1 찾기

두 개의 정수 x와 n이 있다고 가정하고 우리의 임무는 n 값보다 크거나 같은 1의 첫 번째 연속 스트림(32비트 바이너리)을 검색하는 것입니다. 길이를 늘리고 위치를 반환합니다. 그러한 문자열이 없으면 -1을 반환합니다. 예를 들어, x =35이고 n =2이면 결과는 31이 됩니다. 32비트 정수에서 35의 이진 표현은 -

0000000000000000000000000100011. 따라서 두 개의 연속 1이 인덱스 31에 있으므로 답은 31입니다.

이 문제를 해결하려면 선행 0의 수를 찾아야 하고 그 수에서 연속 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