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>
Subject: bug#22689: closed (Re: bug#22689: [PATCH] Add logcount)
Date: Sat, 30 Sep 2017 18:19:02 +0000

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

Your bug report

#22689: 25.1.50; implement logcount

which was filed against the emacs package, has been closed.

The explanation is attached below, along with your original report.
If you require more details, please reply to 22689 <at> debbugs.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: 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.

[Message part 3 (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.

Previous Next

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