[chbot] !!!!!!!! Choc fish challenge 2 !!!!!!!!!

[Michael Field]

It it Tuesday 10pm and nobody has answered?

I think function(x) returns the the first power of two that is greater 
than or equal to x.

It works because the first "shift and or"  propagates  the First Set Bit 
(FSB) to bit(FSB-1)
The second "shift and or" propagates bits(FSB) and bit(FSB-1) to 
bit(FSB-2) and and(FSB-3)
The third "shift and or" propagates bit(FSB) through bit(FSB-3) to 
bits(FSB-4) through bits(FSB-7)
.... and so on.

The "x--" at the start makes sure that it returns "greater than or equal 
to" x. If you remove it you get the first power of two greater than x. 
e.g. function(256) will return 512.

But I don't think it works if x > 2^31, as for f(0x80000001) the return 
value will be 0xFFFFFFFF+1 = 0 <?>.

Without the "x++" on the return it would be quite handy to light a 
string of LEDs to give a sort of give a log(2) signal level meter....

Mike





>  To make up for my massive blunder, I'll offer a replacement fish for an
>  explanation of what the following algorithm does. We'll go with the same
>  timeframe as before, and I'll endeavor not to reply myself.

>  unsigned int function(unsigned int x)
>  {
>   x--;
>   x |= x>>   1;
>   x |= x>>   2;
>   x |= x>>   4;
>   x |= x>>   8;
>   x |= x>>   16;
>   return x + 1;
>}