[fpc-pascal] two small ?s - high(real) and nearest 2^x

[Matthias K.]

On Sat, Oct 10, 2009 at 9:09 PM, Aleksa Todorovic <alexione at gmail.com> wrote:
> On Sat, Oct 10, 2009 at 20:58, Matthias K. <makadev at googlemail.com> wrote:
>> On Sat, Oct 10, 2009 at 7:14 PM, David Emerson <dle3ab at angelbase.com> wrote:
>>> 2. For the purposes of reserving memory in block sizes that can be
>>> easily reallocated, I like to use powers of two. So if I have, e.g., a
>>> dynamic array, I might start with a size of 1024 and then double it
>>> when it hits capacity. Hopefully this smoothes memory management, as I
>>> am using a lot of memory...
>>>
>>> Anyway, what I'd like is a simple function that can quickly identify the
>>> next power-of-two larger than an arbitrary number. So if I feed the
>>> function 472, it will return 512. Thus far I haven't been able to
>>> figure out how to do this without a big if-then-else nest. Is there
>>> some clever way to request that the processor return the position of
>>> the leftmost '1' in 00101101?
>>
>> invalue := 412;
>> --
>> outvalue := 1;
>> while invalue <> 0 do
>> begin
>>  invalue := invalue div 2;
>>  outvalue := outvalue*2;
>> end;
>> --
>
> On x86 processors, there is bsr instruction which finds index of the
> most significant bit set. You just need some simple asm coding to use
> it.
>
Yes, the same thing can be written with 3 instructions (bsr, inc, shl)
for x86, but...

1. the code above is crossplattform compatible
2. with some size checks it can be assured, this code is only called
if "current arraysize < new array size". So with a starting size of
1024 = 2^10, you need to call this code at most 22 times to grow a
(4*SizeOf(array Element Type))GB array
3. the 22 times reallocation overhead is significant less performant..

so its a simple solution with benefits in compatibility