Algo for finding continuous items in log(N) time

Question

Does anyone have a concise answer for this below? I saw this on career cup. http://www.careercup.com/question?id=4860021380743168

Given a binary representation of an integer say 15 as 1111, find the maximum longest continuous sequence of 0s. The twist is it needs to be done in log N.

For example. 10000101 the answer should be 4, because there are 4 continuous zeroes.

If you have an answer in c++ that would be best for me

What is N? The number of bits in the integer? Or the integer value itself? — Kaz, Oct 25 '13 at 23:57
I think that is where my confusion lies as well.. this seems like the question is not well formed. — bjackfly, Oct 25 '13 at 23:58
@Kaz: Who cares what "N" is -- if you want to sound smart in meetings, on forums or at parties, just throw "Oh-of-En" at everyone you see -- after all, if you sound computersciencey enough, who'd ask for details? Now let me make dinner, I usually do that in O(N). — Kerrek SB, Oct 26 '13 at 00:09
@KerrekSB While you make dinner in order N, I will just ... order in. — Kaz, Oct 26 '13 at 00:15

Tomas · Accepted Answer · 2013-10-26T08:51:03.720

5

Pretty trivial, just go through the binary notation, one linear pass. The binary notation has length log(N), so it will take log(N) time.

edited Oct 26 '13 at 08:51

answered Oct 25 '13 at 23:51

Tomas

57,621
49
238
373

What?? Five upvotes for such a super-trivial answer?? I have hundreds of others, very laborous answers here which didn't get a single upvote! :-) – Tomas Oct 26 '13 at 09:49

score 0 · Answer 2 · edited May 23 '17 at 11:50

Seems like this has been asked before.

However, when I feel the need for bit-twiddling, I reach for my copy of the incomparable Hackers Delight. As it turns out, it contains discussions on finding the longest string of 1 bits, including a "logarithmic" implementation that could be used here on the bit/flipped (not) input:

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

Have fun!

Algo for finding continuous items in log(N) time

2 Answers2