From: Mark Oteiza <mvoteiza@udel.edu>
To: 22689@debbugs.gnu.org
Subject: bug#22689: 25.1.50; implement logcount
Date: Mon, 15 Feb 2016 18:18:56 -0500 [thread overview]
Message-ID: <87h9h9pnof.fsf@udel.edu> (raw)
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.
next reply other threads:[~2016-02-15 23:18 UTC|newest]
Thread overview: 16+ messages / expand[flat|nested] mbox.gz Atom feed top
2016-02-15 23:18 Mark Oteiza [this message]
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
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=87h9h9pnof.fsf@udel.edu \
--to=mvoteiza@udel.edu \
--cc=22689@debbugs.gnu.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
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.