Re: highest bit, statically determined

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

On 04/11/2012 20:45, in article op.wm9nx2i3ule2fv@cardamome, "Yannick
Duch�ne   (Hibou57)" <yannick_duchene@yahoo.fr> wrote:

> Le Sat, 29 Sep 2012 21:16:01 +0200, Bill Findlay
> <yaldnif.w@blueyonder.co.uk> a �crit:
> 
>> 
>> 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.
>> 
> 
> What means folding in this context?

Compile-time evaluation, so that the end result is a compile-time known
(I do not say static, as that is a term of art in Ada) value.

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