C ++中二进制表示形式的两个立即数1之间的最大0

问题陈述

给定数字n，任务是在给定n的二进制表示形式中找到两个紧邻的1之间的最大值0。如果二进制表示形式包含少于两个1，则返回-1

示例

如果输入数字为35，则其二进制表示为-

00100011

在上面的二进制表示中，两个立即数1之间有3个0。因此答案是3。

算法

我们可以使用按位移位运算符来解决此问题。我们需要找到n的二进制表示形式中两个立即数1的位置，并使这些位置的差最大。

• 如果数字为0或2的幂，则返回-1

• IInitialize变量prev，位置第一最右1。它存储先前看到的1的位置。

• 取另一个变量cur，它存储prev之后立即数1的位置。

• 当前– prev – 1的差值是到立即数1之间的0的数量，并将其与以前的最大值0进行比较并更新prev即；prev = cur用于下一次迭代。

• I使用变量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