How can we find the longest continuous subsequence of 0's in binary representation of an integer in O(log n) time complexity?

To solve this problem, notice that if we have the binary representation of the number, we can simply iterate through the bits and find the longest substring of zeros in O(L)O(L)O(L) where LLL is the length of the binary string. Also, note that L=⌈log(n+1)⌉L=⌈log⁡(n+1)⌉L = \lceil \log{(n+1)} \rceil A simple approach to solve this problem is to keep a count of the longest substring of zeros so far and update if we find a longer one. I'll simply find the length of this substring, but finding the start and end position is also trivial. Here's a pseudocode of the algorithm: maxLength = 0 currentLength = 0 while n >0 if( n mod 2 = 1) currentLength = 0 else currentLength = currentLength + 1 if (currentLength > maxLength) maxLength = currentLength n = n/2 A simple implementation is given below n = 313131532332342423585349487428 #sample number maxLength = 0 currentLength = 0 while n >0 if( n%2 == 1) currentLength = 0 else currentLength = currentLength + 1 end if (currentLength > maxLength) maxLength = currentLength end n = n/2 end puts maxLength The algorithm takes O(logn)O(log⁡n)O(\log{n}).

The question should be clarified a bit before being answered. First can we define some range for allowed integers. This is important because the allowed range for the integer coerce the available O(1) operators. If it is some arbitrarily large value stored in memory as we can work with at most one machine word at a time, this is not much better than a bit at a time from an algorithmic O point of view. On the other hand if we can limit it to be small enough, (so that a processor register can hold it) bitiwe operators are freely available. And the language level also matters: C or upper level languages only have negation, shifts, and, or, xor bitwise operators, while most modern processors offer some specialized count of leading zero or count of trailing zero instruction at processor level. Really we now have 3 independant problems: a) - find an algorithm for unrestricted integers b) - find an algorithm using C operators for register size integers c) - find and algorithm using all processor instruction set for register size integer Second, big O notation usually defines some n as the size of the problem. At first reading, considering the way the problem was stated I assumed n should be the number of bits of the provided integer... but after a more careful reading, of course it should not be understood like that, because if so the problem would be impossible to solve with the desired complexity. Henceforth  I understand that n is the provided integer, which is a bit abusive when using bif O notation, as the size of the problem should not be confused with the provided value... nevertheless. It also implies that if the integer is provided in a register the leading zeroes should be ignored (ie: for n=2 we want to find the result nbz=1 as longest sequence of zeroes, not 30 on a 32 bits register processor or 62 on a 64 bits processor). Lets' begin: Sub problem a) find an algorithm for unrestricted integers                              (in memory 2's complement representation) This one is simple assuming we start with some 2's compliment representation of number in memory. But we should notice that is we were dealing with actual BigNum representations it could be messy, because we would have to use mathematical operators (like modulo and divide by 2) to extract individual digits and these are not O(1) operations with BigNum libraries, with good libraries we reach O(n log n)... Let's forget that. This is merely a loop over a list from left to right or right to left (with large integer we need to store the number of digits somewhere, henceforth the loop is easy, event if really it's 2 loops, one over memory words, one inside every word). We increment a counter everytime we iterate over a zero, if we find a 1, we keep the counter if it's the best found until now and reset the counter to zero. Pseudo code could be: counter <- 0 max <- 0 for b from list_of_bits(n)     if b = 0:        counter <- counter + 1     else:        if counter > max:            max <- couter            counter <- 0 result is max Can we do better than that ? Well, in the worst case (number all ones or all zeroes) we can't. Between these extremes actually finding the longest 0 string could be slightly better, for instance if we proceed using dichotomy. - split the number in two consecutive bit buckets - check the number of zeroes at end of first string and beginning of second one - find the largest number of zeroes in the remaining left and right bit buckets - stop checking if remaining bit buckets are smaller than the best known result This will be better on average because it does not need to check all bits. Sub problem b) find an algorithm using C operators for register size integers As soons as we use C bitwise operators we are in this case, because such operators are not directly available for arbitrary large numbers. The most important thing to notice is that it's not an algorithmic problem any more. The problem just has to be solved for a specific number of bits which we know. Let's see how to do it for say 32 bits. For instance we can write a program like the one below (pseudo-code, just add semi-colons to have valid C). It looks for continuous parts of number, (left digits) entirely composed of 1 or of 0. The size of the consecutive checked bits change. Of course when mask reach 1 bit it will always latch exactly one bit, zero or one. int ncz(n){     if n == 0{         return 0     }     int res = 0     int count = 0     int masksize = 1         while n > 0:         int mask = (0xFFFFFFFF >> masksize) << masksize;         if (n == (n & mask)){            # rightmost masksize bits are 0            count += masksize            n >>= masksize            masksize *= 2         }         else if ((n & (mask^0xFFFFFFFF)) == (mask^0xFFFFFFFF)){            # rightmost masksize bits are 1            if count > res:               res = count            n >>= masksize            count = 0            masksize *= 2         }         else{            # rightmost bits are mixed            masksize /= 2         }     return res } It's much faster in some cases, but average complexity is still O(n) because of the worst case, make of alternance of 0 and 1. Sub problem c) find and algorithm using processor instruction set for register size integer Many processors have hardware level implementation of count of leading zero (sometimes called bit scan forward) or count of leading one. See wikipedia: http://en.wikipedia.org/wiki/Find_first_set These would allow an even simpler implementation of the algorithm showed in subcase b) that would execute exactly one time for each blocs of consecutive digits in the searched number. Still O(log n) in the worst case, but usually much much faster than that.

#include <stdio.h> #include <string.h> #include <math.h> int main() {     int no,digit,rem,max=0;     int curr,prev=0;         printf("\nEnter the no \n");     scanf("%d",&no);          while(no > 0)     {         digit = log(no)/log(2) + 1;         rem = no - pow(2,digit-1);           curr = digit;                 while((prev - curr-1) > max)         {             max = prev - curr-1;         }         prev = curr;         no = rem;     }         if((curr-1) > max)     {         max = curr-1;        }        printf("%d",max);         return 0; } in this program,suppose lets assume no is 133(133 = 1000101 ), in the first iteration no = 133 digit = 8 in the 2nd iteration no becomes 5 ,digit = 3 max = 4 then no becomes 1,digit = 2 and so on

Lets solve this problem using bit-wise operation. String findLongestContinuousZeroes(int n) {    int count = 0; /* will contain number of consecutive 0's in longest                            subsequene */    int m = ~n; /* bitwise negation flip every 0 to 1 and 1 to 0 */    String longestsubseq = "";      /* Now this is equivalent to finding longest subsequence with consecutive      1's in m */    while (m != 0)    {        m = m & (m >> 1); /* Check for consecutive 1's */        count++;        longestsubseq = longestsubseq+"0";    }    return longestsubseq; } Note : I have not executed the code.

This is the version I know:unsigned count(unsigned n) {    n = ~n;    for(int i=0; n; ++i) n &= (n<<1); return i;}