Tìm chuỗi dài nhất của 1 trong biểu diễn nhị phân với một lần lật trong C ++

Giả sử chúng ta có một số nguyên n. Bên trong đó, chúng ta có thể thực hiện lật một bit để tạo ra chuỗi 1s dài nhất. Giả sử số là 13, do đó, biểu diễn nhị phân là 1101. Nếu chúng ta thực hiện một lần lật một bit như thực hiện từ 0 thành 1, nó sẽ là 1111. Đây là chuỗi 1s dài nhất

Để giải quyết vấn đề này, chúng ta sẽ đi qua các bit của một số nhất định. Chúng tôi sẽ theo dõi độ dài trình tự của 1 hiện tại và độ dài trình tự của 1 trước đó. Khi tìm thấy số 0, hãy cập nhật độ dài trước đó. Vì vậy, nếu bit tiếp theo là 1, thì độ dài trước đó nên được đặt thành độ dài hiện tại. Nếu giá trị tiếp theo là 0, thì hãy đặt lại mã trước đó là 0.

Ví dụ

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

Đầu ra

Maximum length of the sequence with 1s: 4