i think 2 digit combination switch case can be kept:
e.g : there can be value between 1 to F (considered smallest 4 bit
sequence)
now 2, 4, 6 can never be part of coninuous sequence..
switch(combo):
1 followed by 8: valid
1 followed by 9: valid,
1 followed by 10: valid
like that we make combinations of all 1 to f wid each other which are
valid, else invalid:
like combo of 7 followed by F, 3 followed by F, 5 followed by F, 3
followed by 9 make sense
So i think instead of scanning every bit, what can be done is take 8
bits (anding integer with 0x0f, 0xf0)
if switch case gives valid combo as result, remember pointer to first
1's bit of left digit.. go to next, now if this and the right digit
(og previous combo) combo makes sense, then go to next else break
sequence start scanning from next remember the first pointer
(overwrite the pointer stored previously, if lengths of 1's are
greater)..
like that we can get longest sequence.
e.g, the sequence given by you is-
1111,0111,0011,1110,0000,10111
Here at beginning we get F, we remember 1st bit , next we get 7 ,
invalid combo of F and 7 (smallest length till now 4, pointer 1st bit-
remember) ,
next 7 and 3.. forget, next 3 followed by 14 .. valid combo.. length -
> 5 > previously stored length.. overwrite length.. and remember
beginning 1's position in 3..
like that continue..
i think this (if implemented well) can give better result than
scanning eaach bit..
let me know ur view.. and correct me if m wrong
On Jul 5, 12:15 am, Gene <gene.ress...@gmail.com> wrote:
> On Jul 4, 6:31 am, jalaj jaiswal <jalaj.jaiswa...@gmail.com> wrote:
>
> > There is very long array of ints, and you are given pointer to base addr of
> > this array.. each int is 16bit representation... you need to return the
> > pointer to tht "bit" inside array where longest sequence of "1"s start
> > for example. if your array has following in bit representation:
> > 1111,0111,0011,1110,0000,10111
> > then your longest sequence has 5 ones but the longest number has only 4
> > ones.(so finding highest num wnt wrk)
> > --
> > With Regards,
> > Jalaj Jaiswal
> > +919026283397
> > B.TECH IT
> > IIIT ALLAHABAD
>
> You can just define a function that accesses the array by bit index
> and then scan in a simple manner to find the longest stretch of 1's.
>
> I'll assume unsigned short is 16 bits. This code is not compiled or
> tested.
>
> // Exact definition here depends on how you want to index bits.
> // This is only one possibility.
> int bitval(unsigned short *a, unsigned long i)
> {
> return (a[i / 16ul] >> (i % 16 ul)) & 1;
>
> }
>
> // Return index of start of longest span of 1's.
> // The special value NULLBITINDEX is returned if a is all 0's.
>
> // Here's one possibility. Make this 64 bits if bit arrays can be very
> large.
> typedef unsigned long BITINDEX;
> #define NULLBITINDEX (~0ul)
>
> BITINDEX longest1span(unsigned short *a, int size)
> {
> BITINDEX bitsize = size * 16, i, j;
> // Location and length of longest span found so far.
> BITINDEX r = NULLBITINDEX, len = 0;
>
> i = 0;
> while (1) {
> // Find start of a span of 1's.
> while(1) {
> if (i == bitsize) return r;
> if (bitval(a, i) == 1) break;
> i++;
> }
> // i now points to the start of a span of 1's.
> // Get index of next 0 in j.
> for (j = i + 1; j < bitsize; j++) {
> if (bitval(a, j) == 0) break;
> }
> // [i..j-1] is a new span of 1's
> // update longest span info
> if (j - i > len) {
> r = i;
> len = j - i;
> }
> // set preconditions for new span search
> i = j;
> }
>
> }
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to algoge...@googlegroups.com.
To unsubscribe from this group, send email to
algogeeks+unsubscr...@googlegroups.com.
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
