Changes

Jump to: navigation, search

Traversing Subsets of a Set

130 bytes added, 22:37, 11 April 2018
m
no edit summary
</pre>
We add the [[General Setwise Operations#TheLeastSignificantOneBitLS1B|LS1B]] (smallest) to the set, to get a greater number. The former LS1B becomes zero with overflow. If the next higher bit was zero, it takes the carry and the number of set bits didn't change - two flipped bits. Otherwise, if the carry ripples through, leaving further zero(s), we need to set least significant bits accordingly, to keep the cardinality equal. Thus, we xor ripple to get the flipped bits as ones. We shift this sequence right, until it becomes the least significant bits (divide by smallest). To take the two compensating bits off, we need to further divide by 4 (leading or trailing shift right 2). Get the next higher number with the same number of one bits (Snoob) was devised by [[Bill Gosper]] as [[Bill Gosper#HAKMEM175|HAKMEM 175]] in [[PDP-6]] [[Assembly]] <ref>Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[http://home.pipeline.com/~hbaker1/hakmem/hakmem.html HAKMEM]'', Memo 239, Artificial Intelligence Laboratory''. [https://en.wikipedia.org/wiki/MIT_Computer_Science_and_Artificial_Intelligence_Laboratory CSAIL], [[Massachusetts Institute of Technology|MIT]]</ref> and elaborated in [[Henry S. Warren, Jr.#HackersDeligh|Hacker's Delight]] by [[Henry S. Warren, Jr.]] <ref>[http://www.hackersdelight.org/basics1.pdf Sample section of Hacker's Delight, Chapter 2 Basics] (pdf) by [[Henry S. Warren, Jr.]] pp.14 Figure 2–1. ''Next higher number with same number of 1-bits''.</ref> <ref>[http://www.hackersdelight.org/hdcodetxt/snoob.c.txt C code for most of the programs that appear in HD | Fig. 2-1. Next higher number with same number of 1-bits]</ref>.
==<span id="NextSnoob"></span>Snoobing the Universe==
=Selected Publications=
* Michael Beeler, [[Bill Gosper]], [https://en.wikipedia.org/wiki/Richard_Schroeppel Rich Schroeppel] ('''1972'''). ''[http://home.pipeline.com/~hbaker1/hakmem/hakmem.html HAKMEM]'', Memo 239, Artificial Intelligence Laboratory''. [https://en.wikipedia.org/wiki/MIT_Computer_Science_and_Artificial_Intelligence_Laboratory CSAIL], [[Massachusetts Institute of Technology|MIT]], [http://home.pipeline.com/~hbaker1/hakmem/hacks.html#item175 ITEM 175 (Gosper)]
* [[Mathematician#FRuskey|Frank Ruskey]] ('''2003'''). ''Combinatorial Generation''. [https://en.wikipedia.org/wiki/University_of_Victoria University of Victoria], [http://www.1stworks.com/ref/ruskeycombgen.pdf pdf]
* [[Henry S. Warren, Jr.]] ('''2012'''). ''[http://hackersdelight.org/ Hacker's Delight, 2nd Edition]''. [https://en.wikipedia.org/wiki/Addison%E2%80%93Wesley Addison-Wesley]

Navigation menu