25,161
edits
Changes
no edit summary
}
</pre>
This is how the Carry-Rippler, introduced by [[Marcel van Kervinck]] <ref>[httphttps://groups.google.com/groupd/msg/rec.games.chess/msgKnJvBnhgDKU/f4f0751cc8b928c8 Re: move generators in computer chess, yCi5yBx18PQJ Tricky bit tricks] by [[Marcel van Kervinck]], [[Computer Chess Forums|rgccrec.games.chess]], October 20, 1994</ref> and later by [[Steffan Westcott]] <ref>[http://www.stmintz.com/ccc/index.php?id=490129 Re: algorithm question] by [[Steffan Westcott]], [[CCC]], February 27, 2006</ref> works: we first set all "unused" bits of the set by oring the One's Complement of d. The increment ripples a possible carry through all unused bits - and finally we clear all unused bits again by intersection with the set d:
<pre>
n = ((n | ~d) + 1) & d;
=See also=
* [[Bitboard Serialization]]
* [[De Bruijn sequenceSequence]]
* [[Magic Bitboards]]
* [http://groups.google.com/group/rec.games.chess/msg/f4f0751cc8b928c8 Re: move generators in computer chess, Tricky bit tricks] by [[Marcel van Kervinck]], [[Computer Chess Forums|rgcc]], October 20, 1994
* [http://www.stmintz.com/ccc/index.php?id=490129 Re: algorithm question] by [[Steffan Westcott]], [[CCC]], February 27, 2006
* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=73198 Don't understand CarryRippler] by [[Marcel Vanthoor]], [[CCC]], February 27, 2020 » [[#AllSubsetsofanySet|Carry-Rippler]], [[Rust]]
=External Links=
* [https://en.wikipedia.org/wiki/Partially_ordered_set Partially ordered set from Wikipedia]
* [https://en.wikipedia.org/wiki/Power_set Power set from Wikipedia]
=References=
<references />
'''[[Algorithms|Up one Level]]'''
