C++のバイナリ表現での2つの直接の1の間の最大0

問題の説明

数値nが与えられた場合、タスクは、与えられたnの2進表現で2つの直接の1の間の最大0を見つけることです。バイナリ表現に含まれる1が2つ未満の場合は-1を返します

例

入力番号が35の場合、その2進表現は-

00100011

上記のバイナリ表現では、2つの直接の1の間に30があります。したがって、答えは3です。

アルゴリズム

この問題を解決するには、ビット単位のシフト演算子を使用できます。 nの2進表現で2つの直接1の位置を見つけ、これらの位置の差を最大化する必要があります。

• 数値が0または2の累乗の場合は、-1を返します
• IInitialize変数prevを、最初の右端の位置1で保存します。これは、以前に表示された1の位置を格納します。
• 前の直後の1の位置を格納する別の変数curを取得します。
• itakeのcur– prev – 1の差は、0から直前の1までの数になり、以前の最大値である0と比較してprevを更新します。 prev=curは次の反復に使用します。
• IUse変数setBitは、nのすべてのビットをスキャンし、現在のビットが0または1かどうかを検出します。補助変数setBitは、nのすべてのビットをスキャンし、現在のビットが0または1かどうかを検出します。

例

例を見てみましょう-

#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