GNU bug report logs - #22689
25.1.50; implement logcount

Previous Next

Full log

View this message in rfc822 format

From: help-debbugs <at> gnu.org (GNU bug Tracking System)
To: Mark Oteiza <mvoteiza <at> udel.edu>
Cc: tracker <at> debbugs.gnu.org
Subject: bug#22689: closed (25.1.50; implement logcount)
Date: Sat, 30 Sep 2017 18:19:01 +0000

[Message part 1 (text/plain, inline)]

Your message dated Sat, 30 Sep 2017 14:18:07 -0400
with message-id <20170930181807.4eviiyvlxchp4oph <at> logos.localdomain>
and subject line Re: bug#22689: [PATCH] Add logcount
has caused the debbugs.gnu.org bug report #22689,
regarding 25.1.50; implement logcount
to be marked as done.

(If you believe you have received this mail in error, please contact
help-debbugs <at> gnu.org.)


-- 
22689: http://debbugs.gnu.org/cgi/bugreport.cgi?bug=22689
GNU Bug Tracking System
Contact help-debbugs <at> gnu.org with problems

[Message part 2 (message/rfc822, inline)]

From: Mark Oteiza <mvoteiza <at> udel.edu>
To: bug-gnu-emacs <at> gnu.org
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.

[Message part 3 (message/rfc822, inline)]

From: Mark Oteiza <mvoteiza <at> udel.edu>
To: Eli Zaretskii <eliz <at> gnu.org>
Cc: 22689-done <at> debbugs.gnu.org
Subject: Re: bug#22689: [PATCH] Add logcount
Date: Sat, 30 Sep 2017 14:18:07 -0400

On 30/09/17 at 08:53pm, Eli Zaretskii wrote:
> > Date: Sat, 30 Sep 2017 13:07:58 -0400
> > From: Mark Oteiza <mvoteiza <at> udel.edu>
> > Cc: 22689 <at> debbugs.gnu.org
> > 
> > Ok.  Patch including this, Benjamin's catch, and documentation.
> 
> Thanks.  A minor comment on the docs:
> 
> > +@defun 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.

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.