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.talkchess.com/forum/viewtopic.php?t=58230&start=3 Re: Linux Version of Maverick 1.5] by [[Michael Dvorkin]], [[CCC]], November 12, 2015 » [[Mac OS|OS X]], [[Maverick]]
* [http://www.talkchess.com/forum/viewtopic.php?t=61559 syzygy users (and Ronald)] by [[Robert Hyatt]], [[CCC]], September 29, 2016 » [[BitScan]]
==2020 ...==
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=74918 __builtin_popcountll doesn't bring any gain] by [[Oliver Brausch]], [[CCC]], August 28, 2020
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75818 C++20 standard bit operations] by [[Jon Dart]], [[CCC]], November 15, 2020 » [[General Setwise Operations]], [[BitScan]], [[Cpp|C++]]
=External Links=
* [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]]
* [https://github.com/kimwalisch/libpopcnt GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library] » [[Kim Walisch#PopCount|libpopcnt]] by [[Kim Walisch]]
* [https://en.wikipedia.org/wiki/Census Census from Wikipedia]
* [[Videos#JohnAbercrombie:Category:John Abercrombie|John Abercrombie]] 4tet - One, one, one + Spring song, [https://de.wikipedia.org/wiki/Subway_(Musikclub) Subway], [https://en.wikipedia.org/wiki/Cologne Cologne], April 12, 1999, [https://en.wikipedia.org/wiki/3sat 3sat] broadcast <ref>[https://de.wikipedia.org/wiki/Ali_Haurand Ali Haurand from Wikipedia.de] (German)</ref>, [https://en.wikipedia.org/wiki/YouTube YouTube] Video: [[Videos#JohnAbercrombie:Category:John Abercrombie|John Abercrombie]], [https://en.wikipedia.org/wiki/Bobo_Stenson Bobo Stenson], [[Videos#LarsDanielsson:Category:Lars Danielsson|Lars Danielsson]], [[Videos#JonChristensen:Category:Jon Christensen|Jon Christensen]]
: {{#evu:https://www.youtube.com/watch?v=pv5e6ZsFIBw|alignment=left|valignment=top}}
'''[[Bitboards|Up one Level]]'''
[[Category:John Abercrombie]]
[[Category:Jon Christensen]]
[[Category:Lars Danielsson]]
