ビットストリング内の最長ゼロシーケンスの検索

Question

"0001100001"のようなビットストリングが与えられた場合、最長ゼロシーケンスの長さ（この例では4）を見つける必要があります。

アルゴリズムはO（log（b））時間で実行する必要があります.bは文字列の長さです。私だけで線形時間でそれを行う方法を知って

...

は私が必要な複雑さを達成するために、何らかの形で左にビットをシフトする必要があること、聞いたことがあるが、私は、なぜ見当もつかない文字列を反復する。

ログ時間を取得するにはどうすればよいですか？

Answer 1

数を文字列として与えられるので、我々はバイナリで1000000と最長の長さ0が6である64を言う渡す場合

Integer.parseInt(String,Base) 

を使用して数を解析することができ、whileループを実行する必要log2（64）は6ですが、この解決策はあなたが探しているものでなければなりません。私は16,32および64のためにこのプログラムを実行しているし、それがログ（N）で動作時間をこの場合に関与した文字によって全く解析文字が存在しないとしてものためのビット演算子を使用

public class CountZeroes { 
private static long getZeroes(String s) { 
    int x = Integer.parseInt(s,2); 
    long count = 0, maxSoFar = 0; 
    while (x > 0) { 
     System.out.println("Running"); 
     if ((x & 1) == 1) { 
      if (count > maxSoFar) { 
       maxSoFar = count; 
      } 
      count = 0; 
     } else { 
      count += 1; 
     } 
     x = x >> 1; 
    } 
    return maxSoFar; 
} 

public static void main(String[] args) { 
    System.out.println(getZeroes("10000")); 
    System.out.println(getZeroes("100000")); 
    System.out.println(getZeroes("1000000")); 
} 
} 

以下のソリューションをご確認ください同じ。これがいいのか一度確認してください。

ありがとう