--- Begin Message ---
|
Subject: |
25.1.50; implement logcount |
|
Date: |
Mon, 15 Feb 2016 18:18:56 -0500 |
Wishlist:
Logcount, AKA popcount, Hamming weight, sideways sum. Basically,
counting the number of 1s in a number's binary representation. The
concept is similar to that in `bool-vector-count-population', except the
argument would be a number, presumably a non-negative integer.
There are a number of ways to go about it, and beyond that I'm not sure
how to write it into data.c:
- Some compilers have a __builtin_popcount (gcc since 2004 and llvm
since 2005)
- gmp has a popcount function
- lots of algorithms implementing it
Many are given here:
https://en.wikipedia.org/wiki/Hamming_weight
another resource:
http://rosettacode.org/wiki/Population_count
Guile's implementation uses table lookup:
http://git.savannah.gnu.org/cgit/guile.git/tree/libguile/numbers.c#n5234
When I needed it, I just naïvely ported an algorithm to elisp (in
particular ignoring the case of negative numbers):
(let ((m1 #x555555555555555)
(m2 #x333333333333333)
(m4 #x0f0f0f0f0f0f0f0f)
(h01 #x0101010101010101))
(setq x (- x (logand (lsh x -1) m1)))
(setq x (+ (logand x m2) (logand (lsh x -2) m2)))
(setq x (logand (+ x (lsh x -4)) m4))
(lsh (* x h01) -56))
The table lookup isn't so different
(defvar logtab [0 1 1 2 1 2 2 3 1 2 2 3 2 3 3 4])
(let ((count 0))
(while (not (zerop x))
(setq count (+ count (aref logtab (logand 15 x))))
(setq x (lsh x -4)))
count)
I couldn't find any implementation of this in calc either, but such a
function/operation would fit in calc-bin.
--- End Message ---
--- Begin Message ---
|
Subject: |
Re: bug#22689: [PATCH] Add logcount |
|
Date: |
Sat, 30 Sep 2017 14:18:07 -0400 |
|
User-agent: |
NeoMutt/20170912-48-0df7d3-dirty |
On 30/09/17 at 08:53pm, Eli Zaretskii wrote:
> > Date: Sat, 30 Sep 2017 13:07:58 -0400
> > From: Mark Oteiza <address@hidden>
> > Cc: address@hidden
> >
> > Ok. Patch including this, Benjamin's catch, and documentation.
>
> Thanks. A minor comment on the docs:
>
> > address@hidden logcount integer
> > +This function returns the population count of @var{integer}: the
> > +number of ones in the binary representation of @var{integer}.
>
> I would mention here the "Hamming weight" term (in @dfn) that is
> referenced in NEWS, and I would also add a few index entries:
>
> @cindex popcount
> @cindex Hamming weight
> @cindex counting set bits
Done, pushed as 185f3334. Thank you.
--- End Message ---