On Jul 4, 6:31 am, jalaj jaiswal <[email protected]> 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 [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
