25,161
edits
Changes
no edit summary
* [https://en.wikipedia.org/wiki/Fredkin_gate Fredkin gate] by [[Edward Fredkin]]
* [[Hyperbola Quintessence]].
* [[Subtracting a rook Rook from a blocking pieceBlocking Piece|o^(o-2r)]].
* [[Robert Hyatt|Robert Hyatt's]] approach of a [[Shared Hash Table#Lockless|lockless transposition table]]
* [[General Setwise Operations#SwappingBits|Swapping Bits]].
'''x86-mnemonics''' <br/>
[[x86]] has general purpose instruction instructions, [[BMI2]] general purpose instructions not affecting processor flags, as well as [[SIMD and SWAR Techniques|SIMD-instructions]] for various shifts:
<pre>
shr rax, cl ; rax >>= cl
shl rax, cl ; rax <<= cl
shrx r64a, r/m64, r64b; BMI2 r64a = r/m64 >> r64b
shlx r64a, r/m64, r64b; BMI2 r64a = r/m64 << r64b
psrlq mm0, mm1 ; MMX mm0 >>= mm1
psllq mm0, mm1 ; MMX mm0 <<= mm1
</pre>
'''Reset''' <br/>
<span id="ResetBit"></span>Reset a bit of square-index by [[General Setwise Operations#RelativeComplement|relative complement]] of the single bit.,
<pre>
x &= ~singleBitset; // reset bit
</pre>
or conditional toggle by single bit intersection
<pre>
x ^= singleBitset & x; // reset bit
</pre>
Set and toggle (or, xor) might the faster way to reset a bit inside a register (not, and).
'''x86-Instructions''' <br/>
[[x86]] processor provides a bit-test instruction family (bt, bts, btr, btc) with 32- and 64-bit operands. They may be used implicitly by compiler optimization or explicitly by inline assembler or compiler intrinsics. Take care that they are applied on local variables likely registers rather than memory references<ref>[https://groups.google.com/forum/#!topic/fishcooking/TplkvO62I9U On the speed of SquareBB array] by protonspring, [[Computer Chess Forums|FishCooking]], March 22, 2019</ref>:
* [[x86-64#gpinstructions|_bittest64]]
* [[x86-64#gpinstructions|_bittestandset64]]
<span id="ArithmeticalOperations"></span>
=Arithmetic Operations=
At the first glance, [https://en.wikipedia.org/wiki/Arithmetic#Arithmetic_operations arithmetic operations], that is [https://en.wikipedia.org/wiki/Addition addition], [https://en.wikipedia.org/wiki/Subtraction subtraction], [https://en.wikipedia.org/wiki/Multiplication multiplication] and [https://en.wikipedia.org/wiki/Division_%28mathematics%29 division], doesn't make much sense with bitboards. Still, there are some [[Bit-Twiddling|bit-twiddling]] applications related to least significant one bit (LS1B), to [[Traversing Subsets of a Set|enumerate all subsets of a set]] or [[Subtracting a rook Rook from a blocking pieceBlocking Piece|sliding attack generation]]. Multiplication of certain pattern has some applications as well, most likely to calculate hash-indicies of [[Occupancy of any Line#Multiplication|masked occupancies]].
==Derived from Bitwise==
<span id="Subtraction"></span>
==Subtraction==
[https://en.wikipedia.org/wiki/Subtraction Subtraction] (like xor) might be used to implement the [[General Setwise Operations#RelativeComplement|relative complement]], of a [https://en.wikipedia.org/wiki/Subset subset] inside it's superset. As mentioned, subtraction may be useful in calculating [[Subtracting a rook Rook from a blocking pieceBlocking Piece|sliding attacks]].
'''x86-mnemonics''' <br/>
* [[Mathematician#Venn|John Venn]] ('''1880'''). ''[http://www.tandfonline.com/doi/abs/10.1080/14786448008626877#.U3kRnHYfwgI On the Diagrammatic and Mechanical Representation of Propositions and Reasonings]''. [https://en.wikipedia.org/wiki/Philosophical_Magazine Philosophical Magazine], Vol. 9, No. 5
* [[Mathematician#Venn|John Venn]] ('''1881'''). ''[https://archive.org/details/symboliclogic00venniala Symbolic Logic]''. MacMillan & Co.
==1900 ...==
* [[Claude Shannon]] ('''1938'''). ''[https://en.wikipedia.org/wiki/A_Symbolic_Analysis_of_Relay_and_Switching_Circuits A Symbolic Analysis of Relay and Switching Circuits]''. [https://en.wikipedia.org/wiki/American_Institute_of_Electrical_Engineers Transactions of the AIEE], Vol. 57, No 12, Master's thesis 1940, [[Massachusetts Institute of Technology]]
* [[Mathematician#VIShestakov|Victor I. Shestakov]] ('''1941'''). ''Algebra of Two Poles Schemata''. [https://en.wikipedia.org/wiki/Automation_and_Remote_Control Automatics and Telemechanics], Vol. 5, No 2
==1950 ...==
* [https://en.wikipedia.org/wiki/Lazar_Lyusternik [Mathematician#LLyusternik|Lazar A. Lyusternik]], [http://www.mathnet.ru/php/person.phtml?personid=30351&option_lang=eng [Mathematician#AAbramov|Aleksandr A. Abramov]], [https://en.wikipedia.org/wiki/Victor_Shestakov [Mathematician#VIShestakov|Victor I. Shestakov]], [[Mikhail R. Shura-Bura]] ('''1952'''). ''Programming for High-Speed Electronic Computers''. (Программирование для электронных счетных машин)
* [[Christopher Strachey]] ('''1961'''). ''Bitwise operations''. [[ACM#Communications|Communications of the ACM]], Vol. 4, No. 3
==2000 ...==
* [[Henry S. Warren, Jr.]] ('''2002, 2012'''). ''[[Henry S. Warren, Jr.#HackersDelight|Hacker's Delight]]''. [https://en.wikipedia.org/wiki/Addison%E2%80%93Wesley Addison-Wesley]
* [[Donald Knuth]] ('''2009'''). ''[http://www-cs-faculty.stanford.edu/%7Eknuth/taocp.html The Art of Computer Programming], Volume 4, Fascicle 1: Bitwise tricks & techniques'', as [http://www-cs-faculty.stanford.edu/%7Eknuth/fasc1a.ps.gz Pre-Fascicle 1a postscript]
* [[Ronald L. Rivest]] ('''2011'''). ''The invertibility of the XOR of rotations of a binary word''. [https://dblp1.uni-trier.de/db/journals/ijcm/ijcm88.html International Journal of Computer Mathematics, Vol. 88], [https://pdfs.semanticscholar.org/8177/7b0bb30aa7ca12f9a1aea57691a6fb1e1249.pdf 2009 pdf preprint]
=Forum Posts=
==2000 ...==
* [https://www.stmintz.com/ccc/index.php?id=306882 curiosity killed the cat... hi/lo bit C verses Assembly] by [[Dann Corbit]], [[CCC]], July 17, 2003
* [https://www.stmintz.com/ccc/index.php?id=450730 mask of highest bit] by [[Andrew Shapira]], [[CCC]], September 21, 2005
==2010 ...==
* [http://www.talkchess.com/forum/viewtopic.php?t=47710 How to Shift Left (by) a Negative Number??] by [[Steve Maughan]], [[CCC]], April 05, 2013
* [http://www.open-chess.org/viewtopic.php?f=5&t=2878 To shift or not to shift] by thevinenator, [[Computer Chess Forums|OpenChess Forum]], September 09, 2015» [[Space-Time Tradeoff]]* [https://groups.google.com/d/msg/fishcooking/r_7TSUtNXls/PUM5JgcSFQAJ Question about resetting a bit in a bitboard corresponding to a given square] by guenther, [[Computer Chess Forums|FishCooking]], September 09, 2016 » [[#ResetBit|Reset Bit]]* [https://groups.google.com/forum/#!topic/fishcooking/TplkvO62I9U On the speed of SquareBB array] by protonspring, [[Computer Chess Forums|FishCooking]], March 22, 2019==2020 ...==* [http://www.talkchess.com/forum3/viewtopic.php?f=7&t=75818 C++20 standard bit operations] by [[Jon Dart]], [[CCC]], November 15, 2020 » [[Population Count]], [[BitScan]], [[Cpp|C++]]
=External Links=
