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

Andre Renaud andre at bluewatersys.com
Tue Aug 2 20:26:19 BST 2011


Hi Mike,
That seems to be the correct answer, and you're right about the overflow. Although in those cases the answer is not representable in 32bits anyway, so no valid outcome would ever be possible. As you previously stated changing the return to uint64_t would fix that.

Chocolate fish to be arranged.

Regards,
Andre

On 2/08/2011, at 10:10 PM, Michael Field <hamster at snap.net.nz> wrote:

> 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;
>> }
> 
> 
> 
> 
> _______________________________________________
> Chchrobotics mailing list Chchrobotics at lists.linuxnut.co.nz
> http://lists.ourshack.com/mailman/listinfo/chchrobotics
> Mail Archives: http://lists.ourshack.com/pipermail/chchrobotics/
> Web site: http://kiwibots.org
> Meetings 3rd Monday each month at Tait Radio Communications, 175 Roydvale Ave, 6.30pm
> 
> When replying, please edit your Subject line to reflect new content.



More information about the Chchrobotics mailing list