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
– Kaz, Commented Oct 25, 2013 at 23:57
I think that is where my confusion lies as well.. this seems like the question is not well formed. — bjackfly
– bjackfly, Commented Oct 25, 2013 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
– Kerrek SB, Commented Oct 26, 2013 at 0:09
@KerrekSB While you make dinner in order N, I will just ... order in. — Kaz
– Kaz, Commented Oct 26, 2013 at 0:15

Tomas · Accepted Answer · 2013-10-26 08:51:03Z

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, 2013 at 8:51

answered Oct 25, 2013 at 23:51

Tomas

60.2k54 gold badges251 silver badges386 bronze badges

Sign up to request clarification or add additional context in comments.

1 Comment

Tomas Over a year ago

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! :-)

Community · Accepted Answer · 2017-05-23 11:50:05Z

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!

Collectives™ on Stack Overflow

Algo for finding continuous items in log(N) time

2 Answers 2

1 Comment

Comments

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

Comments

Linked

Related