Changes

'''[[Main Page|Home]] * [[Board Representation]] * [[Bitboards]] * General Setwise Operations'''

'''General Setwise Operations''',<br/>

if (a != b) -> both sets are not equal

</pre>

[[x86]] has a cmp-instruction, which internally performs a subtraction to set its internal processor flags (carry, zero, overflow) accordantly, for instance the zero-flag if both sets are equal. Those flags are then used by conditional jump or move instructions.

<pre>

set-wise = {a1, b1, c1, d1, ....., e8, f8, g8, h8}

</pre>

</pre>

Programmers often wonder to use -1 in [[C]], [[Cpp|C++]] as unsigned constant. See [[General Setwise Operations#TheTwosComplement|The Two's Complement]] - alternately one may use ~0 to define the universal set. Since in [[C]] or [[Cpp|C++]], decimal numbers without ULL suffix are treated as 32-bit integers, constants outside the integer range need some care concerning sign or zero extension. Const declarations or using the [[Bitboards#DefiningBitboards|C64 Macro]] is recommended:

<pre>

<span id="Intersection"></span>

==Intersection==

In [https://en.wikipedia.org/wiki/Set_theory set theory] [https://en.wikipedia.org/wiki/Intersection_%28set_theory%29 intersection] is denoted as:

In [https://en.wikipedia.org/wiki/Boolean_algebra_%28logic%29 boolean algebra] [https://en.wikipedia.org/wiki/Logical_conjunction conjunction] is denoted as:

Bitboard intersection or conjunction is performed by [https://en.wikipedia.org/wiki/Bitwise_operation#AND bitwise and] (binary operator & in [[C]], [[Cpp|C++]] or [[Java]], and the keyword "AND" in [[Pascal]]).

intersection = a & b

Truth table of [https://en.wikipedia.org/wiki/AND_gate and] for one bit, for a '1' result both inputs need to be '1':

{| class="wikitable"

Conjunction acts like a bitwise minimum, min(a, b) or as bitwise multiplication (a * b).

[[x86]] has general purpose instruction as well as [[SIMD and SWAR Techniques|SIMD-instructions]] for bitwise and:

<pre>

vpand ymm0, ymm1, ymm2 ; AVX2 ymm0 = ymm1 & ymm2

</pre>

[[AVX-512]] has [[AVX-512#VPTERNLOG|VPTERNLOG]]

Conjunction is [https://en.wikipedia.org/wiki/Idempotence idempotent].

a & a == a

Conjunction is [https://en.wikipedia.org/wiki/Commutative commutative]

a & b == b & a

Conjunction is [https://en.wikipedia.org/wiki/Associative associative].

(a & b) & c == a & (b & c)

The intersection of two sets is [https://en.wikipedia.org/wiki/Subset subset] of both.

</pre>

<span id="DisjointSets"></span>

To test whether two sets are [https://en.wikipedia.org/wiki/Disjoint disjoint] - that is their intersection is empty - compiler emit the [[x86]] test-instruction instead of and. That saves the content of a register, if the intersection is not otherwise needed:

<pre>

<span id="Union"></span>

==Union==

In [https://en.wikipedia.org/wiki/Set_theory set theory] [https://en.wikipedia.org/wiki/Union_%28set_theory%29 union] is denoted as:

In [https://en.wikipedia.org/wiki/Boolean_algebra_%28logic%29 boolean algebra] [https://en.wikipedia.org/wiki/Logical_disjunction disjunction] is denoted as:

The union or disjunction of two bitboards is applied by [https://en.wikipedia.org/wiki/Bitwise_operation#OR bitwise or] (binary operator | in [[C]], [[Cpp|C++]] or [[Java]], or the keyword "OR" in [[Pascal]]). The union is superset of the [[General Setwise Operations#Intersection|intersection]], while the [[General Setwise Operations#Intersection|intersection]] is [https://en.wikipedia.org/wiki/Subset subset] of the union.

union = a | b

Truth table of [https://en.wikipedia.org/wiki/OR_gate or] for one bit, one set input bits is sufficient to set the output:

{| class="wikitable"

Disjunction acts like bitwise maximum, max(a, b) or as addition with saturation, min(a + b, 1). It can also be interpreted as sum minus product, a + b - a*b, with possible temporary overflow of one binary digit to two - or with modulo 2 arithmetic.

[[x86]] has general purpose instruction as well as [[SIMD and SWAR Techniques|SIMD-instructions]] for bitwise or:

<pre>

vpor ymm0, ymm1, ymm2 ; AVX2 ymm0 = ymm1 | ymm2

</pre>

Disjunction is [https://en.wikipedia.org/wiki/Idempotence idempotent].

a | a == a

Disjunction is [https://en.wikipedia.org/wiki/Commutative commutative]

a | b == b | a

Disjunction is [https://en.wikipedia.org/wiki/Associative associative].

(a | b) | c == a | (b | c)

<span id="DistributiveAndOr"></span>

Disjunction is [https://en.wikipedia.org/wiki/Distributivity distributive] over [[General Setwise Operations#Intersection|conjunction]] and vice versa:

x | (y & z) == (x | y) & (x | z)

x & (y | z) == (x & y) | (x & z)

The union of two sets is superset of both. For instance the union of all white and black pieces are the set of all occupied squares:

<pre>

<span id="ComplementSet"></span>

==Complement Set==

In [https://en.wikipedia.org/wiki/Set_theory set theory] [https://en.wikipedia.org/wiki/Complement_%28set_theory%29 complement set] is denoted as:

In [https://en.wikipedia.org/wiki/Boolean_algebra_%28logic%29 boolean algebra] [https://en.wikipedia.org/wiki/Negation negation] is denoted as:

The complement set (absolute complement set), negation or [https://en.wikipedia.org/wiki/Ones%27_complement#Ones.27_complement ones' complement] has it's equivalent in [https://en.wikipedia.org/wiki/Bitwise_operation#NOT bitwise not] (unary operator '~' in [[C]], [[Cpp|C++]] or [[Java]], or the keyword "NOT" in [[Pascal]]).

Truth table of [https://en.wikipedia.org/wiki/NOT_gate not] for one bit:

{| class="wikitable"

The complement can be interpreted as bitwise subtraction (1 - a).

Available as general purpose instruction.

not rax ; rax = ~rax

[[AVX-512]] has [[AVX-512#VPTERNLOG|VPTERNLOG]]

The set of empty squares for instance is the complement-set of all occupied squares and vice versa:

<pre>

!-1 == 0

<span id="Complementlaws"></span>

* The [[General Setwise Operations#Union|union]] of a set with it's complement is the universal set -1.

* The [[General Setwise Operations#Intersection|intersection]] of a set with it's complement is the empty set 0 - both are [https://en.wikipedia.org/wiki/Disjoint disjoint].

~(-1) == 0

<span id="DeMorganslaws"></span>

* Complement of [[General Setwise Operations#Union|union]] ([https://en.wikipedia.org/wiki/NOR_gate NOR] ) is the [[General Setwise Operations#Intersection|intersection]] of the complements <ref>[[Mathematician#ADeMorgan|Augustus De Morgan]] ('''1860'''). ''[http://books.google.com/books?id=Od3jgF5rZtgC Syllabus of a Proposed System of Logic]''. Walton & Malbery</ref>.

* Complement of [[General Setwise Operations#Intersection|intersection]] ([https://en.wikipedia.org/wiki/NAND_logic NAND] or [https://en.wikipedia.org/wiki/Sheffer_stroke Sheffer stroke] ) is the [[General Setwise Operations#Union|union]] of the complements.

<span id="RelativeComplement"></span>

==Relative Complement==

In [https://en.wikipedia.org/wiki/Set_theory set theory] [https://en.wikipedia.org/wiki/Complement_%28set_theory%29#Relative_complement relative complement] is denoted as:

The relative complement is the [[General Setwise Operations#ComplementSet|absolute complement]] restricted to some other set. The relative complement of 'a' inside 'b' is also known as the '''set theoretic difference''' of 'b' minus 'a'. It is the set of all elements that belong to 'b' but '''not''' to 'a'. Also called 'b' without 'a'. It is the [[General Setwise Operations#Intersection|intersection]] of 'b' with the absolute complement of 'a'.

not_a_in_b = ~a & b

b_without_a = b & ~a

Truth table of relative complement for one bit:

{| class="wikitable"

The relative complement of 'a' in 'b' may be interpreted as a bitwise (a < b) relation.

[[x86]] don't has an own general purpose instruction for relative complement, but [[x86-64]] expansion [[BMI1]], and [[SIMD and SWAR Techniques|SIMD-instructions]]:

<pre>

vpandn ymm0, ymm1, ymm2 ; AVX xmm0 = ~xmm1 & xmm2

</pre>

[[AVX-512]] has [[AVX-512#VPTERNLOG|VPTERNLOG]]

In presumption of [[General Setwise Operations#XorWithout|subtraction or exclusive or]] there are alternatives to calculate the relative complement - superset minus subset. We can take either the union without the complementing set - or the other set without the intersection

~a & b == ( a | b ) - a

==Implication==

Logical Implication or [https://en.wikipedia.org/wiki/Entailment Entailment] is denoted as:

The boolean [https://en.wikipedia.org/wiki/Material_conditional Material conditional] is denoted as:

Logical Implication or the boolean Material conditional 'a' implies 'b' (if 'a' then 'b') is an derived boolean operation, implemented as [[General Setwise Operations#Union|union]] of the [[General Setwise Operations#ComplementSet|absolute complement]] of 'a' with 'b':

a_implies_b == ~a | b

Implication may be interpreted as a bitwise (a <= b) relation.

<span id="ExclusiveOr"></span>

==Exclusive Or==

In [https://en.wikipedia.org/wiki/Set_theory set theory] [https://en.wikipedia.org/wiki/Symmetric_difference symmetric difference] is denoted as:

In [https://en.wikipedia.org/wiki/Boolean_algebra_%28logic%29 boolean algebra] [https://en.wikipedia.org/wiki/Exclusive_or Exclusive or] is denoted as:

<pre>

1 . . . . . . 1 . . . . . . . . 1 . . . . . . 1

1 . . . . . . 1 . . . . . . . . 1 . . . . . . 1

</pre>

Truth table of [https://en.wikipedia.org/wiki/XOR_gate exclusive or] for one bit:

{| class="wikitable"

It also acts like a bitwise subtraction (modulo 2).

[[x86]] has general purpose instruction as well as [[SIMD and SWAR Techniques|SIMD-instructions]] for bitwise exclusive or:

<pre>

vpxor ymm0, ymm1, ymm2 ; AVX2 ymm0 = ymm1 ^ ymm2

</pre>

[[AVX-512]] has [[AVX-512#VPTERNLOG|VPTERNLOG]]

Exclusive disjunction is [https://en.wikipedia.org/wiki/Commutative commutative]

a ^ b == b ^ a

Xor is [https://en.wikipedia.org/wiki/Associative associative] as well.

(a ^ b) ^ c == a ^ (b ^ c)

[[General Setwise Operations#Intersection|Conjunction]] is [https://en.wikipedia.org/wiki/Distributivity distributive] over exclusive disjunction - but '''not''' vice versa, since conjunction acts like multiplication, while xor acts as addition in the [https://en.wikipedia.org/wiki/Finite_field Galois field] [https://en.wikipedia.org/wiki/GF%282%29 GF(2)] :

x & (y ^ z) == (x & y) ^ (x & z)

If applied two (even) times with the same operand, xor restores the original result. It is own inverse or an [https://en.wikipedia.org/wiki/Involution involution] .

If one operand is subset of the other, xor (or subtraction) implements the [[General Setwise Operations#RelativeComplement|relative complement]].

<pre>

. . . . . . . . . . . . . . . . . . . . . . . .

</pre>

While commutative, xor is a better replacement for subtracting from power of two minus one values, such as 63.

This is because it usually safes one [[x86]] load instruction and an additional register, but uses opcodes with immediate operands - for instance:

<pre>

-1 - a == a ^ -1

</pre>

Xor is the same as a [[General Setwise Operations#Union|union]] without the [[General Setwise Operations#Intersection|intersection]] - all the bits different, 0,1 or 1,0. Since the [[General Setwise Operations#Intersection|intersection]] is subset of the [[General Setwise Operations#Union|union]], xor or subtraction can replace the "without" operation & ~:

a ^ b == (a | b) &~(a & b)

a ^ b == (a | b) ^ (a & b)

a ^ b == (a | b) - (a & b)

The symmetric difference of disjoint sets is equal to the [[General Setwise Operations#Union|union]] or arithmetical addition. Since [[General Setwise Operations#Intersection|intersection]] and symmetric difference are disjoint, the union might defined that way:

a | b = ( a & b ) ^ ( a ^ b )

a | b = ( a & b ) + ( a ^ b )

Assume we have distinct attack sets of pawns in left or right [[Direction|direction]]. The set of all squares attacked by two pawns is the intersection, the set exclusively attacked by one pawn (either right or left) is the xor-sum, while all squares attacked by any pawn is the union, see [[Pawn Attacks (Bitboards)#PawnAttacks|pawn attacks]].

The symmetric difference is equivalent to the [[General Setwise Operations#Union|union]] of both [[General Setwise Operations#RelativeComplement|relative complements]]. Since both [[General Setwise Operations#RelativeComplement|relative complements]] are [https://en.wikipedia.org/wiki/Disjoint disjoint], bitwise or or add can replaced by xor itself:

a ^ b == (a & ~b) | (b & ~a)

a ^ b == (a & ~b) ^ (b & ~a)

a ^ b == (a & ~b) + (b & ~a)

Xor can be used to toggle or flip bits by a mask.

x ^= mask;

xor with the universal set -1 flips each bit and results in the ones' complement.

a ^ -1 == ~a

<span id="XorWithout"></span>

Due to distributive law and since symmetric difference of set and subset is the relative complement of subset in set, there are some equivalent ways to calculate the [[General Setwise Operations#RelativeComplement|relative complement]] by xor. Based on surrounding expressions or whether subexpressions such as union, intersection or symmetric difference may be reused one may prefer the one or other alternative.

a & ~b == a & (-1 ^ b )

a & ~b == a ^ ( a & b ) == a - ( a & b )

a & ~b == b ^ ( a | b ) == ( a | b ) - b

a & a == a & -1

<span id="XorClear"></span>

Since 'a' xor 'a' is zero, it is the shorter opcode to clear a register, since it takes no immediate operand. Applied by optimizing compilers. Same is true for subtraction by the way.

<pre>

pxor xmm0, xmm0 ; SSE2 - 128-bit xmm-register

</pre>

Three xors on the same registers swap their content: (Note: this only works when a and b are stored on distinct memory adresses!)

<pre>

... 'a' becomes 'b', but only a part of 'b', where mask is one, becomes 'a'.

<span id="BitsFrom2SourcesByMask"></span>

Getting arbitrary, [https://en.wikipedia.org/wiki/Disjoint disjoint] bits from two sources by a mask:

<pre>

== (a & ~mask) + (b & mask) because both sets of the union are disjoint

</pre>

* Calculation of hash-keys based on [[Zobrist Hashing|Zobrist-keys]].

* [https://en.wikipedia.org/wiki/Cyclic_redundancy_check Cyclic redundancy check], [[Parallel Prefix Algorithms#ParityWords|Parity words]] or [[Parallel Prefix Algorithms#GrayCode|Gray Code]]

==Equivalence==

[https://en.wikipedia.org/wiki/Logical_equivalence Logical equivalence] is denoted as:

[https://en.wikipedia.org/wiki/Logical_equality Logical equality], [https://en.wikipedia.org/wiki/Logical_equivalence logical equivalence] or [https://en.wikipedia.org/wiki/Logical_biconditional biconditional] ([https://en.wikipedia.org/wiki/If_and_only_if if and only if], [https://en.wikipedia.org/wiki/XNOR_gate XNOR] ) is the complement of xor.

a_equal_b == (a & b) | (~a & ~b)

a_equal_b == (a & b) | ~(a | b)

Truth table of equivalence or for one bit:

{| class="wikitable"

Equivalence implements a bitwise (a == b) relation.

<span id="Majority"></span>

==Majority==

The [https://en.wikipedia.org/wiki/Majority_function majority function] or '''median operator''' is a function from n inputs to one output. The value of the operation is false when n/2 or fewer arguments are false, and true otherwise. For two inputs it is the [[General Setwise Operations#Intersection|intersection]]. Three inputs require some more computation:

Truth table of majority for three inputs:

{| class="wikitable"

See the application of [[Population Count#CardinalityofMultipleSets|cardinality of multiple sets]] for more than three inputs.

[[AVX-512]] [[AVX-512#VPTERNLOG|VPTERNLOG]] imm8 = 0xe8 implements the majority function.

<span id="GreaterOne"></span>

==Greater One Sets==

'''Greater One''' is a function from n inputs to one output. The value of the operation is true if more than one argument is true, false otherwise. Obviously, for two inputs it is the [[General Setwise Operations#Intersection|intersection]], for three inputs it is the [[General Setwise Operations#Majority|majority function]]. For more inputs it is the union of all distinct pairwise intersections, which can be expressed with setwise operators that way:

With four bitboards this is equivalent to:

<pre>

operations - that is 11 for n == 4.

Due to [[General Setwise Operations#DistributiveAndOr|distibutive law]] one can factor out common sets ...

<pre>

... with further reductions of the number of operations, also due to aggregation of the inner or-terms. Three additional operations for an increment of n, thus the former quadratic increase becomes linear.

requires

n * (n - 1) - 1

The reason the bitboard type-definintion is unsigned in [[C]], [[Cpp|C++]] is to avoid so called [https://en.wikipedia.org/wiki/Arithmetic_shift arithmetical shift right] in opposition to [https://en.wikipedia.org/wiki/Logical_shift logical shift right] . Arithmetical shift right implies filling one-bits in from MSB-direction if the operand is negative and has MSB bit 63 set. Logical shift right always shifts in zeros - that is what we need. [[Java]] has no unsigned types, but a special unsigned shift right operator >>>.

[[x86]] has general purpose instruction as well as [[SIMD and SWAR Techniques|SIMD-instructions]] for various shifts:

<pre>

ror rax, cl

</pre>

Otherwise rotate has to be emulated by shifts, with some chance optimizing compiler will emit exactly one rotate instruction.

<pre>

</pre>

<span id="GenOneStep"></span>

[[x86-64]] rot64 works like a generalized shift with positive or negative shift amount - since it internally applies an unsigned modulo 64 ( & 63) and makes -i = 64-i. We need to clear either the lower or upper bits by intersection with a mask, which might be combined with the wrap-ands for [[General Setwise Operations#OneStepOnly|one step]]. It might be applied to get attacks for both sides with a [[Direction|direction]] parameter and small lookups for shift amount and wrap-ands - instead of multiple code for eight directions. Of course generalized shift will be a bit slower due to lookups and using cl as the shift amount register.

<pre>

''The inverse function square = log2(x), is topic of [[BitScan|bitscan]] and [[Bitboard Serialization|bitboard serialization]].''

While 1 << square sounds cheap, it is rather expensive in 32-bit mode - and therefor often precalculated in a small lookup-table of 64-single bit bitboards. Also, on [[x86-64]]-processors a variable shift is restricted to the byte-register cl. Thus, two or more variable shifts are constrained by sequential execution <ref>[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</ref>.

Test a bit of a square-index by [[General Setwise Operations#Intersection|intersection]]-operator 'and'.

<pre>

if (x & singleBitset) -> bit is set;

</pre>

Set a bit of a square-index by [[General Setwise Operations#Union|union]]-operator 'or'.

<pre>

x |= singleBitset; // set bit

</pre>

Toggle a bit of square-index by [[General Setwise Operations#ExclusiveOr|xor]].

<pre>

x ^= singleBitset; // toggle bit

</pre>

Reset a bit of square-index by [[General Setwise Operations#RelativeComplement|relative complement]] of the single bit.

<pre>

If singleBitset needs to preserved, an extra register is needed for the complement.

[[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:

* [[x86-64#_bittest64|_bittest64]]

Similar for special moves like [[Castling|castling]], [[Promotions|promotions]] and [[En passant|en passant captures]].

<span id="UpperAndLowerBits"></span>

To get a set of all upper squares or bits, either shift ~1 or -2 left by square:

<pre>

</pre>

Lower squares are simply Bit by Square minus one.

<pre>

[http://graphics.stanford.edu/%7Eseander/bithacks.html#SwappingBitsXOR Swapping] none overlapping bit-sequences in a bitboard is the base of a lot of [https://en.wikipedia.org/wiki/Permutation permutation] tricks.

Suppose we like to swap n [[Bit|bits]] from two none overlapping bit locations of a bitboard. The trick is to set all n least significant bits by subtracting one from n power of 2. Both substrings are shifted to bit zero, exclusive ored and masked by the n ones. This sequence is then twice shifted back to their original places, while the [[General Setwise Operations#Union|union]] (xor-union due to [https://en.wikipedia.org/wiki/Disjoint disjoint] bits) is finally exclusive ored with the original bitboard to swap both sequences.

<pre>

</pre>

<span id="DeltaSwap"></span>

To swap any none overlapping pairs we can shift by the difference (j-i, with j>i) and supply an explicit mask with a '1' on the least significant position for each pair supposed to be swapped.

<pre>

==Derived from Bitwise==

Unlike bitwise boolean operations on 64-bit words, which are in fact 64 parallel operations on each bit without any interaction between them, arithmetic operations like addition need to propagate possible [https://en.wikipedia.org/wiki/Carry_%28arithmetic%29 carries] from lower to higher bits. Despite, Add and Sub are usually as fast their bitwise boolean counterparts, because they are implemented in Hardware within the [[Combinatorial Logic#ALU|ALU]] of the CPU. A so called [[Combinatorial Logic#Adder|half-adder]] to add two bits (A, B), requires an [[Combinatorial Logic#AND|And-Gate]] for the carry (C) and a [[Combinatorial Logic#XOR|Xor-Gate]] for the sum (S):

<pre>

two_bitsum = (bitA ^ bitB) | ((bitA & bitB) << 1);

[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 from a blocking piece|sliding attacks]].

<pre>

sub rax, rbx ; rax -= rbx

A lot of [[Bit-Twiddling|bit-twiddling]] tricks on bitboards to traverse or isolate subsets, rely on [https://en.wikipedia.org/wiki/Two%27s_complement two's complement] arithmetic. Most recent processors (and compiler or interpreter for these processors) use the two's complement to implement the unary minus operator for signed as well for unsigned integer types. In [[C]] it is guaranteed for unsigned integer types. [[Java]] guarantees two's complement for all implicit signed integral types char, short, int, long.

<pre>

</pre>

-x == ~x + 1

<pre>

x + (-x) == 0

==> x + ~x == -1 the universal set

</pre>

Replacing x by x - 1 in the increment of complement formula, leaves another definition - two's complement or Negation is also the ones' complement of the ones' decrement:

-x == ~(x - 1)

x - y == ~(~x + y)

</pre>

The two's complement may also defined by a bitwise copy-loop from right (LSB) to left (MSB):

<pre>

</pre>

This works independently whether we interpret 'x' as signed or unsigned. While 0 is is the synonym for all bits clear, -1 is the synonym for all bits set in a computer word of any arbitrary bit-size, also for 64-bit words such as bitboards.

Some C++ compiler warn -x still unsigned - (0-x) may used to avoid that with no overhead.

[[x86-64]] expansion [[BMI1]] has LS1B bit isolation:

<pre>

... since we already know two's complement (-x) and ones' decrement (x-1) are complement sets.

[[x86-64]] expansion [[BMI1]] has LS1B bit reset:

<pre>

1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

</pre>

[[x86-64]] expansion [[BMI1]] has [[BMI1#BLSMSK|BLSMSK]] (Mask Up to Lowest Set Bit = below_LSB1_mask_including), [[AMD|AMD's]] [[x86-64]] expansion [[TBM]] has [[TBM#TZMSK|TZMSK]] (Mask From Trailing Zeros = below_LSB1_mask):

<pre>

. . . . . . . . 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1

</pre>

[[AMD|AMD's]] [[x86-64]] expansion [[TBM]] has a [[TBM#BLSFILL|Fill From Lowest Set Bit]] instruction:

<pre>

Still quite expensive - better to traverse sets the other way around or rely on intrinsic functions to use special processor instructions like [[BitScan#Bitscanreverse|BitScanReverse]] or LeadingZeroCount, which implicitly performs not only the isolation but also the [https://en.wikipedia.org/wiki/Binary_logarithm log2].

Two sets have a common MS1B, if the [[General Setwise Operations#Intersection|intersection]] is greater than the xor sum:

<pre>

y = x * 0x00010100;

</pre>

In fact, we can replace [[Parallel Prefix Algorithms|parallel prefix]] left shifts like,

<pre>

See [[Kindergarten Bitboards|Kindergarten-Bitboards]]- or [[Magic Bitboards|Magic-Bitboards]] as applications of fill-multiplication.

Another bitboard related application of multiplication is to determine the bit-index of the least significant one bit. A isolated, single bit is multiplied with a [[De Bruijn sequence]] to implement a [[Bitscan#DeBruijnMultiplation|bitscan]].

<span id="Division"></span>

===Power of Two===

As a remainder, and to close the cycle to [[General Setwise Operations#Bitwisebooleanoperations|bitwise boolean operations]], the well known trick is mentioned, to replace modulo by power of two by [[General Setwise Operations#Intersection|intersection]] with power of two minus one:

=Selected Publications=

* [[Mathematician#CSPeirce|Charles S. Peirce]] ('''1867'''). ''On an Improvement in Boole's Calculus of Logic''. Proceedings of the American Academy of Arts and Sciences, Series Vol. 7

* [[Mathematician#Cantor|Georg Cantor]] ('''1874'''). ''[https://glossar.hs-augsburg.de/Cantor,_G._(1874):_Ueber_eine_Eigenschaft_des_Inbegriffs_aller_reellen_algebraischen_Zahlen Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen]''. [https://en.wikipedia.org/wiki/Crelle%27s_Journal Journal für die reine und angewandte Mathematik], No. 77

* [[Mathematician#CSPeirce|Charles S. Peirce]] ('''1880'''). ''[https://archive.org/details/jstor-2369442 On the Algebra of Logic]''. [https://en.wikipedia.org/wiki/American_Journal_of_Mathematics American Journal of Mathematics], Vol. 3

* [[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