From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00
	autolearn=unavailable autolearn_force=no version=3.4.4
Path: 
 eternal-september.org!reader01.eternal-september.org!reader02.eternal-september.org!news.eternal-september.org!mx02.eternal-september.org!feeder.eternal-september.org!news.swapon.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail
From: Niklas Holsti <niklas.holsti@tidorum.invalid>
Newsgroups: comp.lang.ada
Subject: Re: Efficient Bit Vector Manipulation.
Date: Fri, 15 May 2015 19:26:02 +0300
Organization: Tidorum Ltd
Message-ID: <crml0kFpmvdU1@mid.individual.net>
References: <62605fe5-6ecf-4750-b13c-24bce65e3439@googlegroups.com>
Mime-Version: 1.0
Content-Type: text/plain; charset=windows-1252; format=flowed
Content-Transfer-Encoding: 7bit
X-Trace: individual.net JxYsulgVS1DbhxmaiGqn4g5t+Y+Oh41/5umH8ZpAQFRbuWyZ9g
Cancel-Lock: sha1:3yEEXqek6NnKdDbqTdcW5kEOY7A=
User-Agent: Mozilla/5.0 (Macintosh; Intel Mac OS X 10.8;
 rv:31.0) Gecko/20100101 Thunderbird/31.6.0
In-Reply-To: <62605fe5-6ecf-4750-b13c-24bce65e3439@googlegroups.com>
Xref: news.eternal-september.org comp.lang.ada:25886
Date: 2015-05-15T19:26:02+03:00
List-Id: <comp.lang.ada>

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