25,161
edits
Changes
no edit summary
<span id="HAKMEM169"></span>
==HAKMEM 169==
A similar technique was proposed by [[Bill Gosper]] et al. from [[Massachusetts Institute of Technology]], as published 1972 in [https://en.wikipedia.org/wiki/HAKMEM Memo 239 (HAKMEM)] <ref>[http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 HAKMEM - ITEM 169 To count the ones in a PDP-6/10 word] (in order of one-ups-manship: [[Bill Gosper|Gosper]], Mann, Lenard, [Root and Mann])</ref> <ref>[http://www.cl.cam.ac.uk/~am21/hakmemc.html HAKMEMC -- HAKMEM Programming hacks in C] by [http://www.cl.cam.ac.uk/~am21/ Alan Mycroft]</ref>, to add bit-trio- rather than duo populations consecutively, and the 32 bit version relies on casting out 63. Note that the constants in the code below have [https://en.wikipedia.org/wiki/Octal octal] (base-8) digits, originally written in [[Assembly#HAKMEM169|Assembly]] for the [[PDP-6]] <ref>[[Bill Gosper#HAKMEM169|HAKMEM 169]] for [[PDP-6]]/[[PDP-10]] 36-bit words</ref>. An expanded 64-bit version, casting out 511 or 4095, is slightly less efficient than the binary SWAR version above.
<pre>
int hakmem169_32(unsigned int x) {
* [[Mathematician#MVWilkes|Maurice Wilkes]], [[Mathematician#DJWheeler|David Wheeler]], [https://en.wikipedia.org/wiki/Stanley_Gill Stanley Gill] ('''1957'''). ''The Preparation of Programs for an Electronic Digital Computer''. Addison-Wesley Press; 2nd edition, [http://www.amazon.com/preparation-programs-electronic-Addison-Wesley-mathematics/dp/B0006AV1QQ amazon.com], [[Mathematician#DBGillies|Donald B. Gillies]] and [https://en.wikipedia.org/wiki/J._C._P._Miller Jeffrey C. P. Miller] on [[Population Count#SWARPopcount|SWAR-Popcount]], pages 191–193
* [[Mathematician#PWegner|Peter Wegner]] ('''1960'''). ''A technique for counting ones in a binary computer''. [[ACM#Communications|Communications of the ACM]], [http://www.informatik.uni-trier.de/~ley/db/journals/cacm/cacm3.html#Wegner60 Volume 3, 1960]
* Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[https://dspace.mit.edu/handle/1721.1/6086 HAKMEM]'', Memo 239, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology]]
* [[Mathematician#DAWagner|David A. Wagner]], [[Steven M. Bellovin]] ('''1994'''). ''[http://academiccommons.columbia.edu/catalog/ac:127097 A Programmable Plaintext Recognizer]''. <ref>[http://cryptome.org/jya/sadd.htm Sideways Add / Population Count] by [http://www.couperus.org/ Jitze Couperus] and [[Steven M. Bellovin|Steve Bellovin]] et al., [https://en.wikipedia.org/wiki/C2Net cryptography@c2.net], January 28, 1999</ref>
==2000 ...==
* [http://www.crazyontap.com/topic.php?TopicId=43382 Crazy On Tap - Secret Opcodes] <ref>[https://en.wikipedia.org/wiki/National_Security_Agency National Security Agency from Wikipedia]</ref>
* [http://kent-vandervelden.blogspot.com/2009/10/counting-bits-population-count-and.html Blender: POPCNT for counting bits]
* [http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item169 HAKMEM - ITEM 169 To count the ones in a PDP-6/10 word] (in order of one-ups-manship: [[Bill Gosper|Gosper]], Mann, Lenard, [Root and Mann]) <ref>Michael Beeler, [[Bill Gosper]] and [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[http://home.pipeline.com/~hbaker1/hakmem/hakmem.html HAKMEM]'', Memo 239, Artificial Intelligence Laboratory, [[Massachusetts Institute of Technology]], made Web-available by [http://home.pipeline.com/~hbaker1/ Henry Baker]</ref>: [http://www.cl.cam.ac.uk/~am21/hakmemc.html HAKMEMC -- HAKMEM Programming hacks in C] by [http://www.cl.cam.ac.uk/~am21/ Alan Mycroft]
* [http://www.hackersdelight.org/hdcodetxt/pop.c.txt popcount] [[C]] samples from [[Henry S. Warren, Jr.]] ('''2002, 2012'''). ''[[Henry S. Warren, Jr.#HackersDeligh|Hacker's Delight]]''. [https://en.wikipedia.org/wiki/Addison%E2%80%93Wesley Addison-Wesley]
* [http://aggregate.org/MAGIC/#Population%20Count%20%28Ones%20Count The Aggregate Magic Algorithms -Population Count (Ones Count)] by [[Hank Dietz]]
