Re: highest bit, statically determined

[Bill Findlay <yaldnif.w@blueyonder.co.uk>]

On 29/09/2012 19:57, in article CC8D0314.1E2CC%yaldnif.w@blueyonder.co.uk,
"Bill Findlay" <yaldnif.w@blueyonder.co.uk> wrote:

> On 29/09/2012 18:34, in article
> 50673111$0$9505$9b4e6d93@newsspool1.arcor-online.net, "Georg Bauhaus"
> <rm.dash-bauhaus@futureapps.de> wrote:
> 
>> Is there a shorter/better way of having the compiler
>> find the highest bit = 1 in a static numeric constant?
>> 
>> If N is such a constant, e.g. Some_Type'Last where
>> Some_Type'Size = 8 and its bound are static, then
>> 
>>     Highest_Bit_In_Octet : constant :=
>>       Natural'Max
>>       (8 * Boolean'Pos (N / 2**7 > 0),
>>        Natural'Max
>>        (7 * Boolean'Pos (N / 2**6 > 0),
>>         Natural'Max
>>         (6 * Boolean'Pos (N / 2**5 > 0),
>>          Natural'Max
>>          (5 * Boolean'Pos (N / 2**4 > 0),
>>           Natural'Max
>>           (4 * Boolean'Pos (N / 2**3 > 0),
>>            Natural'Max
>>            (3 * Boolean'Pos (N / 2**2 > 0),
>>             Natural'Max
>>             (2 * Boolean'Pos (N / 2**1 > 0),
>>              Natural'Max
>>              (1 * Boolean'Pos (N / 2**0 > 0), 0))))))));
> 
> In my experience that sort of code, applied in non-static cases, is less
> efficient than one would hope, and more obvious code works faster.
> 
> Something like the following can be readily extended to greater operand
> widths:
> 
>    function first_1_bit (y : octet)
>    return Natural is
>       x : octet;
>       r : Natural;
>    begin
>       if y = 0 then return 0; end if;
> 
>       if (y / 16) /= 0 then
>          r := 4; x := y / 16;
>       else
>          r := 0; x := y;
>       end if;
> 
>       if (x / 4) /= 0 then
>          r := r + 2; x := x / 4;
>       end if;
> 
>       if (x / 2) /= 0 then
>          r := r + 1;
>       end if;
> 
>       return r + 1;
>    end first_1_bit;
> 
> It looks fairly inline-able, and foldable for a static value of y.

I can now confirm that with GNAT GPL 2012 at -O3 it does inline and fold,
but I now see that you want the result to be static as well as the operand,
and this does not achieve that.

-- 
Bill Findlay
with blueyonder.co.uk;
use  surname & forename;