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,FREEMAIL_FROM autolearn=unavailable autolearn_force=no version=3.4.4 X-Received: by 10.66.224.73 with SMTP id ra9mr20262096pac.9.1431777481854; Sat, 16 May 2015 04:58:01 -0700 (PDT) X-Received: by 10.140.23.50 with SMTP id 47mr235404qgo.24.1431777481798; Sat, 16 May 2015 04:58:01 -0700 (PDT) Path: buffer1.nntp.dca1.giganews.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!j8no2605203igd.0!news-out.google.com!k20ni19943qgd.0!nntp.google.com!z60no1013875qgd.0!postnews.google.com!glegroupsg2000goo.googlegroups.com!not-for-mail Newsgroups: comp.lang.ada Date: Sat, 16 May 2015 04:58:01 -0700 (PDT) In-Reply-To: Complaints-To: groups-abuse@google.com Injection-Info: glegroupsg2000goo.googlegroups.com; posting-host=87.91.37.131; posting-account=hya6vwoAAADTA0O27Aq3u6Su3lQKpSMz NNTP-Posting-Host: 87.91.37.131 References: <62605fe5-6ecf-4750-b13c-24bce65e3439@googlegroups.com> User-Agent: G2/1.0 MIME-Version: 1.0 Message-ID: Subject: Re: Efficient Bit Vector Manipulation. From: vincent.diemunsch@gmail.com Injection-Date: Sat, 16 May 2015 11:58:01 +0000 Content-Type: text/plain; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable Xref: number.nntp.giganews.com comp.lang.ada:193200 Date: 2015-05-16T04:58:01-07:00 List-Id: Le vendredi 15 mai 2015 18:25:59 UTC+2, Niklas Holsti a =E9crit=A0: > Very well-known problem... see > http://en.wikipedia.org/wiki/Find_first_set > and > http://graphics.stanford.edu/~seander/bithacks.html >=20 > The latter page gives C code, which should be easy to translate to Ada=20 > 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 ! =20 > Same suggestion for the rest of your questions: use modular types,=20 > shifts and masks. >=20 > I doubt that any compiler provides good optimization of such operations= =20 > on Boolean arrays, even if packed to one bit per element. Anyway, the=20 > Ada RM does not define in which order the bits are indexed, so code=20 > using Boolean arrays would be unportable if it uses Unchecked_Conversion= =20 > to converts between integers and arrays. So there is a need for an optimized Bit Vector package based on packed=20 boolean arrays, and implemented both as shifts for portability and as assembly instructions for the most common machines. Kind regards, Vincent