all messages for Emacs-related lists mirrored at yhetil.org
 help / color / mirror / code / Atom feed
* bug#22689: 25.1.50; implement logcount
@ 2016-02-15 23:18 Mark Oteiza
  2017-09-29 17:41 ` bug#22689: [PATCH] Add logcount Mark Oteiza
  2017-09-30 22:48 ` Paul Eggert
  0 siblings, 2 replies; 16+ messages in thread
From: Mark Oteiza @ 2016-02-15 23:18 UTC (permalink / raw)
  To: 22689


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.





^ permalink raw reply	[flat|nested] 16+ messages in thread

end of thread, other threads:[~2017-09-30 23:22 UTC | newest]

Thread overview: 16+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2016-02-15 23:18 bug#22689: 25.1.50; implement logcount Mark Oteiza
2017-09-29 17:41 ` bug#22689: [PATCH] Add logcount Mark Oteiza
2017-09-30 11:42   ` Eli Zaretskii
2017-09-30 13:16     ` Mark Oteiza
2017-09-30 13:59       ` Eli Zaretskii
2017-09-30 14:55         ` Mark Oteiza
2017-09-30 15:38           ` Eli Zaretskii
2017-09-30 16:03             ` Mark Oteiza
2017-09-30 16:17               ` Eli Zaretskii
2017-09-30 17:07                 ` Mark Oteiza
2017-09-30 17:53                   ` Eli Zaretskii
2017-09-30 18:18                     ` Mark Oteiza
2017-09-30 16:50           ` Benjamin Riefenstahl
2017-09-30 16:59             ` Mark Oteiza
2017-09-30 22:48 ` Paul Eggert
2017-09-30 23:22   ` Mark Oteiza

Code repositories for project(s) associated with this external index

	https://git.savannah.gnu.org/cgit/emacs.git
	https://git.savannah.gnu.org/cgit/emacs/org-mode.git

This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.