C++에서 한 번의 플립으로 이진 표현에서 가장 긴 1 시퀀스 찾기

하나의 정수 n이 있다고 가정합니다. 그 안에서 우리는 1의 가장 긴 시퀀스를 생성하기 위해 1비트 플립을 만들 수 있습니다. 숫자가 13이라고 가정하고 이진 표현은 1101입니다. 0에서 1로 1비트 뒤집기를 하면 1111이 됩니다. 이것은 1의 가장 긴 시퀀스입니다.

이 문제를 해결하기 위해 주어진 숫자의 비트를 살펴보겠습니다. 현재 1의 시퀀스 길이와 이전 1의 시퀀스 길이를 추적합니다. 0이 발견되면 이전 길이를 업데이트합니다. 따라서 다음 비트가 1이면 이전 길이를 현재 길이로 설정해야 합니다. 다음 값이 0이면 이전 값을 다시 0으로 만듭니다.

예시

#include<iostream>
using namespace std;
int singleFlipMaxOnes(unsigned number) {
   if (~number == 0)
      return 8*sizeof(int);
   int curr = 0, prev = 0, max_size = 0;
   while (number!= 0) {
      if ((number & 1) == 1)
         curr++;
      else if ((number & 1) == 0) {
         prev = (number & 2) == 0? 0 : curr;
         curr = 0;
      }
      max_size = max(prev + curr, max_size);
      number >>= 1;
   }
   return max_size+1;
}
int main() {
   cout << "Maximum length of the sequence with 1s: " << singleFlipMaxOnes(13);
}

출력

Maximum length of the sequence with 1s: 4