Re: Efficient Bit Vector Manipulation.

[robin.vowels@gmail.com]

On Friday, May 15, 2015 at 10:07:41 PM UTC+10, 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. Then, we call k = length( I ) - 1. k is the number of useful bits, i.e. the bits following the first 1.
> 
> For instance : 
>  - I = 1 is represented by 1 and k = 0.
>  - I = 2 is represented by 10 and k = 1.
>  - I = 3 is represented by 11 and k = 1.
>  - I = 4 is represented by 100 and k = 2. 
> 
> Then I would like to :
> - extract the b = floor(k/2) bits leading the first 1 starting from MSB and convert them to an integer : B
> - extract the remaining e = Ceiling (k/2) bits and convert them to an integer : E.
> 
> then I = 2^k + B * 2^b + E
> 
> How can I do that efficiently in Ada ? I mean I thought of using boolean arrays but will this
> be optimized by the compiler to CPU instructions ? I used to know how to do it in assembly langage on the Intel 386 but that seems not portable at all :-). Maybe I should use shifts. 
> 
> Any suggestion ?

In PL/I there are specific functions for extracting bits from an integer.
These include IAND (and there are others, probably not relevent here).
Shifting is performed by ISRL and ISLL.
All of these operations (and others) have direct CPU instructions.