Re: Efficient Bit Vector Manipulation.

[Stefan.Lucks@uni-weimar.de]

[-- Attachment #1: Type: TEXT/PLAIN, Size: 1546 bytes --]

On Fri, 15 May 2015, Vincent wrote:

> I need to extract in a very efficient way, information from the bit 
> sequence that represents a 32 bits Positive number, named I > 0.

A good way to represent a 32-bit Positive number may be

   type Int is mod 2**32;

> - find the length of the bit sequence, i.e. the number of bits a given 
[...]
> 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.

The following should give you the k you ask for:

   type Position_Type is range 0 .. 32;

    function Significant_Bits(I: Int) return Position_Type is
       Result: Position_Type := 0;
       Value:  Int := I;
    begin
       while Value > 1 loop
 	 Result := Result + 1;
 	 Value := Value / 2;
       end loop;
       return Result;
    end Significant_Bits;

> 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

This looks like a homework problem -- so I will not give you a complete 
solution. But the above should give you a good start.


Stefan.

------  I  love  the  taste  of  Cryptanalysis  in  the morning!  ------
uni-weimar.de/de/medien/professuren/mediensicherheit/people/stefan-lucks
--Stefan.Lucks (at) uni-weimar.de, Bauhaus-Universität Weimar, Germany--