OpenEuphoria

Re: new new challenge

• Posted by rforno at tutopia.com Aug 20, 2001
• 461 views

You were really close to what I think is an unbeatable solution, namely:

function best(integer x)
    return xor_bits(x, and_bits(x, x - 1))
end function

The two functions may be reversed.

----- Original Message ----- 
From: <rossboyd at ihug.com.au>
To: "EUforum" <EUforum at topica.com>
Subject: Re: new new challenge


> 
> > This is a new and (I think) simpler challenge:
> > Find the fastest algorithm to compute the largest power of 2 that
> exactly
> > divides an integer from 1 to 2^31 - 1.
> 
> Hi,
> The solution boils down to finding the value of the least significant
> bit.
> Here are two alternatives... unfortunately the ugly one is faster.
> Ross
> 
> 
> -- This solution is elegant but slower due to the divide by 2.
> -- If Euphoria had a bit shift operator or integer division
> -- this would probably be the fastest method.
> 
> function best2(integer x)
>     if and_bits(x,1) then  -- quickly eliminate odd numbers
>         return 1
>     end if
>     return floor(xor_bits(x,x-1)/2) + 1
> end function
> 
> -- Cruder and faster solution...
> -- You could make it even faster by 'jumping' depending on the
> -- value of x and hence reduce the number of comparisons.
> -- But why bother... this method stinks already.
> function best(integer x)
>     if and_bits(x,1) then
>         return 1
>     end if
>     if and_bits(x,2) then
>         return 2
>     end if
>     if and_bits(x,4) then
>         return 4
>     end if
>     if and_bits(x,8) then
>         return 8
>     end if
>     if and_bits(x,16) then
>         return 16
>     end if
>     if and_bits(x,32) then
>         return 32
>     end if
>     if and_bits(x,64) then
>         return 64
>     end if
>     if and_bits(x,128) then
>         return 128
>     end if
>     if and_bits(x,256) then
>         return 256
>     end if
>     if and_bits(x,512) then
>         return 512
>     end if
>     if and_bits(x,1024) then
>         return 1024
>     end if
>     if and_bits(x,2048) then
>         return 2048
>     end if
>     if and_bits(x,4096) then
>         return 4096
>     end if
>     if and_bits(x,8192) then
>         return 8192
>     end if
>     if and_bits(x,16384) then
>         return 16384
>     end if
>     if and_bits(x,32768) then
>         return 32768
>     end if
>     if and_bits(x,65536) then
>         return 65536
>     end if
>     if and_bits(x,131072) then
>         return 131072
>     end if
>     if and_bits(x,262144) then
>         return 262144
>     end if
>     if and_bits(x,524288) then
>         return 524288
>     end if
>     if and_bits(x,1048576) then
>         return 1048576
>     end if
>     if and_bits(x,2097152) then
>         return 2097152
>     end if
>     if and_bits(x,4194304) then
>         return 4194304
>     end if
>     if and_bits(x,8388608) then
>         return 8388608
>     end if
<snip>

> 
>