C++의 이진 표현에서 두 개의 즉각적인 1 사이의 최대 0

문제 설명

주어진 숫자 n에서 작업은 주어진 n의 이진 표현에서 두 개의 즉각적인 1 사이의 최대 0을 찾는 것입니다. 이진 표현에 1이 2개 미만이면 -1을 반환합니다.

예시

입력 번호가 35이면 이진 표현은 -

00100011

위의 이진 표현에서 두 개의 즉각적인 1 사이에는 3개의 0이 있습니다. 따라서 답은 3입니다.

알고리즘

비트 시프트 연산자를 사용하여 이 문제를 해결할 수 있습니다. n의 이진 표현에서 두 개의 즉각적인 1의 위치를 ​​찾고 이 위치의 차이를 최대화해야 합니다.

• 숫자가 0이거나 2의 거듭제곱이면 -1을 반환합니다.
• 변수 prev를 맨 오른쪽 첫 번째 위치로 초기화합니다. 이전에 본 위치를 1로 저장합니다.
• prev 바로 뒤에 1의 위치를 ​​저장하는 다른 변수 cur를 가져옵니다.
• Cur – prev – 1의 차이를 구하면 즉시 1과 0 사이의 0의 개수가 되며 이전 최대값인 0과 비교하여 prev를 업데이트합니다. 다음 반복을 위해 prev=cur.
• n의 모든 비트를 스캔하고 현재 비트가 0 또는 1인지 감지하는 데 도움이 되는 변수 setBit를 사용합니다. n의 모든 비트를 스캔하고 현재 비트가 0 또는 1인지 감지하는 데 도움이 되는 보조 변수 setBit을 사용합니다.

예시

이제 예를 살펴보겠습니다 -

#include <bits/stdc++.h>
using namespace std;
int getMaxZeros(int n) {
   if (n == 0 || (n & (n - 1) == 0)) {
      return -1;
   }
   int setBit = 1;
   int prev = 0;
   int i;
   for (i = 1; i < sizeof(int) * 8; ++i) {
      ++prev;
      if ((n & setBit) == setBit) {
         setBit = setBit << 1;
         break;
      }
      setBit = setBit << 1;
   }
   int maxZeros = INT_MIN;
   int cur = prev;
   for (int j = i + 1; j <= sizeof(int) * 8; ++j) {
      ++cur;
      if ((n & setBit) == setBit) {
         if (maxZeros < (cur - prev - 1)) {
            maxZeros = cur - prev - 1; prev = cur;
         }
      }
      setBit = setBit << 1;
   }
   return maxZeros;
}
int main() {
   int n = 35;
   cout << "Maximum zeros = " << getMaxZeros(n) << endl;
   return 0;
}

출력

Maximum zeros = 3