From mboxrd@z Thu Jan 1 00:00:00 1970 Path: news.gmane.org!not-for-mail From: Mark Oteiza Newsgroups: gmane.emacs.bugs Subject: bug#22689: 25.1.50; implement logcount Date: Mon, 15 Feb 2016 18:18:56 -0500 Message-ID: <87h9h9pnof.fsf@udel.edu> NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Trace: ger.gmane.org 1455578421 26463 80.91.229.3 (15 Feb 2016 23:20:21 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Mon, 15 Feb 2016 23:20:21 +0000 (UTC) To: 22689@debbugs.gnu.org Original-X-From: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Tue Feb 16 00:20:11 2016 Return-path: Envelope-to: geb-bug-gnu-emacs@m.gmane.org Original-Received: from lists.gnu.org ([208.118.235.17]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1aVSR8-0006NB-4P for geb-bug-gnu-emacs@m.gmane.org; Tue, 16 Feb 2016 00:20:10 +0100 Original-Received: from localhost ([::1]:37183 helo=lists.gnu.org) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSR7-0001mF-C5 for geb-bug-gnu-emacs@m.gmane.org; Mon, 15 Feb 2016 18:20:09 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:60166) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSR3-0001ke-5m for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:20:06 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aVSQz-0006C2-TD for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:20:05 -0500 Original-Received: from debbugs.gnu.org ([208.118.235.43]:49791) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQz-0006By-Pk for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:20:01 -0500 Original-Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84) (envelope-from ) id 1aVSQz-0008Oe-MF for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:20:01 -0500 X-Loop: help-debbugs@gnu.org Resent-From: Mark Oteiza Original-Sender: "Debbugs-submit" Resent-CC: bug-gnu-emacs@gnu.org Resent-Date: Mon, 15 Feb 2016 23:20:01 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: report 22689 X-GNU-PR-Package: emacs X-GNU-PR-Keywords: X-Debbugs-Original-To: bug-gnu-emacs@gnu.org Original-Received: via spool by submit@debbugs.gnu.org id=B.145557835332210 (code B ref -1); Mon, 15 Feb 2016 23:20:01 +0000 Original-Received: (at submit) by debbugs.gnu.org; 15 Feb 2016 23:19:13 +0000 Original-Received: from localhost ([127.0.0.1]:40566 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84) (envelope-from ) id 1aVSQD-0008NS-HR for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:13 -0500 Original-Received: from eggs.gnu.org ([208.118.235.92]:40779) by debbugs.gnu.org with esmtp (Exim 4.84) (envelope-from ) id 1aVSQB-0008NB-Sc for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:12 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aVSQ5-00064m-Or for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:06 -0500 Original-Received: from lists.gnu.org ([2001:4830:134:3::11]:37116) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQ5-00064i-Ln for submit@debbugs.gnu.org; Mon, 15 Feb 2016 18:19:05 -0500 Original-Received: from eggs.gnu.org ([2001:4830:134:3::10]:59975) by lists.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQ4-0001g8-EV for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:19:05 -0500 Original-Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1aVSQ1-000643-5r for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:19:04 -0500 Original-Received: from mail-yw0-x235.google.com ([2607:f8b0:4002:c05::235]:36784) by eggs.gnu.org with esmtp (Exim 4.71) (envelope-from ) id 1aVSQ1-00063u-0m for bug-gnu-emacs@gnu.org; Mon, 15 Feb 2016 18:19:01 -0500 Original-Received: by mail-yw0-x235.google.com with SMTP id e63so31303077ywc.3 for ; Mon, 15 Feb 2016 15:19:00 -0800 (PST) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=udel-edu.20150623.gappssmtp.com; s=20150623; h=from:to:subject:date:message-id:mime-version:content-type :content-transfer-encoding; bh=52gCL3e7IlJbAv1MYrZyoaeaF+irVjw73tKxYcTR9es=; b=OFjf/5BBgt7Sltmqdo1zJhMzqTA+HRUIktOly+Ceso5wLFXo0cdwnPXFAeJMIKSrzj vTB0cAq1qufv+Q/mZ4+wbab5PiPon2618gw5YK8cClma3Hi+4zQYuxKseTqcFM4sQD/D WQ/QDS8clxJtM2oZg5KsDZhh+LdB3dZGoaNNVEIQxKHbVyljTLN1XGxEU7TWg01tJw95 hfbEhQZgXM+JdSMoY4o0ogap2YBf4LHy1/+8ZzHJOEON2fZaQ2Jk+IL/+bk9rNpgCeoC 4snSY8oxnuZBE0YDKhzdmdywe08jDDOpCbD8RACiZK3jz1B10WBUC6G/Gub84l0yI8pr tXbg== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:from:to:subject:date:message-id:mime-version :content-type:content-transfer-encoding; bh=52gCL3e7IlJbAv1MYrZyoaeaF+irVjw73tKxYcTR9es=; b=J7I1zZUASw7O70XCu9tLNqUC0PKrNEE+D/w4F4Zb/WP2rxxWgYgesNk8DPo5/kL8EH cq+Dfo0hpMCFPHdwGrok7yxinEMKcVxdh7vj6kWTsGCoLXb4KK6ZpM95bWDgUmsLIol+ EVf2Ti7OvDcX+XzZRzPMId6aWQ8XVoIlb520/H+o520FxP0uDAemH+TVNhOIwyJkkYC9 aGTRQ//QA44C0+TRbEtW+tp0Gpa5fvccd6hweAkKTtoDvhbFLPiIAlNJWIrT/TrxM9KN WT1dTvyHuza0UT9J3xlUV0R42hzkgtleD9wQywKRes9ENh7cZaHG7Cr75H2s9D8YaUcE 0XCA== X-Gm-Message-State: AG10YORgbMHPCMbyCJsjW0yqSurmbpyFPOwmV13y79QoMkCXbPvB8SZGyhXGE5GlmqyP+NNk X-Received: by 10.13.250.196 with SMTP id k187mr11854036ywf.23.1455578340076; Mon, 15 Feb 2016 15:19:00 -0800 (PST) Original-Received: from holos.localdomain (pool-96-227-83-242.phlapa.fios.verizon.net. [96.227.83.242]) by smtp.gmail.com with ESMTPSA id e4sm22369840ywb.0.2016.02.15.15.18.58 for (version=TLS1_2 cipher=ECDHE-RSA-AES128-GCM-SHA256 bits=128/128); Mon, 15 Feb 2016 15:18:58 -0800 (PST) Original-Received: by holos.localdomain (Postfix, from userid 1000) id 3CF3F696ED; Mon, 15 Feb 2016 18:18:57 -0500 (EST) X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.6.x X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-detected-operating-system: by eggs.gnu.org: GNU/Linux 2.2.x-3.x [generic] X-Received-From: 208.118.235.43 X-BeenThere: bug-gnu-emacs@gnu.org List-Id: "Bug reports for GNU Emacs, the Swiss army knife of text editors" List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Original-Sender: bug-gnu-emacs-bounces+geb-bug-gnu-emacs=m.gmane.org@gnu.org Xref: news.gmane.org gmane.emacs.bugs:113101 Archived-At: 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=C3=AFvely 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.