I''m a graduate programmer doing the round with job agencies at the moment. I was recently tested by one such agency with the following question. "Write a C function to return the value of a 32-bit word making execution time proportional to the number of bits set within the word." It''s stuck in my mind as I could not answer it yet it seems a simple operation. Anyone know the answer? [pseudo code appreciated] Cheers Lord[BRIT]

quote: Original post by Lord[BRIT]

"Write a C function to return the value of a 32-bit word making execution time proportional to the number of bits set within the word."

Return the value? What do you mean? If you''re talking about a string->binary conversion, simply use the left shift operator and bitwise OR values in. For example, for a 4-bit word:

__int4 word4 = 0;
char str[sizeof(__int4)+1] = "1011";
for (i = 0; i < 4; i++)
word4 /= str == ''1'' ? 1 << i : 0;

This is how the loop goes.

i / word4 (binary)
---------------------
0 0001
1 0011
2 0011
3 1011

which is what you want.

Helps any?

ok I think I understand what there asking here....
ummm I''m just going to do some code here...
I''m just doing it off the top of my head so....

void SomeFunc(word bits){
short number_of_bits=0;

for(int i=0;i<32;i++){//loop to count number of ones
if( (bits>>i)%2)//shift it i bits the the right then mod by 2... because we jsut want to know if the first bit is on... if it is it wont be evenly divisable by 2...
number_of_bits++;
}
for(int u=0;u//do something
// this will delay the return of the func proporanaly to the number of bits on...
}
}

I don''t know if this is what you wanted but....

Great Milenko

Words Of Wisdom:
"Never Stick A Pretzel In Your Butt It Might Break Off In There."

http://www.crosswinds.net/~milenko
http://www.crosswinds.net/~pirotech

"Write a C function to return the value of a 32-bit word making execution time proportional to the number of bits set within the word."

[I''ll refer to the ''32-bit word'' as a DWORD]

First, literally taking the problem text, it means that if the DWORD has ''k'' bits set, then the running/execution time is exactly O(k) .. meaning O(1) * k ..

Secondly, they say "proportional"..

The answer, I would say, goes something like this {other variations certainly exist):

DWORD answer(DWORD d)
{

DWORD d2 = d;

// If a bit is set, shift right until it''s gone..
while(d2)
{
while(d2 % 2 == 0) d2 >>= 1; // Shift Right While LSB is 0
d2 >>= 1; // Shift Right to remove ''1'' bit
}
// Return value of 32-bit word .. same as input!
return(d);

}

// CHRIS

Thanks guys. I get it now.

Cheers


Lord[BRIT]