Path: csiph.com!newsfeed.hal-mli.net!feeder3.hal-mli.net!newsfeed.hal-mli.net!feeder1.hal-mli.net!feeder.erje.net!eu.feeder.erje.net!newsfeed.fsmpi.rwth-aachen.de!news-1.dfn.de!news.dfn.de!news.informatik.hu-berlin.de!fu-berlin.de!uni-berlin.de!individual.net!not-for-mail From: "osmium" Newsgroups: comp.programming Subject: Re: Fast counting of 1-bits of arbitrarily long bit sequences Date: Tue, 3 Dec 2013 10:16:22 -0600 Lines: 23 Message-ID: References: <7q9r99thnsln7i1d09evsdq4c80r4qrvd1@4ax.com> X-Trace: individual.net EpQf+016Tc8CjsWKQvPPuwhNpQcfg4qNAAAp7QDo1IjsQjesyn Cancel-Lock: sha1:/UWtbxf+Z6ujLXok0TkrESekjI4= X-Priority: 3 X-MSMail-Priority: Normal X-Newsreader: Microsoft Outlook Express 6.00.2900.2180 X-RFC2646: Format=Flowed; Original X-MimeOLE: Produced By Microsoft MimeOLE V6.00.2900.2180 Xref: csiph.com comp.programming:4021 "Robert Wessel" wrote: > On Mon, 02 Dec 2013 19:17:55 +0100, Mok-Kong Shen > wrote: > >> >>Given a n-bit sequence, one may be interested to determine the number >>of 1-bits in it. Decades ago, some computers, e.g. those from CDC, had >>an instruction delivering the bit count of a computer word, which was >>commonly believed to have been specially provided to facilitate some >>crypto studies. A fast software bit counting algorithm for n=32 in C is >>well-known. In the following is a Python code for arbitrary large >>values of n, based on the same idea. Hopefully it could be useful for >>some readers. > > > Many current machines have population count instructions, including > x86, zSeries, PPC/POWER, ARM... (Not all versions, of course). Is there any way to use those instructions in a high-level language such as C without resorting to assembly language?