Maximum 0's Between Two Immediate 1's in Binary Representation in C++

Problem statement

Given a number n, the task is to find the maximum 0’s between two immediate 1’s in binary representation of given n. Return -1 if binary representation contains less than two 1’s

Example

If input number is 35 then its binary representation is −

00100011

In above binary representation there are 3 0’s between two immediate 1’s. Hence answer is 3.

Algorithm

We can use bitwise shift operator to solve this problem. We need to find the position of two immediate 1’s in binary representation of n and maximize the difference of these position.

• If number is 0 or power of 2 then return -1
• IInitialize variable prev with position of first right most 1. It stores the position of previously seen 1.
• Take another variable cur which stores the position of immediate 1 just after prev.
• ITake difference of cur – prev – 1, it will be the number of 0’s between to immediate 1’s and compare it with previous max value of 0’s and update prev i.e; prev=cur for next iteration.
• IUse variable setBit, which scans all bits of n and helps to detect if current bits is 0 or 1. Use auxiliary variable setBit, which scans all bits of n and helps to detect if current bits is 0 or 1.

Example

Let us now see an example −

 Live Demo

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

Output

Maximum zeros = 3