Re: Efficient Bit Vector Manipulation.

[Niklas Holsti <niklas.holsti@tidorum.invalid>]

On 15-05-15 15:07 , Vincent wrote:
> Hello Ada language experts,
>
> I need to extract in a very efficient way, information from the bit
> sequence that represents a 32 bits Positive number, named I > 0.
>
> What i would like to do is :
>
> - find the length of the bit sequence, i.e. the number of bits a
> given value of I needs to be represented properly as a binary number.
> This can be computed by taking the first non zero bit starting from
> the MSB of I.

Very well-known problem... see

http://en.wikipedia.org/wiki/Find_first_set

and

http://graphics.stanford.edu/~seander/bithacks.html

The latter page gives C code, which should be easy to translate to Ada 
using the modular types from Interfaces and their shift operations.

Same suggestion for the rest of your questions: use modular types, 
shifts and masks.

I doubt that any compiler provides good optimization of such operations 
on Boolean arrays, even if packed to one bit per element. Anyway, the 
Ada RM does not define in which order the bits are indexed, so code 
using Boolean arrays would be unportable if it uses Unchecked_Conversion 
to converts between integers and arrays.

-- 
Niklas Holsti
Tidorum Ltd
niklas holsti tidorum fi
       .      @       .