c++ - log(N) 時間で連続するアイテムを見つけるためのアルゴリズム

Question

以下にこれに対する簡潔な答えがありますか？キャリアカップで見ました。http://www.careercup.com/question?id=4860021380743168

15 を 1111 とする整数のバイナリ表現が与えられた場合、連続する 0 の最大連続シーケンスを見つけます。ねじれは、log N で実行する必要があることです。

例えば。10000101 ゼロが 4 つ連続しているため、答えは 4 になるはずです。

C ++で答えがあれば、それが私に最適です

Answer 1

かなり些細なことですが、バイナリ表記を 1 つの線形パスで処理するだけです。バイナリ表記は長さlog(N)があるので、時間がかかりlog(N)ます。

Answer 2

これは以前に尋ねられたようです。

ただし、少しいじる必要があると感じたときは、比類のないHackers Delightのコピーに手を伸ばします。判明したように、ビット/反転された (ない) 入力でここで使用できる「対数」実装を含む、1 ビットの最長の文字列を見つけることに関する議論が含まれています。

int fmaxstr0(unsigned x, int *apos) {
   // invert bits.
   x = ~x;

   unsigned x2, x4, x8, x16, y, t;
   int s;

   if (x == 0) {*apos = 32; return 0;}
   x2 = x & (x << 1);
   if (x2 == 0) {s = 1; y = x; goto L1;}
   x4 = x2 & (x2 << 2);
   if (x4 == 0) {s = 2; y = x2; goto L2;}
   x8 = x4 & (x4 << 4);
   if (x8 == 0) {s = 4; y = x4; goto L4;}
   x16 = x8 & (x8 << 8);
   if (x16 == 0) {s = 8; y = x8; goto L8;}
   if (x == 0xFFFFFFFF) {*apos = 0; return 32;}
   s = 16; y = x16;

L16: t = y & (x8 << s);
     if (t != 0) {s = s + 8; y = t;}
L8:  t = y & (x4 << s);
     if (t != 0) {s = s + 4; y = t;}
L4:  t = y & (x2 << s);
     if (t != 0) {s = s + 2; y = t;}
L2:  t = y & (x  << s);
     if (t != 0) {s = s + 1; y = t;}
L1:  *apos = nlz(y);
   return s;
}

楽しむ！