i fail to understand how can you give a pointer to a bit which is not
starting at the word boundary?
Best Regards
Ashish Goel
"Think positive and find fuel in failure"
+919985813081
+919966006652
On Mon, Jul 5, 2010 at 7:24 PM, Siddhi <siddhi.tadpatri...@gmail.com> wrote:
> 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<algogeeks%2bunsubscr...@googlegroups.com>
> .
> For more options, visit this group at
> http://groups.google.com/group/algogeeks?hl=en.
>
>
--
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.
