CareerCup

Do we need to take care of endianness ?

eg no=16704 can be represented as

01000001 01000001 MSB LSB
01000001 01000001 LSB MSB

depending upon endianess

I got a method:
1)Define a signature for each int. For example, an integer like 1111,0011,1111,0000 will have a signature in string as "14021604". The even char in the signature is either 0 or 1, while the odd char is the # of consecutive 0 or 1, which is represented in hex (since the consecutive # of 0 or 1 may be larger than 10, but we only want represent the # as one char).
2)therefore, we can convert the whole array into a string.
3)Go through the whole string, it is easy to get the longest consecutive sequence of 1 and its bit position.
For example, we have an array like: 3, 4, 5, 7, if we represent each int as 4 bits, we will have 0011, 0100, 0101, 0111. Then we have the signature: "0212","011102","01110111","0113".
Then we go through the string, we can get the longest consecutive sequence is 3.

int *largestseqone(int * p,int len)
{
int *temp=p;
int count=0,maxcount=0;
int i=0,n=0;
for(i=0;i<len;i++)
{
n=*(temp+i);
printf("\n %d \n",n);
while(n!=0)
{
if(n%2==1)
{
count++;
printf("count increment: for %d is %d ",n,count);
if(count>maxcount)
{
maxcount=count;
p=temp+i;
}
}
else
{
if(count>maxcount)
{
maxcount=count;
p=temp+i;
}
count=0;
}
n=n/2;
}
count=0;
}
return p;
}


int main()
{
int arr[5]={1,13,12,8,7};
int *q=largestseqone(arr,5);
printf("\n the answer is %d",*q);
getch();

return 0;
}

gives the answer as :7 which is correct

Everybody has written something,but can somebody explain how can one return a pointer to a bit in C ??????????????
I think there should be a correction in the question

Something take this simple example:
Array = {15,7,2,1,0,23}
1111,0111,0010,0001,0000,10111
^
Result: Pointer should point to 1st bit of number 15.

anybody has the answer

Longest sequence of 1 implies the highest number in the collection. If we know the highest number in the collection, then we can return the pointer to it.

Thought about a method..Let me know if sounds Ok..
1.)keep incrementing the given integer pointer to access the elements of the array.
2.)for each integer element use the left shift operator to determine the longest sequence of 1's i.e.both "start" and "end" point..
2 a.)if the "end" point of previous element and starting bit of next element are continuous and greater increase the global count of "Continous 1's" and their starting position.
3.)For each element maintain the the number of continous 1 bits from the 16th bit.
3 a.)if the "end" point of previous element and starting bit of next element are continuous and greater increase the global count of "Continous 1's" and their starting position.
4.)finally we will have the global variable with maximum 1's with their start and endpoints.Probably return a type casted character pointer to the starting point..

I know I have written it in a confused manner. But I hope u get the Idea..

I don't think we need to consider endian problem, as long as we compare bit by bit.

how about taking two character pointers pointing to beginning of array and move till its size. moving a pointer one by one as soon as u find 1 and simultaneously tracking the sequence count and initial pointer of sequence.

I would suggest to have a 16 bit long bitmask with first bit set as 1 and rest set to zero. Do AND of that with a given integer. Check if output is 1 else do left shift of 1 bit on bitmask and check for 1 again. Once you got 1, store it and check for longest sequence in a similar way.

this is problem on bit array(search wiki) ,implement iterator over bitarray .

I don't think that it is important point to return pointer to bit. What is important that the algorithm implementation.

mask = 0x8000;
count = 0;
max = 0;
ii = 0;	// index of element in the array where longest sequence of "1"s start.
jj = 0;	// index of first "1" bit in above element
iCandidate = 0, jCandidate = 0;
for (i = 0; i < arrLen; i++)
{
	mask = 0x8000;
	for (j = 0; j < 16; j++)
	{
		if (arr[j] & mask)
		{
			if (!count)
			{
				iCandidate = i;
				jCandidate = j;
			}
			count++;
		}
		else
		{
			if (count > max)
			{
				max = count;
				ii = iCandidate;
				jj = jCandidate;
			}
			count = 0;
		}

		max >>= 1;
	}
}

Tested this in VC++, but can't figure out how to return ptr to bit.

void printArrayBits (int *ptr, int arraySize)
{
unsigned int i = 0, j = 0;
unsigned char *p = 0;

p = (unsigned char *) ptr;
for (i = 0; i < arraySize * sizeof(int); i++) {
printf ("%08X: ", i+p);
for (j = 0; j < 8; j++) {
if (*(p+i) & (0x80 >> j))
printf ("1");
else
printf ("0");
}
printf ("\n");
}
}

unsigned char *findLongestContinuousOneBitsInArray (int *ptr, int arraySize)
{
unsigned int i = 0, j = 0;
unsigned char *retPtr = 0;
unsigned char *p = 0;
unsigned char *q = 0;
int numOfOnes = 0;
int maxNumOfOnes = 0;

p = (unsigned char *) ptr;
for (i = 0; i < arraySize * sizeof(int); i++) {
for (j = 0; j < 8; j++) {
if (*(p+i) & (0x80 >> j)) {
if (numOfOnes == 0) {
// remember where we started
q = (p+i);
}
numOfOnes++;
} else {
if (numOfOnes > maxNumOfOnes) {
maxNumOfOnes = numOfOnes;
retPtr = q;
}
numOfOnes = 0;
}
}
}

// In case the array is all 1's
if (numOfOnes > 0 && q == 0) {
retPtr = q;
}


return retPtr;
}

int main(int argc, char* argv[])
{
int arr[5]={1,13,12,8,7};

printArrayBits (arr, 5);
unsigned char *p = findLongestContinuousOneBitsInArray (arr, 5);

printf("\n the answer is %p",p);
getchar();

return 0;
}

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++;
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++;
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0;
unsigned int flag=1;

for(i=0;i< ARRAYSIZE;i++)
{
flag = 01U;
for(j=0;j<INTSIZE;j++)
{
if(a[i]& flag)
temp_bits++;
else
{
if(temp_bits > no_bits)
no_bits=temp_bits;
temp_bits=0;
}
flag = flag << 1;
}
if(temp_bits > max_bits)
index=i;
}
return i;

unsigned int index=0;
unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0;
unsigned int mask=0;;

for(i=0;i < ARRAYSIZE;i++)
{
mask = 1;
no_bits = 0;
for(j=0;j<INTSIZE;j++)
{
if(a[i] & mask)
temp_bits++;
else
{
if(temp_bits > no_bits)
no_bits=temp_bits;
temp_bits=0;
}
mask = mask << 1;
}
if(no_bits > max_bits)
index=i;
}
return i;

void get_indexes(int *array_index,int * bit_index,int *array)
{

unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0;
unsigned int mask=0;
unsigned int temp_bit_index=0;

for(i=0;i < ARRAYSIZE;i++)
{
mask = 1;
no_bits = 0;
for(j=0;j<INTSIZE;j++)
{
if(array[i] & mask)
temp_bits++;
else
{
if(temp_bits > no_bits)
{
no_bits=temp_bits;
temp_bit_index =j - temp_bits;
temp_bits=0;
}
mask = mask << 1;
}
if(no_bits > max_bits)
{
array_index=i;
bit_index = temp_bit_index;
}
}
return;
}

The following function will work

#define ARRAYSIZE some value
#define INTSIZE 16

void get_indexes(int *array_index,int *bit_index,int *array)
{
unsigned int max_bits=0;
unsigned int temp_bits=0,no_bits=0,temp_bits1=0;
unsigned int mask=0;
unsigned int temp_bit_index=0;

int i=0,j=0;

for(i=0;i < ARRAYSIZE ;i++)
{
mask = 1;
no_bits = 0;
temp_bits=0;
for(j=0;j<INTSIZE;j++)
{
if(array[i] & mask)
temp_bits++;
else
{
if(temp_bits > no_bits)
{
no_bits=temp_bits;
temp_bit_index = j - no_bits;
temp_bits=0;
}
}
mask = mask << 1;

}
if((no_bits > max_bits) || (temp_bits > max_bits) )
{
max_bits=temp_bits > no_bits ? temp_bits : no_bits;
*array_index=i;
*bit_index = temp_bits > no_bits ? (j - temp_bits) : temp_bit_index;
}

}
return;
}

I think this should work, any advice ? ( make a little change, return max length of '1', no start position )

int	LeftOne( short  num)
{
	int count = 0;
	while( num & (short)0x8000)
	{
		count++;
		num <<= 1;
	}
	return count;
}

int	RightOne(short num )
{
	int count = 0;
	while( num & (short) 1 )
	{
		count++;
		num >>= 1;
	}
	return count;
}

int	MaxContiguousOne( short *input, int len)
{
	int max = 0;
	int sum = 0;

	for ( int i = 0; i < len; i++)
	{
		if ( input[i] == 0xEEEE )
		{
			sum += 16;
			continue;
		}
		else
		{
			sum += LeftOne(input[i]);
			if ( sum > max )
				max = sum;
			sum = RightOne(input[i]);
		}
	}
	return max;
}

static int bitcount_lookup[256] = {
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8,
};

/* returns number of 1 bits */
static idx_t
count(bitarrayobject *self)
{
Py_ssize_t i;
idx_t res = 0;
unsigned char c;

setunused(self);
for (i = 0; i < Py_SIZE(self); i++) {
c = self->ob_item[i];
res += bitcount_lookup[c];
}
return res;
}