Re: Efficient Bit Vector Manipulation.

[vincent.diemunsch@gmail.com]

Le vendredi 15 mai 2015 18:25:59 UTC+2, Niklas Holsti a écrit :

> 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.

Thank you very much Niklas, there is all I need here for finding the first 1 bit !
 
> 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.

So there is a need for an optimized Bit Vector package based on packed 
boolean arrays, and implemented both as shifts for portability and as
assembly instructions for the most common machines.

Kind regards,

Vincent