Wikispaces : chessprogramming - items matching description

AVX

GerdIsenberg — Tue, 07 Mar 2017 20:14:51 GMT

Advantages of AVX

AVX on non-Intel CPUs

Home * Hardware * x86 * AVX

Advanced Vector Extensions (AVX) is a 256 bit extension to the x86 and x86-64 SSE, SSE2, SSE3, SSSE3, and SSE4 SIMD instruction sets, announced by Intel in March 2008, and first released in January, 2011 with Intel's Sandy Bridge architecture. With the Bulldozer microarchitecture, AVX is also available on AMD processors ^[1], along with their own XOP extension on Bulldozer only.

AVX supports 256-bit wide SIMD registers (YMM0-YMM7 in operating modes that are 32-bit or less, YMM0-YMM15 in 64-bit mode) to keep floating point vectors of either 8 floats or 4 doubles inside one register. The lower 128 bits of the YMM registers are aliased to the respective 128-bit XMM registers. AVX employs an instruction encoding scheme using a new VEX prefix, allowing a three-operand SIMD instruction format, where the destination register is distinct from the two source operands.

Advantages of AVX

AVX introduces expanded 256-bit versions of floating point instructions, which are typically not useful for chess programming. Though it does not yet expand the integer instructions to 256-bit, AVX does provide VEX-encoded versions of existing SSE 128-bit instructions. For instance, bitwise logical and:

Set	Instruction	Operation
SSE2	pand xmm1, xmm2/m128	xmm1 := xmm1 & xmm2
AVX	vpand xmm1, xmm2, xmm3/m128	xmm1 := xmm2 & xmm3

Though AVX does not yet support 256-bit integer operations, there are some benefits to using it. 3-operand support can be used to eliminate many "move" instructions, which otherwise can take up significant execution resources.

Additionally, when using xmm registers numbered 8 and higher, the AVX encoding of an SSE instruction is often one byte smaller, due to the more compact nature of the VEX encoding scheme. Finally, the ymm registers offer double the register space: even if the top halves aren't used for computation, they might be suitable as temporary storage space, avoiding the use of a scratch buffer or the stack.

While AVX can do 32-byte loads and stores, no CPU (as of Sandy Bridge) actually has a 32-byte load or store unit; such loads and stores are done simply by doing two separate 16-byte memory operations internally. Thus, AVX is no faster for memory operations (yet).

AVX on non-Intel CPUs

AMD's Bulldozer does not benefit from 3-operand in the same way that Intel's AVX-supporting CPU, Sandy Bridge, does. Bulldozer has a "move elimination" feature that resolves SIMD move instructions separately from the main execution pipeline. On Bulldozer, 3-operand support can still help reduce code size and reduce dispatch bottlenecks, but usually does not help performance much.

Additionally, Bulldozer only has a 128-bit floating-point execution unit, so 256-bit floating point operations are no faster than 128-bit ones, and sometimes actually slower. Nevertheless, some functions might still benefit from the extra register space.

Mixing AVX and SSE

Besides 3-operand support, the primary difference between the AVX and SSE encodings of an SSE instruction is that the AVX version clears the unused portion of the ymm register (the top 128 bits), while the SSE version does not modify it. Intel strongly advises against mixing SSE 128-bit instructions and AVX 256-bit instructions, as this "mode-switching" can cost upwards of 70 clock cycles. However, mixing SSE 128-bit and AVX 128-bit is okay, as is mixing AVX 128-bit and AVX 256-bit.

In order to safely switch modes, Intel recommends using vzeroupper after using 256-bit AVX instructions and before using 128-bit SSE instructions, if the two are being used in the same program.

AVX2

see main article AVX2

Manuals

External Links

Advanced Vector Extensions from Wikipedia
VEX prefix From Wikipedia
Intel Software Development Emulator, which can be used to experiment with AVX and AVX2 on a CPU that doesn't support them.
AMD and Intel incompatible - What to do? from AMD Developer Central
Intel Intrinsics Guide

References

^ AMD64 Architecture, Programmer’s Manual, Volume 4 128-Bit and 256-Bit Media Instructions (pdf)

What links here?

Page	Date Edited
AltiVec	Jun 7, 2016
AMD	Mar 9, 2018
AVX	Mar 7, 2017
AVX-512	Aug 8, 2017
AVX2	Aug 8, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
General Setwise Operations	Feb 25, 2018
Hyperbola Quintessence	Mar 25, 2017
Intel	Aug 29, 2015
Shared Hash Table	Sep 11, 2017
SIMD and SWAR Techniques	Jun 27, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
TBM	Jun 28, 2012
Windows	Nov 2, 2017
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

AVX-512

GerdIsenberg — Tue, 08 Aug 2017 19:56:01 GMT

Home * Hardware * x86-64 * AVX-512

Extensions

Selected Instructions

AVX-512,
an expansion of Intel's the AVX and AVX2 instructions using the EVEX prefix, featuring 32 512-bit wide vector SIMD registers zmm0 through zmm31, keeping either eight doubles or integer quad words such as bitboards, and eight (seven) dedicated mask registers which specify which vector elements are operated on and written. If the Nth bit of a vector mask register is set, then the Nth element of the destination vector is overridden with the result of the operation; otherwise, dependent of the instruction, the element is zeroed, or overridden by an element from another source register (remains unchanged if same source). A vector mask register can be set using vector compare instructions, instructions to move contents from a GP register, or a special subset of vector mask arithmetic instructions.

Extensions

AVX-512 consists of multiple extensions not all meant to be supported by all AVX-512 capable processors. Only the core extension AVX-512F (AVX-512 Foundation) is required by all implementations ^[1] AVX-512F and AVX-512CD were first implemented in the Xeon Phi processor and coprocessor known by the code name Knights Landing ^[2] , launched on June 20, 2016.

Extension	Description	Architecture	CPUID 7 Reg:Bit ^[3]
AVX-512F	Foundation	Knights Landing	EBX:16
AVX-512CD	Conflict Detection Instructions		EBX:28
AVX-512ER	Exponential and Reciprocal Instructions		EBX:27
AVX-512PF	Prefetch Instructions		EBX:26
AVX-512BW	Byte and Word Instructions	Skylake X	EBX:30
AVX-512DQ	Doubleword and Quadword Instructions		EBX:17
AVX-512VL	Vector Length Extensions		EBX:31
AVX-512IFMA	Integer Fused Multiply Add	Cannonlake	EBX:21
AVX-512VBMI	Vector Byte Manipulation Instructions	Cannonlake	ECX:01
AVX-512VPOPCNTDQ	Vector Population Count	Knights Mill	ECX:14
AVX-512-4VNNIW	Vector Neural Network Instructions Word variable precision		EDX:02
AVX-512-4FMAPS	Fused Multiply Accumulation Packed Single precision		EDX:03

Selected Instructions

VPTERNLOG

AVX-512F features the instruction VPTERNLOGQ (or VPTERNLOGD) to perform bitwise ternary logic, for instance to operate on vectors of bitboards. Three input vectors are bitwise combined by an operation determined by an immediate byte operand (imm8), whose 256 possible values corresponds with the boolean output vector of the truth table for all eight combinations of the three input bits, as demonstrated with some selected imm8 values in the table below ^[4] ^[5] :

Input					Output of Operations
				imm8	0x00	0x01	0x16	0x17	0x28	0x80	0x88	0x96	0xca	0xe8	0xfe	0xff
#	a	b	c	C-exp	false	~(a\|b\|c)	a?~(b\|c):b^c	minor(a,b,c)	c&(a^b)	a&b&c	b&c	a^b^c	a?b:c	major(a,b,c)	a\|b\|c	true
0	0	0	0		0	1	0	1	0	0	0	0	0	0	0	1
1	0	0	1		0	0	1	1	0	0	0	1	1	0	1	1
2	0	1	0		0	0	1	1	0	0	0	1	0	0	1	1
3	0	1	1		0	0	0	0	1	0	1	0	1	1	1	1
4	1	0	0		0	0	1	1	0	0	0	1	0	0	1	1
5	1	0	1		0	0	0	0	1	0	0	0	0	1	1	1
6	1	1	0		0	0	0	0	0	0	0	0	1	1	1	1
7	1	1	1		0	0	0	0	0	1	1	1	1	1	1	1

Following VPTERNLOGQ intrinsics are declared, where the maskz version sets unmasked destination quad word elements to zero, while the mask version copies unmasked elements from s:

__m512i _mm512_ternarylogic_epi64(__m512i a, __m512i b, __m512i c, int imm8);
__m512i _mm512_maskz_ternarylogic_epi64( __mmask8 m, __m512i a, __m512i b, __m512i c, int imm8);
__m512i _mm512_mask_ternarylogic_epi64(__m512i s, __mmask8 m, __m512i a, __m512i b, __m512i c, int imm8);

VPLZCNT

AVX-512CD has Vector Leading Zero Count - VPLZCNTQ counts leading zeroes on a vector of eight bitboards in parallel ^[6] - using following intrinsics ^[7], where the maskz version sets unmasked destination elements to zero, while the mask version copies unmasked elements from s:

__m512i _mm512_lzcnt_epi64(__m512i a);
__m512i _mm512_maskz_lzcnt_epi64(__mmask8 m, __m512i a);
__m512i _mm512_mask_lzcnt_epi64(__m512i s, __mmask8 m, __m512i a);

VPOPCNT

The future AVX-512VPOPCNTDQ extension has a vector population count instruction to count one bits of either 16 32-bit double words (VPOPCNTD) or 8 64-bit quad words aka bitboards (VPOPCNTQ) in parallel ^[8] ^[9].

Manuals

Intel® Architecture Instruction Set Extensions Programming Reference (pdf)

External Links

Blog Postings

AVX-512 instructions | Intel® Developer Zone by James Reinders, July 23, 2013
Future instruction set: AVX-512 by Agner Fog, October, 09, 2013
Additional AVX-512 instructions | Intel® Developer Zone by James Reinders, July 17, 2014
Processing Arrays of Bits with Intel® Advanced Vector Extensions 512 (Intel® AVX-512) | Intel® Developer Zone by Thomas Willhalm, July 24, 2014
AVX-512 May Be a Hidden Gem” in Intel Xeon Scalable Processors by James Reinders, HPCwire, June 29, 2017

Compiler Support

Intel Intrinsics Guide - AVX-512
Intel® Advanced Vector Extensions 2015/2016 Support in GNU Compiler Collection (pdf) by Kirill Yukhin, July 2014
Guide to Automatic Vectorization with Intel AVX-512 Instructions in Knights Landing Processors - Colfax Research, May 11, 2016
Microsoft Visual Studio 2017 Supports Intel® AVX-512 | Visual C++ Team Blog by Eric Battalio, July 11, 2017

References

^ AVX-512 from Wikipedia
^ Additional AVX-512 instructions | Intel® Developer Zone by James Reinders, July 17, 2014
^ AVX512 table from Heise
^ AVX512: ternary functions evaluation by Wojciech Muła, March 03, 2015
^ Intel® Architecture Instruction Set Extensions Programming Reference (pdf) 5.3 TERNARY BIT VECTOR LOGIC TABLE
^ Patent US9372692 - Methods, apparatus, instructions, and logic to provide permute controls with leading zero count functionality - Google Patent Search
^ VPLZCNTD/Q—Count the Number of Leading Zero Bits for Packed Dword, Packed Qword Values
^ sse-popcount/popcnt-avx512-harley-seal.cpp at master · WojciechMula/sse-popcount · GitHub
^ Wojciech Muła, Nathan Kurz, Daniel Lemire (2016). Faster Population Counts Using AVX2 Instructions. arXiv:1611.07612

What links here?

Page	Date Edited
AltiVec	Jun 7, 2016
AVX	Mar 7, 2017
AVX-512	Aug 8, 2017
AVX2	Aug 8, 2017
BitScan	Sep 10, 2017
DirGolem	Jun 5, 2016
General Setwise Operations	Feb 25, 2018
Population Count	Sep 3, 2017
SIMD and SWAR Techniques	Jun 27, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
Wojciech Muła	Aug 10, 2017
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

Bitboard Serialization

GerdIsenberg — Wed, 24 Dec 2014 12:09:43 GMT

Home * Board Representation * Bitboards * Bitboard Serialization

		Bitboard Serialization refers to the transformation of a bitboard with up to 64 one-bits set into a list of up to 64 bit-indices aka square indices of a 8x8 board - for instance to process move-target sets for move generation. This is done in two phases, isolating none-empty subsets and then transforming those more versatile subsets into lists, either bit by bit, by applying a bisection scheme, where finally words or bytes may act as index of a pre-calculated database, or by perfect hashing of square lists by subsets with a limited maximum popularity, for instance move-target sets of a king or knight even with minimal perfect hashing.
M. C. Escher, Encounter, 1944 ^[1]

Isolating Subsets

Single Bits

Multiple Bits

Converting Sets to Lists

Square Index Serialization

Hashing Multiple Bits

Isolating Subsets

The process of isolating subsets is performed by intersection, for single populated subsets with the two's complement.

Single Bits

This obvious loop approach is similar to Brian Kernighan's way to count the number of one-bits by consecutively isolating and clearing the LS1B:

while ( x ) {
   U64 ls1b = x & -x; // isolate LS1B
   ...
   x &= x-1; // reset LS1B
}

or with likely the same generated assembly:

if ( x ) do {
   U64 ls1b = x & -x; // isolate LS1B
   ...
} while ( x &= x-1 );

Of course we may also reset the LS1B by

   x ^= ls1b; // reset LS1B

but todays processors like to gain more parallelism to calculate independent expressions.

Multiple Bits

Isolating none-empty subsets with possibly multiple one-bits can be applied by divide and conquer, that is to divide the bitboard or quad word recursively into smaller items, two double words, consisting of two words and those again of two bytes. Word and byte-wide isolated subsets may then act as an index of a pre-calculated lookup table to convert those subsets to adequate data-structures, most likely lists with up to sixteen or eight elements.

Converting Sets to Lists

Square Index Serialization

For most applications LS1B-isolation alone is not appropriate, but the conversion from the exponential bitboard centric world to the scalar square centric world, also called bit-scanning.

Scanning Forward

if ( x ) do {
   int idx = bitScanForward(x); // square index from 0..63
   *list++ = foo(idx, ...);
} while (x &= x-1); // reset LS1B

Per definition bitScanForward reveals the index of LS1B.

Scanning Reverse

If - for some reason - we like to traverse the sets in reverse or unknown order anyway, we can not (or don't want to) rely on the independent LS1B reset.

if ( x ) do {
   int idx = bitScanReverse(x); // square index from 0..63
   *list++ = foo(idx, ...);
} while (x ^= powOf2[idx]) ; // or 1ULL << idx -> reset found bit

Scanning with Reset

A win of abstraction is to use a combined bitscan with reset found bit routine. This is fine. But probably harder for compilers to generate optimal code in the if-do-while-sense, where reset last bit already sets the zero-flag. If you don't care on such micro-optimizations, this is the preferred control structure.

while ( x ) {
   int idx = bitScanAndReset(&x); // square index from 0..63
   *list++ = foo(idx, ...);
}

One may even don't care about the order.

Intrinsic Version

If bitscan is able to properly handle empty sets - leaving an value outside the 0..63 range (like leading or trailing zero count), we may think about to skip the leading while condition and to break on bitscan(x) > 63 for instance. That was not recommend - since the reset leaves the condition en-passant, and the computational cost of an additional bitscan or zero count was higher. If you like to play the optimization game, it might be fine for x86-64 Core 2 duo thought - using bitscan and bittestandreset intrinsics or wrappers - if kept all in registers of course.

while (_BitScanForward64(&idx, x)) { // or reverse
   *list++ = foo(idx, ...);
   _bittestandreset64(&x, idx);
}

The loop is intended to look like this in x86-64 assembly:

; input rdx - move target set
;       ecx - move from aspects
;       rdi - pointer to movelist
   std           ; set direction flag
   bsf  rax, rdx ; scan first to-bit
   jz   over     ; jump if no more moves
loop:
   btr  rdx, rax ; reset found bit
   or   eax, ecx ; combine to- with from-square
   stosw         ; store 16-bit move *rdi++ = move
   bsf  rax, rdx ; scan next to-bit
   jnz  loop     ; jump if more moves
over:

Black or White

With bitboard serialization one minor problem is the relative order in move generation considering side to move. Bsf scans the board in a1..h1, a2..h2, a8..h8 order, assuming little-endian rank-file mapping, which might be the desired order for an attacking black player. Traversing white pieces and target squares the same way may result in asymmetries and different search behavior of color flipped positions. Despite other features considered in move ordering, the initial order in generation has more or less influence. Therefore, it is desired to traverse the "white" bitboards with priority for the black back-rank as well ^[2] . This might be done by bitscan reverse, which covers the rank symmetry, but also mirrors the files. Another alternative is to traverse a vertically flipped "white" bitboard, which can be done outside the do-while loop by a "conditional" x86-64 byte swap, and requires one further register and xor per loop cycle, which might be combined with other stuff, f.i. the from square of a move:

if ( x ) {
   U64 m = (U64)color - 1; // e.g. -1 if white, 0 for black
   int o = (int)m & 56;
   x = x ^ ((x ^ flipVertical(x)) & m); // conditional flip
   do {
      int idx = bitScanForward(x) ^ o; // square index from 0..63
      *list++ = foo(idx , ...);
   } while (x &= x-1); // reset LS1B
}

STL Iterator

Rein Halbersma has written a prototype of a generic C++11 bitset template that can be used to traverse a set in STL iterator style, hiding bitscan and reset ^[3] ^[4] ...

typedef bit_set<int64_t, 1> bitset;
 
void testLoop(int* p, const bitset & x) {
  for (auto it = x.begin(); it != x.end(); ++it)
    *p++ = *it;
}
/* or std::copy */
void testCopy(int* p, const bitset & x) {
  std::copy(x.begin(), x.end(), p); 
}

... which yields in following X86-64 assembly, almost identical for the iterator loop and std::copy ^[5]:

; testLoop(int*, bit_set<long, 1ul>):
  test  rsi, rsi
  jne   .L13
.L7:
  ret
.L13:
  bsf   rax, rsi
  mov   DWORD PTR [rdi], eax
  lea   rax, [rsi-1]
  add   rdi, 4
  and   rsi, rax
  jne   .L13
  jmp   .L7

Hashing Multiple Bits

Similar to the idea to hash occupancies in kindergarten bitboards and magic bitboards, one may hash certain move-target subsets of one piece in one run, to lookup tables with pre-calculated moves-lists ^[6] . Sounds like doing up to eight bitscans in parallel. The idea is to muliply-shift-lookup a move-target bitboard, to do an almost branch-less move-generation with pre-calculated moves inside move-lists. For instance king- and knight-moves ^[7] as well as moves of sliding pieces per line:

moveTarget = KingAttacks[sq] & ~(ownPieces | attackedSquares);
idx = (moveTarget * kingMagic[sq]) >> kingShift[sq]);
movelists = kingMoveLists[sq];
movelist  = movelists[idx];
moveCpy(target, movelist, movelist->n);

A king in a corner may have up to three moves. Thus there are 2^3 == 8 possible move-lists.
For instance for a king on a1 (number of moves: vector of moves):

0:{empty}
1:{a1-b1}
1:{a1-a2}
1:{a1-b2}
2:{a1-b1,a1-a2}
2:{a1-b1,a1-b2}
2:{a1-a2,a1-b2}
3:{a1-b1,a1-a2,a1-b2}

Kings on edges have 5 potential target squares, thus there are 32 possible move-lists. All other kings have 8 all the 8 neighbors with up to 256 move-lists. Similar move-list enumeration is possible with knights and others. All possible move-target subsets of kings and knights for all 64 from-squares are perfectly minimal hashtable with a magic factor of four one-bits set. 10016 possible king-move-lists and 5520 knight-move-lists. To reduce memory one may offset the sets to a "normalized" source square per king, knight and sliding piece line, implying some vector arithmetic in the board centric world considering the offset.

The less populated move-target subsets are, the less efficient this hashing technique. This might become a problem since bitboard move-generation is essentially about subsets of moves with certain properties, like most importantly fast winning captures at Cut-nodes.

Forum Posts

Subject: sliding move generation idea with bitboards by Gerd Isenberg, CCC, February 19, 2006
Magic Knight- and King-Move Generation by Gerd Isenberg, Winboard Forum, Januar 11, 2007
Re: C vs ASM by Rein Halbersma, CCC, March 05, 2013
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014 » BitScan

External Links

Serialization from Wikipedia

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Re: Alternatives to History Heuristics by Robert Hyatt, CCC, September 02, 2009
^ LiveWorkSpace(IDE online): C++-3.2 (clang++): 41EaZl
^ Re: C vs ASM by Rein Halbersma, CCC, March 05, 2013
^ GCC Explorer with g++ 4.7 compiler, options -std=c++11 -O3 -march=k8-sse3 -fverbose-asm
^ Subject: sliding move generation idea with bitboards by Gerd Isenberg, CCC, February 19, 2006
^ Magic Knight- and King-Move Generation by Gerd Isenberg, Winboard Forum, Januar 11, 2007

What links here?

Page	Date Edited
More Links
Backtracking	Dec 16, 2017
Bison	Sep 29, 2016
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
BitScan	Sep 10, 2017
Blockers and Beyond	Mar 21, 2014
Brainless	Jun 24, 2017
Checks and Pinned Pieces (Bitboards)	Aug 14, 2013
CHEOPS	Apr 18, 2015
Color Flipping	May 17, 2017
Crafty	Jan 28, 2018
Double and Triple (Bitboards)	May 12, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Hash Table	Jan 1, 2018
Iteration	May 5, 2017
Joker IT	Sep 16, 2017
Knight Pattern	Feb 23, 2015
Lasse Hansen	Sep 1, 2015
Linked List	Oct 11, 2016
Move Generation	Jan 29, 2018
NoraGrace	Nov 23, 2014
Open Pawns (Bitboards)	Aug 24, 2017
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Pushes (Bitboards)	Apr 5, 2013
Piece-Sets	Jun 9, 2017
Pieces versus Directions	Oct 6, 2016
Population Count	Sep 3, 2017
Praetorian	Feb 21, 2015
Rein Halbersma	Dec 22, 2015
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
Rybka	Mar 27, 2017
Sliding Piece Attacks	May 27, 2016
Sliding Pieces	Aug 3, 2017
Spector	Nov 11, 2016
Tinker	Aug 29, 2015
Traversing Subsets of a Set	Oct 14, 2016

Up one Level

BitScan

GerdIsenberg — Sun, 10 Sep 2017 15:44:37 GMT

Home * Board Representation * Bitboards * BitScan

		BitScan, a function that determines the bit-index of the least significant 1 bit (LS1B) or the most significant 1 bit (MS1B) in an integer such as bitboards. If exactly one bit is set in an unsigned integer, representing a numerical value of a power of two, this is equivalent to a base-2 logarithm. Many implementations have been devised since the advent of bitboards, as described on this page, and some implementation samples of concrete open source engines listed for didactic purpose.
M. C. Escher, Eye, 1946 ^[1]

Hardware vs. Software

For recent x86-64 architectures like Core 2 duo and K10, one should use the Processor Instructions for Bitscans via intrinsics or inline assembly, see x86-64 timing. P4 and K8 have rather slow bitscan-instructions. K8 uses so called vector path instructions ^[2] with 9 or 11 cycles latency, even blocking other processor resources. For these processors, specially K8 with already fast multiplication, the De Bruijn Multiplication (64-bit mode) or Matt Taylor's Folded 32-bit Multiplication (32-bit mode) might be the right choice. Other routines mentioned might be advantageous on certain architectures, specially with slow integer multiplications.

Non Empty Sets

Bitscan is most often used in serializing bitboards, and is therefor - due to a leading while-condition - not called with empty sets. Until stated otherwise, most mentioned bitscan-routines in C/C++ have the same prototype and assume none empty sets as actual parameter.

Bitscan forward

A bitscan forward is used to find the index of the least significant 1 bit (LS1B).

Trailing Zero Count

Bitscan forward is identical with a Trailing Zero Count for none empty sets, possibly available as machine instruction on some architectures, for instance the x86-64 bit-manipulation expansion set BMI1.

De Bruijn Multiplication

The De Bruijn bitscan was devised in 1997, according to Donald Knuth ^[3] by Martin Läuter, and independently by Charles Leiserson, Harald Prokop and Keith H. Randall a few month later ^[4] ^[5] , to determine the LS1B index by minimal perfect hashing. De Bruijn sequences were named after the Dutch mathematician Nicolaas de Bruijn. Interestingly sequences with the binary alphabet were already investigated by the French mathematician Camille Flye Sainte-Marie in 1894, but later "forgotten" and re-investigated and generalized by De Bruijn and Tanja van Ardenne-Ehrenfest half a century later ^[6] .

A 64-bit De Bruijn sequence contains 64-overlapped unique 6-bit sequences, thus a circle of 64 bits, where five leading zeros overlap five hidden "trailing" zeros. There are 226 = 67108864 odd sequences with 6 leading binary zeros and 226 even sequences with 5 leading binary zeros, which may be calculated from the odd ones by shifting left one.

With isolated LS1B

A multiplication with a power of two value (the isolated LS1B) acts like a left shift by it's exponent. Thus, if we multiply a 64-bit De Bruijn sequence with the isolated LS1B, we get a unique six bit subsequence inside the most significant bits. To obtain the bit-index we need to extract these upper six bits by shifting right the product, to lookup an array.

const int index64[64] = {
    0,  1, 48,  2, 57, 49, 28,  3,
   61, 58, 50, 42, 38, 29, 17,  4,
   62, 55, 59, 36, 53, 51, 43, 22,
   45, 39, 33, 30, 24, 18, 12,  5,
   63, 47, 56, 27, 60, 41, 37, 16,
   54, 35, 52, 21, 44, 32, 23, 11,
   46, 26, 40, 15, 34, 20, 31, 10,
   25, 14, 19,  9, 13,  8,  7,  6
};
 
/**
 * bitScanForward
 * @author Martin Läuter (1997)
 *         Charles E. Leiserson
 *         Harald Prokop
 *         Keith H. Randall
 * "Using de Bruijn Sequences to Index a 1 in a Computer Word"
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   return index64[((bb & -bb) * debruijn64) >> 58];
}

See also how to Generate your "private" De Bruijn Bitscan Routine.

With separated LS1B

Instead of the classical LS1B isolation, Kim Walisch proposed the faster xor with the ones' decrement. The separation bb ^ (bb-1) contains all bits set including and below the LS1B. The 222 (4,194,304) upper De Bruijn sequences of the 226 available leave unique 6-bit indices. Using LS1B separation takes advantage of the x86 lea instruction, which saves the move instruction and unlike negate, has no data dependency on the flag register. Kim reported a 10 to 15 percent faster execution (compilers: g++-4.7 -O2, clang++-3.1 -O2, x86_64) than the traditional 64-bit De Bruijn bitscan on Intel Nehalem and Sandy Bridge CPUs.

const int index64[64] = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
 
/**
 * bitScanForward
 * @author Kim Walisch (2012)
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   return index64[((bb ^ (bb-1)) * debruijn64) >> 58];
}

Matt Taylor's Folding trick

A 32-bit friendly implementation to find the the bit-index of LS1B by Matt Taylor ^[7]. The xor with the ones' decrement, bb ^ (bb-1) contains all bits set including and below the LS1B. The 32-bit xor-difference of both halves yields either the complement of the upper half, or the lower half otherwise. Some samples:

ls1b	bb ^ (bb-1)	folded
63	`0xffffffffffffffff`	`0x00000000`
62	`0x7fffffffffffffff`	`0x80000000`
59	`0x0fffffffffffffff`	`0xf0000000`
32	`0x00000001ffffffff`	`0xfffffffe`
31	`0x00000000ffffffff`	`0xffffffff`
30	`0x000000007fffffff`	`0x7fffffff`
0	`0x0000000000000001`	`0x00000001`

Even if this folded "LS1B" contains multiple consecutive one-bits, the multiplication is De Bruijn like. There are only two magic 32-bit constants with the combined property of 32- and 64-bit De Bruijn sequences to apply this minimal perfect hashing:

const int lsb_64_table[64] =
{
   63, 30,  3, 32, 59, 14, 11, 33,
   60, 24, 50,  9, 55, 19, 21, 34,
   61, 29,  2, 53, 51, 23, 41, 18,
   56, 28,  1, 43, 46, 27,  0, 35,
   62, 31, 58,  4,  5, 49, 54,  6,
   15, 52, 12, 40,  7, 42, 45, 16,
   25, 57, 48, 13, 10, 39,  8, 44,
   20, 47, 38, 22, 17, 37, 36, 26
};
 
/**
 * bitScanForward
 * @author Matt Taylor (2003)
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   unsigned int folded;
   assert (bb != 0);
   bb ^= bb - 1;
   folded = (int) bb ^ (bb >> 32);
   return lsb_64_table[folded * 0x78291ACF >> 26];
}

A slightly modified version may take one x86-register less in 32-bit mode, but calculates bb-1 twice:

int bitScanForwardM(BitBoard bb) {
   unsigned int folded;
   assert (bb != 0);
   folded  = (int)((bb ^ (bb-1)) >> 32);
   folded ^= (int)( bb ^ (bb-1)); // lea
   return lsb_64_table[folded * 0x78291ACF >> 26];
}

with this VC6 generated x86 assembly to compare:

bitScanForward PROC NEAR                   bitScanForwardM PROC NEAR
   mov  ecx, DWORD PTR _bb$[esp-4]            mov  eax, DWORD PTR _bb$[esp-4]
   mov  eax, DWORD PTR _bb$[esp]              mov  ecx, eax
   mov  edx, ecx                              add  ecx, -1
   push esi                                   mov  ecx, DWORD PTR _bb$[esp]
   add  edx, -1                               mov  edx, ecx
   mov  esi, eax                              adc  edx, -1
   adc  esi, -1                               xor  edx, ecx
   xor  ecx, edx                              lea  ecx, DWORD PTR [eax-1]
   xor  eax, esi                              xor  edx, ecx
   pop  esi
   xor  eax, ecx                              xor  edx, eax
   imul eax, 78291acfH                        imul edx, 78291acfH
   shr  eax, 26                               shr  edx, 26
   mov  eax, DWORD PTR _lsb_64_table[eax*4]   mov  eax, DWORD PTR _lsb_64_table[edx*4]
   ret  0                                     ret  0
bitScanForward ENDP                        bitScanForward ENDP

Walter Faxon's magic Bitscan

Walter Faxon's 32-bit friendly magic bitscan ^[8] uses a fast none minimal perfect hashing function:

const char LSB_64_table[154] =
{
#define __ 0
   22,__,__,__,30,__,__,38,18,__, 16,15,17,__,46, 9,19, 8, 7,10,
   0, 63, 1,56,55,57, 2,11,__,58, __,__,20,__, 3,__,__,59,__,__,
   __,__,__,12,__,__,__,__,__,__, 4,__,__,60,__,__,__,__,__,__,
   __,__,__,__,21,__,__,__,29,__, __,37,__,__,__,13,__,__,45,__,
   __,__, 5,__,__,61,__,__,__,53, __,__,__,__,__,__,__,__,__,__,
   28,__,__,36,__,__,__,__,__,__, 44,__,__,__,__,__,27,__,__,35,
   __,52,__,__,26,__,43,34,25,23, 24,33,31,32,42,39,40,51,41,14,
   __,49,47,48,__,50, 6,__,__,62, __,__,__,54
#undef __
};
 
/**
 * bitScanForward
 * @author Walter Faxon, slightly modified
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb)
{
   unsigned int t32;
   assert(bb);
   bb  ^= bb - 1;
   t32  = (int)bb ^ (int)(bb >> 32);
   t32 ^= 0x01C5FC81;
   t32 +=  t32 >> 16;
   t32 -= (t32 >> 8) + 51;
   return LSB_64_table [t32 & 255]; // 0..63
}

A slightly modified version may take one x86-register less in 32-bit mode, but calculates bb-1 twice:

int bitScanForward(U64 bb)
{
   int t32 = 0x01C5FC81;
   assert(bb);
   t32 ^= (int)((bb ^ (bb-1)) >> 32);
   t32 ^= (int)( bb ^ (bb-1)); // lea
   t32 += t32 >> 16;
   t32 -=(t32 >>  8) + 51;
   return LSB_64_table [t32 & 255];
}

The initial LS1B separation by bb ^ (bb-1) and folding is equivalent to Matt's,

ls1b	bb ^ (bb-1)	folded
63	`0xffffffffffffffff`	`0x00000000`
62	`0x7fffffffffffffff`	`0x80000000`
59	`0x0fffffffffffffff`	`0xf0000000`
32	`0x00000001ffffffff`	`0xfffffffe`
31	`0x00000000ffffffff`	`0xffffffff`
30	`0x000000007fffffff`	`0x7fffffff`
0	`0x0000000000000001`	`0x00000001`

while Walter originally resets the LS1B, yielding in a cyclic index wrap:

LS1B	(bb & (bb-1)) ^ (bb-1)	folded
0	`0x0000000000000000`	`0x00000000`
63	`0x7fffffffffffffff`	`0x80000000`
60	`0x0fffffffffffffff`	`0xf0000000`
33	`0x00000001ffffffff`	`0xfffffffe`
32	`0x00000000ffffffff`	`0xffffffff`
31	`0x000000007fffffff`	`0x7fffffff`
1	`0x0000000000000001`	`0x00000001`

Bitscan by Modulo

Another idea is to apply a modulo (remainder of a division) operation of the isolated LS1B by the prime number 67 ^[9] ^[10] . The remainder 0..66 can be used to perfectly hash the bit-index table. Three gaps are 0, 17, and 34, so the mod 67 can make a branchless trailing zero count:

Bit-Index	Bitboard	mod 67
-	0x0000000000000000	0
0	0x0000000000000001	1
1	0x0000000000000002	2
2	0x0000000000000004	4
3	0x0000000000000008	8
4	0x0000000000000010	16
5	0x0000000000000020	32
6	0x0000000000000040	64
7	0x0000000000000080	61
8	0x0000000000000100	55
9	0x0000000000000200	43
10	0x0000000000000400	19
11	0x0000000000000800	38
12	0x0000000000001000	9
13	0x0000000000002000	18
14	0x0000000000004000	36
15	0x0000000000008000	5
16	0x0000000000010000	10
17	0x0000000000020000	20
18	0x0000000000040000	40
19	0x0000000000080000	13
20	0x0000000000100000	26
21	0x0000000000200000	52
22	0x0000000000400000	37
23	0x0000000000800000	7
24	0x0000000001000000	14
25	0x0000000002000000	28
26	0x0000000004000000	56
27	0x0000000008000000	45
28	0x0000000010000000	23
29	0x0000000020000000	46
30	0x0000000040000000	25
31	0x0000000080000000	50
32	0x0000000100000000	33
33	0x0000000200000000	66
34	0x0000000400000000	65
35	0x0000000800000000	63
36	0x0000001000000000	59
37	0x0000002000000000	51
38	0x0000004000000000	35
39	0x0000008000000000	3
40	0x0000010000000000	6
41	0x0000020000000000	12
42	0x0000040000000000	24
43	0x0000080000000000	48
44	0x0000100000000000	29
45	0x0000200000000000	58
46	0x0000400000000000	49
47	0x0000800000000000	31
48	0x0001000000000000	62
49	0x0002000000000000	57
50	0x0004000000000000	47
51	0x0008000000000000	27
52	0x0010000000000000	54
53	0x0020000000000000	41
54	0x0040000000000000	15
55	0x0080000000000000	30
56	0x0100000000000000	60
57	0x0200000000000000	53
58	0x0400000000000000	39
59	0x0800000000000000	11
60	0x1000000000000000	22
61	0x2000000000000000	44
62	0x4000000000000000	21
63	0x8000000000000000	42

/**
 * trailingZeroCount
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit, 64 if bb is zero
 */
int trailingZeroCount(U64 bb) {
   static const int lookup67[67+1] = {
      64,  0,  1, 39,  2, 15, 40, 23,
       3, 12, 16, 59, 41, 19, 24, 54,
       4, -1, 13, 10, 17, 62, 60, 28,
      42, 30, 20, 51, 25, 44, 55, 47,
       5, 32, -1, 38, 14, 22, 11, 58,
      18, 53, 63,  9, 61, 27, 29, 50,
      43, 46, 31, 37, 21, 57, 52,  8,
      26, 49, 45, 36, 56,  7, 48, 35,
       6, 34, 33, -1 };
   return lookup67[(bb & -bb) % 67];
}

Since div/mod is an expensive instruction, a modulo by a constant is likely replaced by reciprocal fixed point multiplication to get the quotient and a second multiplication and difference to get the remainder. Compared with De Bruijn multiplication it is still too slow.

Divide and Conquer

This is a broad group of bitscans that test in succession, like the trailing zero count based on Reinhard Scharnagl's proposal ^[11] :

/**
 * trailingZeroCount
 *  like bitScanForward for none empty sets
 * @author Reinhard Scharnagl
 * @param bb bitboard to scan
 * @return index (0..64)
 */
unsigned char lsbRS[256] = {
    8, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};
 
int trailingZeroCount(U64 b) {
  unsigned buf;
  int acc = 0;
 
  if ((buf = (unsigned)b) == 0) {
    buf = (unsigned)(b >> 32);
    acc = 32;
  }
  if ((unsigned short)buf == 0) {
    buf >>= 16;
    acc += 16;
  }
  if ((unsigned char)buf == 0) {
    buf >>= 8;
    acc += 8;
  }
  return acc + lsbRS[buf & 0xff];
}

What about direct calculation? On x86 this is a chain of test, set and lea instructions:

/**
 * bitScanForward
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 bb) {
   unsigned int lsb;
   assert (bb != 0);
   bb &= -bb; // LS1B-Isolation
   lsb = (unsigned)bb
       | (unsigned)(bb>>32);
   return (((((((((((unsigned)(bb>>32) !=0)  * 2)
                 + ((lsb & 0xffff0000) !=0)) * 2)
                 + ((lsb & 0xff00ff00) !=0)) * 2)
                 + ((lsb & 0xf0f0f0f0) !=0)) * 2)
                 + ((lsb & 0xcccccccc) !=0)) * 2)
                 + ((lsb & 0xaaaaaaaa) !=0);
}

Double conversion of LS1B

Assuming 64-bit doubles and little-endian structure (not portable). We convert the isolated LS1B to a double and interprete the exponent:

/**
 * bitScanForward
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @return index (0..63) of least significant one bit
 *         -1023 if passing zero
 */
int bitScanForward(U64 bb)
{
   union {
      double d;
      struct {
         unsigned int mantissal : 32;
         unsigned int mantissah : 20;
         unsigned int exponent : 11;
         unsigned int sign : 1;
      };
   } ud;
   ud.d = (double)(bb & -bb); // isolated LS1B to double
   return ud.exponent - 1023;
}

Index of LS1B by Popcount

If we have a fast population-count instruction, we can count the trailing zeros of LS1B after subtracting one:

// precondition bb != 0
int bitScanForward(U64 bb) {
   assert (bb != 0);
   return popCount( (bb & -bb) - 1 );
}

Bitscan reverse

A bitscan reverse is used to find the index of the most significant 1 bit (MS1B). For non empty sets it is equivalent to floor of the base-2 logarithm. MS1B isolalation or separation is more expensive than LS1B isolalation or separation, due to the LS1B related Two's complement tricks are not applicable. However, beside Divide and Conquer and Double conversion, Bitscan reverse with MS1B separation is mentioned.

Divide and Conquer

As introduced by Eugene Nalimov in 2000, for an IA-64 version of Crafty ^[12] ^[13]

/**
 * bitScanReverse
 * @author Eugene Nalimov
 * @param bb bitboard to scan
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 bb)
{
   int result = 0;
   if (bb > 0xFFFFFFFF) {
      bb >>= 32;
      result = 32;
   }
   if (bb > 0xFFFF) {
      bb >>= 16;
      result += 16;
   }
   if (bb > 0xFF) {
      bb >>= 8;
      result += 8;
   }
   return result + ms1bTable[bb];
}

Tribute to Frank Zappa

A branchless and little bit obfuscated version of the devide and conquer bitScanReverse with in-register-lookup ^[14] - as tribute to Frank Zappa with identifiers from Freak Out! (1966), Hot Rats (1969), Waka/Jawaka (1972), Sofa (1975), One Size Fits All (1975), Sheik Yerbouti (1979), and Jazz from Hell (1986):

typedef unsigned __int64 OneSizeFits;
typedef unsigned int HotRats;
const HotRats s      =   0;
const HotRats heik   = 457;
const HotRats y      =   1;
const HotRats e      =   2;
const HotRats r      =   3;
const HotRats b      =   4;
const HotRats o      =   5;
const HotRats u      =   8;
const HotRats t      =  16;
const HotRats i      =  32;
const HotRats     ka = (1<< 4)-1;
const HotRats   waka = (1<< 8)-1;
const HotRats jawaka = (1<<16)-1;
const HotRats jazzFromHell = 0-(16*3*heik);
 
HotRats freakOut(OneSizeFits all) {
   HotRats so,fa;
   fa   = (HotRats)(all >> i);
   so   = (fa!=s)       << o;
   fa  ^= (HotRats) all & (fa!=s)-y;
   so  ^= (jawaka < fa) << b;
   fa >>= (jawaka < fa) << b;
   so  ^= (  waka - fa) >> t    & u;
   fa >>= (  waka - fa) >> t    & u;
   so  ^= (    ka - fa) >> u    & b;
   fa >>= (    ka - fa) >> u    & b;
   so  ^=  jazzFromHell >> e*fa & r;
   return so;
}

De Bruijn Multiplication

While the tribute to Frank Zappa is quite 32-bit friendly ^[15], Kim Walisch suggested to use the parallel prefix fill for a MS1B separation with the same De Bruijn multiplication and lookup as in his bitScanForward routine with separated LS1B, with less instructions in 64-bit mode. A log base 2 method was already devised by Eric Cole on January 8, 2006, and shaved off rounded up to one less than the next power of 2 by Mark Dickinson ^[16] on December 10, 2009, as published in Sean Eron Anderson's Bit Twiddling Hacks for 32-bit integers ^[17].

const int index64[64] = {
    0, 47,  1, 56, 48, 27,  2, 60,
   57, 49, 41, 37, 28, 16,  3, 61,
   54, 58, 35, 52, 50, 42, 21, 44,
   38, 32, 29, 23, 17, 11,  4, 62,
   46, 55, 26, 59, 40, 36, 15, 53,
   34, 51, 20, 43, 31, 22, 10, 45,
   25, 39, 14, 33, 19, 30,  9, 24,
   13, 18,  8, 12,  7,  6,  5, 63
};
 
/**
 * bitScanReverse
 * @authors Kim Walisch, Mark Dickinson
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 bb) {
   const U64 debruijn64 = C64(0x03f79d71b4cb0a89);
   assert (bb != 0);
   bb |= bb >> 1; 
   bb |= bb >> 2;
   bb |= bb >> 4;
   bb |= bb >> 8;
   bb |= bb >> 16;
   bb |= bb >> 32;
   return index64[(bb * debruijn64) >> 58];
}

Double conversion

Assuming 64-bit doubles and little-endian structure (not portable!). Conversion to a double, interpreting the exponent. To avoid possible rounding errors, some lower bits may be cleared.

/**
 * bitScanReverse
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @return index (0..63) of most significant one bit
 *         -1023 if passing zero
 */
int bitScanReverse(U64 bb)
{
   union {
      double d;
      struct {
         unsigned int mantissal : 32;
         unsigned int mantissah : 20;
         unsigned int exponent : 11;
         unsigned int sign : 1;
      };
   } ud;
   ud.d = (double)(bb & ~(bb >> 32));  // avoid rounding error
   return ud.exponent - 1023;
}

Leading Zero Count

Some processors have a fast leading zero count instruction. The Motorola 68020 has a bit field find first one instruction (BFFFO), which actually performs an up to 32-bit Leading Zero Count ^[18] . x86-64 AMD K10 has lzcnt as part of the SSE4a extension ^[19] ^[20] , BMI1 has lzcnt as well, while AVX-512CD even features leading zero count on vectors of eight bitbaords.

One can replace bitScanReverse of non empty sets by leadingZeroCount xor 63. Like trailing zero count, it returns 64 for empty sets, and might therefor save the leading condition in some applications.

Bitscan versus Zero Count

While the presented bitscan routines are suited to work only on none empty sets and return a value-range from 0 to 63 as bit-index, leading or trailing zero-count instructions or routines leave 64 for empty sets. Zero-counting has a immanent property of dealing correctly with empty sets - while it likely takes a conditional branch to implement this semantic in bit-scanning.

int trailingZeroCount(U64 bb) {
    if ( bb )
       return bitScanForward(bb);
    return 64;
}
 
int leadingZeroCount(U64 bb) {
    if ( bb )
       return bitScanReverse(bb) ^ 63;
    return 64;
}

Bitscan with Reset

While traversing sets, one may combine bitscanning with reset found bit. That implies passing the bitboard per reference or pointer, and tends to confuse compilers to keep all inside registers inside a typical serialization loop ^[21] .

int bitScanForwardWithReset(U64 &bb) { // also called dropForward
    int idx = bitScanForward(bb);
    bb &= bb - 1; // reset bit outside
    return idx;
}

Generalized Bitscan

This generalized bitscan uses a boolean parameter to scan reverse or forward. It relies on bitScanReverse, but conditionally masks the LS1B in case of scanning forward. It might be used in the classical approach to get positive or negative ray directions with one generalized routine.

 /**
 * generalized bitScan
 * @author Gerd Isenberg
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @param reverse, true bitScanReverse, false bitScanForward
 * @return index (0..63) of least/most significant one bit
 */
 int bitScan(U64 bb, bool reverse) {
    U64 rMask;
    assert (bb != 0);
    rMask = -(U64)reverse;
    bb &= -bb | rMask;
    return bitScanReverse(bb);
 }

Processor Instructions for Bitscans

x86

x86-64 processors have bitscan instructions and can be accessed with compilers today through either inline assembly or compiler intrinsics. For the Microsoft/Intel C compiler, the intrinsics can be accessed by including and using the instructions _BitScanForward64 ^[22] , _BitScanReverse64 ^[23] or _lzcnt64 ^[24] .

unsigned char_BitScanForward64(unsigned long * Index,  unsigned __int64 Mask);
unsigned char _BitScanReverse64(unsigned long * Index,  unsigned __int64 Mask);
unsigned __int64 __lzcnt64(unsigned __int64 value); // AMD K10 only see CPUID

Linux provides library functions ^[25] , find first bit set (ffsll) in a word leaves an index of 1..64, and zero of no bit is set ^[26] . GCC 4.4.5 further has the Built-in Function _builtin_ffsll for finding the least significant one bit, _builtin_ctzll for trailing, and _builtin_clzll for leading zero count ^[27] :

/* Returns one plus the index of the least significant 1-bit of x, or if x is zero, returns zero */
int __builtin_ffsll (unsigned long long);
 
/* Returns the number of trailing 0-bits in x, starting at the least significant bit position.
   If x is 0, the result is undefined */
int __builtin_ctzll (unsigned long long);
 
/* Returns the number of leading 0-bits in x, starting at the most significant bit position.
   If x is 0, the result is undefined */
int __builtin_clzll (unsigned long long);

Emulating Intrinsics

For the GNU C compiler, the intrinsics can be emulated with inline assembly ^[28] .

//These processor instructions work only for 64-bit processors
#ifdef _MSC_VER
    #include <intrin.h>
    #ifdef _WIN64
        #pragma intrinsic(_BitScanForward64)
        #pragma intrinsic(_BitScanReverse64)
        #define USING_INTRINSICS
    #endif
#elif defined(__GNUC__) && defined(__LP64__)
    static INLINE unsigned char _BitScanForward64(unsigned long* Index, U64 Mask)
    {
        U64 Ret;
        __asm__
        (
            "bsfq %[Mask], %[Ret]"
            :[Ret] "=r" (Ret)
            :[Mask] "mr" (Mask)
        );
        *Index = (unsigned long)Ret;
        return Mask?1:0;
    }
    static INLINE unsigned char _BitScanReverse64(unsigned long* Index, U64 Mask)
    {
        U64 Ret;
        __asm__
        (
            "bsrq %[Mask], %[Ret]"
            :[Ret] "=r" (Ret)
            :[Mask] "mr" (Mask)
        );
        *Index = (unsigned long)Ret;
        return Mask?1:0;
    }
    #define USING_INTRINSICS
#endif

Intrinsics versus asm

Alternatively, rather than to emulate the intrinsics one might use the standard prototype, by using intrinsics or inline assembly for GCC ^[29] :

#ifdef USE_X86INTRINSICS
#include <intrin.h>
#pragma intrinsic(_BitScanForward64)
#pragma intrinsic(_BitScanReverse64)
 
/**
 * bitScanForward
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 x) {
   unsigned long index;
   assert (x != 0);
   _BitScanForward64(&index, x);
   return (int) index;
}
 
/**
 * bitScanReverse
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 x) {
   unsigned long index;
   assert (x != 0);
   _BitScanReverse64(&index, x);
   return (int) index;
}
#else
 
/**
 * bitScanForward
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of least significant one bit
 */
int bitScanForward(U64 x) {
   assert (x != 0);
   asm ("bsfq %0, %0" : "=r" (x) : "0" (x));
   return (int) x;
}
 
/**
 * bitScanReverse
 * @param bb bitboard to scan
 * @precondition bb != 0
 * @return index (0..63) of most significant one bit
 */
int bitScanReverse(U64 x) {
   assert (x != 0);
   asm ("bsrl %0, %0" : "=r" (x) : "0" (x));
   return (int) x;
}
#endif

Bsf/Bsr x86-64 Timings

The instruction latency and reciprocal throughput ^[30] heavily differs between various x86-64 architectures:

Architecture Stepping	Instruction(s)	Latency / Cycles	Reciprocal Throughput
AMD
K8 ^[31]	BSF reg16/32/64, mreg16/32/64	Vector Path 8/8/9	8/8/9
K8 ^[31]	BSR reg16/32/64, mreg16/32/64	Vector Path 11	11
K10 ^[32]	BSF reg, reg	Vector Path 4	4
	BSR reg, reg	Vector Path 4	4
	LZCNT reg, reg	Direct Path single 2	1
Intel ^[33]
ATOM	BSF/BSR	16	15
NetBurst 0F_3H	BSF/BSR	16	4
NetBurst 0F_2H	BSF/BSR	8	2
Core 06_0EH	BSF/BSR	2	1
65 nm Intel Core 06_0FH	BSF/BSR	2	1
Enhanced Intel Core 06_17H	BSF/BSR	1	1
Enhanced Intel Core 06_1DH	BSF/BSR	1	1
Nehalem 06_1AH	BSF/BSR	3	1
Sandy Bridge Ivy Bridge Haswell ^[34]	BSF/BSR	3	1
	LZCNT	3	1
	TZCNT	3	1

Bsf/Bsr behavior with zero source

Intel and AMD specify different behavior. In praxis there seems no difference so far. However, as long as Intel docs explicitly state content undefined, it is recommend to don't rely on a pre-initialized content of that target register, if the source is zero.

Intel : If the content of the source operand is 0, the content of the destination operand is undefined. ^[35]
AMD: If the second operand contains 0, the instruction sets ZF to 1 and does not change the contents of the destination register. ^[36]

ARM

ARM has CLZ (Count Leading Zeros) instruction for 32-bit integers. ARM instruction is available in ARMv5 and above, 32-bit Thumb instruction is available in ARMv6T2 and ARMv7 ^[37] , the C-intrinsic is called _builtin_clz ^[38] ^[39] ^[40] .

Engine Samples

Publications

Alan Turing (1949). Alan Turing's Manual for the Ferranti Mk. I. transcribed in 2000 by Robert Thau, pdf from The Computer History Museum, 9.4 The position of the most significant digit » Ferranti Mark 1
Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf
Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p. 10
Andreas Stiller (2013). Spezialkommando - Bits setzen, abfragen, scannen und mehr. c't Magazin für Computertechnik 7/2013, p. 186 (German)

Forum Posts

1996 ...

Bitboards: speeding up FirstOne by Laurent Desnogues, rgcc, April 10, 1996 » Othello
bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 6, 1996
bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 7, 1996
bitboard 2^i mod 67 is unique by Joël Rivat, rgcc, September 2, 1996
Question to Bob: Crafty , Alpha and FindBit() by Guido Schimmels, CCC, June 05, 1998
To Nalimov and other programmers about BSF/BSR in VC by Dezhi Zhao, CCC, January 16, 1999

2000 ...

Re: TASM 5.0 versus BSF by Frans Morsch, comp.lang.asm.x86, March 28, 2000
Will the Itanium have a BSF or BSR instruction? by Larry Griffiths, CCC, August 15, 2000
Re: Will the Itanium have a BSF or BSR instruction? by Eugene Nalimov, CCC, August 16, 2000
Binary question by Severi Salminen, CCC, October 19, 2000
Bitboards and Piece Lists by Dann Corbit, CCC, June 14, 2001
FirstBit() in assembler by David Rasmussen, CCC, January 13, 2002
Reply from Intel about BSF/BSR by Severi Salminen, CCC, January 31, 2002
"Using de Bruijn Sequences to Index a 1 in a Computer Word" by Oliver Roese, CCC, February 08, 2002
Another hacky method for bitboard bit extraction by Walter Faxon, CCC, November 17, 2002
Modulo verus BitScan and MMX-PopCount by Gerd Isenberg, CCC, November 29, 2002
Fast 3DNow! BitScan by Gerd Isenberg, CCC, December 01, 2002
Bitscan Conclusions by Matt Taylor, CCC, January 05, 2003
Bitscan by Matt Taylor, CCC, February 11, 2003
FirstOne for Linux by Sune Fischer, CCC, March 29, 2003
Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
Re: De Bruijn Sequence Generator by Dieter Bürssner, CCC, December 30, 2003 » De Bruijn Sequence Generator
Determining location of LSB/MSB by Renze Steenhuisen, CCC, February 09, 2004
Nalimov: bsf/bsr intrinsics implementation still not optimal by Dezhi Zhao, CCC, September 22, 2004
Re: Nalimov: bsf/bsr intrinsics implementation still not optimal by Eugene Nalimov, CCC, September 23, 2004

2005 ...

A data point for PowerPC bitboard program authors by Steven Edwards, CCC, May 09, 2005 » PowerPC
Best BitBoard LSB funktion? by Reinhard Scharnagl, Winboard Programming Forum, July 20, 2005
Fastest bitboard compress routine when you can't use ASM by mambofish, CCC, May 31, 2007
Bit twiddling question, part 2: arbitrary bitscan order by Zach Wegner, CCC, August 11, 2009
32 bit versions for bitscan64 by Michael Hoffmann, CCC, August 21, 2009
64-bit intrinsic performance by Nathan Thom, CCC, October 27, 2009
Bit Scan (equivalent to ASM instructions bsr and bsf) by Pascal Georges, CCC, December 24, 2009

2010 ...

bitScanReverse32 by Luca Hemmerich, CCC, January 25, 2010
Introduction and (hopefully) contribution - bitboard methods by Alcides Schulz, CCC, June 03, 2011 » Population Count
Leading Zero Count Question by Matthew R. Brades, CCC, September 16, 2012
Optimizing bitboards for ARM by Martin Sedlak, CCC, November 17, 2012
Symmetric move generation using bitboards by Lasse Hansen, CCC, December 20, 2014
Stockfish 32-bit and hardware instructions on MSVC++ by Syed Fahad, CCC, December 30, 2014 » Stockfish, BitScan, Population Count

2015 ...

Fun with De Bruijn by Henk van den Belt, CCC, August 27, 2015
Re: Linux Version of Maverick 1.5 by Michael Dvorkin, CCC, November 12, 2015 » OS X, Maverick
syzygy users (and Ronald) by Robert Hyatt, CCC, September 29, 2016 » Population Count

External Links

Find first set from Wikipedia
The Aggregate Magic Algorithms by Hank Dietz
Bit Twiddling Hacks by Sean Eron Anderson
An Efficient Bit-Reversal Sorting Algorithm for the Fast Fourier Transform by Jennifer Elaan, January 16, 2005
Efficient bit scan mechanism - United States Patent 6172623 from FreePatentsOnline.com
Frank Zappa & the Mothers - King Kong BBC Studio Recording 1968, YouTube Video

References

^ Picture gallery "Back in Holland 1941 - 1954" from The Official M.C. Escher Website
^ Chip Architect: Detailed Architecture of AMD's Opteron - 1.3 A third class of Instructions by Hans de Vries
^ Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p 10
^ Charles E. Leiserson, Harald Prokop and Keith H. Randall (1998). Using de Bruijn Sequences to Index a 1 in a Computer Word, pdf
^ "Using de Bruijn Sequences to Index a 1 in a Computer Word" discussion in CCC, February 08, 2002
^ N. G. de Bruijn (1975). Acknowledgement of priority to C. Flye Sainte-Marie on the counting of circular arrangements of 2n zeros and ones that show each n-letter word exactly once. Technical Report, Technische Hogeschool Eindhoven, available as pdf reprint
^ Bit magic by Matt Taylor, comp.lang.asm.x86, June 26, 2003
^ Another hacky method for bitboard bit extraction by Walter Faxon, CCC, November 17, 2002
^ bitboard 2^i mod 67 is unique by Stefan Plenkner, rgcc, August 6, 1996
^ Pablo San Segundo, Ramón Galán (2005). Bitboards: A New Approach. AIA 2005
^ Best BitBoard LSB funktion? by Reinhard Scharnagl, Winboard Programming Forum, July 20, 2005
^ Re: Will the Itanium have a BSF or BSR instruction? by Eugene Nalimov, CCC, August 16, 2000
^ ms1bTable array in Eugene Nalimovs bitScanReverse by Stef Luijten, CCC, April 17, 2011
^ just another reverse bitscan by Gerd Isenberg, CCC, December 22, 2005
^ final version - homage to FZ by Gerd Isenberg, CCC, December 23, 2005
^ EuroPython 2012: Florence, July 2–8 | Mark Dickinson
^ Find the log base 2 of an N-bit integer in O(lg(N)) operations with multiply and lookup from Bit Twiddling Hacks by Sean Eron Anderson
^ 68020 Bit Field Instructions
^ SSE4a from Wikipedia
^ __lzcnt16, __lzcnt, __lzcnt64 Visual C++ Language Reference
^ Bitscan by Matt Taylor, CCC, February 11, 2003
^ _BitScanForward, _BitScanForward64 Visual C++ Language Reference
^ _BitScanReverse, _BitScanReverse64 Visual C++ Language Reference
^ __lzcnt16, __lzcnt, __lzcnt64 Visual C++ Language Reference
^ Section 3: library functions - Linux man pages
^ ffsll(3): find first bit set in word - Linux man page
^ Other Builtins - Using the GNU Compiler Collection (GCC)
^ Re: Nalimov: bsf/bsr intrinsics implementation still not optimal by Eugene Nalimov, CCC, September 23, 2004
^ Matters Computational - ideas, algorithms, source code (pdf) Ideas and Source Code by Jörg Arndt
^ Instruction tables, Lists of instruction latencies, throughputs and microoperation breakdowns for Intel and AMD CPU's (pdf) by Agner Fog
^ Software Optimization Guide for AMD64 Processors
^ Software Optimization Guide for AMD Family 10h and 12h Processors
^ Intel 64 and IA32 Architectures Optimization Reference Manual
^ Haswell Instructions Latency
^ Intel® 64 and IA-32 Architectures Software Developer’s Manual Volume 2A: Instruction Set Reference, A-M (pdf) BSF—Bit Scan Forward 3-87
^ AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions (pdf) Bit Scan Forward pg. 111
^ ARM Information Center > General data processing instructions > CLZ
^ ARM Information Center > Instruction intrinsics > __builtin_clz
^ Other Builtins - Using the GNU Compiler Collection (GCC)
^ Bit Scan (equivalent to ASM instructions bsr and bsf) by Pascal Georges, CCC, December 24, 2009

What links here?

Page	Date Edited
68020	Jun 7, 2016
Alcides Schulz	Mar 29, 2018
Algorithms	May 5, 2017
Amundsen	Sep 3, 2013
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
AVX-512	Aug 8, 2017
Backtracking	Dec 16, 2017
Beowulf	May 5, 2017
Bison	Sep 29, 2016
Bit	Oct 29, 2012
Bit-Twiddling	Nov 6, 2017
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Bitfoot	Sep 8, 2015
BitScan	Sep 10, 2017
Blockage Detection	Oct 19, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Bobcat	Jun 27, 2017
Brainless	Jun 24, 2017
Cassandre	Jul 5, 2013
Charles Leiserson	Oct 12, 2016
CHEOPS	Apr 18, 2015
Chess 0.5	Nov 20, 2016
Chezzz	Jan 20, 2013
Classical Approach	Jan 28, 2018
Congruent Modulo Bitboards	Jun 26, 2013
CookieCat	Nov 15, 2016
Crafty	Jan 28, 2018
Cray-1	Dec 25, 2017
Cupcake	May 19, 2016
Daniel White	Feb 9, 2016
David Rasmussen	Dec 16, 2017
De Bruijn sequence	Feb 20, 2018
De Bruijn Sequence Generator	Dec 1, 2016
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Dieter Bürssner	Dec 1, 2016
Djinn	Feb 8, 2016
Double	May 30, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Encoding Moves	Mar 27, 2016
Eugene Nalimov	Dec 23, 2016
Ferranti Mark 1	Jun 2, 2015
Fizbo	Dec 22, 2017
Float	Nov 11, 2016
Gaviota	Jan 21, 2018
General Setwise Operations	Feb 25, 2018
Gibbon	Dec 23, 2014
Gk	Oct 9, 2017
Guido Schimmels	Apr 23, 2013
Hakkapeliitta	Apr 26, 2016
Harald Prokop	Nov 29, 2017
Hash Table	Jan 1, 2018
HeavyChess	Feb 14, 2014
Ifrit	Feb 7, 2016
Intel	Aug 29, 2015
Itanium	Aug 29, 2015
Jan Renze Steenhuisen	Sep 10, 2017
Java-Bitscan	Mar 15, 2014
Joël Rivat	Jul 21, 2017
Joker IT	Sep 16, 2017
Keith H. Randall	Jun 16, 2015
Kim Walisch	Aug 10, 2017
King of Kings	Sep 4, 2013
King Pattern	Nov 15, 2013
Knight Pattern	Feb 23, 2015
Koundinya Veluri	Feb 2, 2013
Kurt	Apr 20, 2014
Leila	May 8, 2017
Little Wing	Oct 26, 2017
Luca Hemmerich	Jun 19, 2017
Mac OS	Mar 25, 2016
Martin Sedlak	Dec 25, 2017
Mathematician	Apr 9, 2018
Matt Taylor	Feb 17, 2013
Matthew R. Brades	Jun 9, 2017
Michael Dvorkin	Jan 8, 2016
Mikhail R. Shura-Bura	Oct 30, 2013
Murka	Nov 11, 2016
Nathan Thom	Mar 15, 2013
Nicolaas de Bruijn	Feb 3, 2015
NoraGrace	Nov 23, 2014
Obstruction Difference	May 27, 2016
Othello	Jan 4, 2018
Pablo San Segundo	Feb 25, 2015
Paladin	Jan 29, 2017
Pascal Georges	Jun 1, 2014
PIC Microcontroller	Oct 27, 2017
Pieces versus Directions	Oct 6, 2016
Population Count	Sep 3, 2017
PowerPC	Oct 6, 2017
Prophet	Sep 30, 2017
Ramón Galán	Feb 25, 2015
RedQueen	Nov 13, 2017
Reinhard Scharnagl	Apr 9, 2016
Reverse Bitboards	Aug 29, 2015
Robert Hyatt	Dec 25, 2017
Robocide	May 11, 2016
SBAMG	Dec 4, 2016
Scorpio	Mar 28, 2018
Searcher	Sep 26, 2016
Senpai	Nov 10, 2017
Severi Salminen	May 7, 2015
Shifted Bitboards	Jan 9, 2011
Sliding Piece Attacks	May 27, 2016
Space-Time Tradeoff	Jun 17, 2015
Spector	Nov 11, 2016
SSE4	Jun 5, 2016
Stef Luijten	Apr 26, 2015
Stefan Plenkner	Dec 31, 2015
Stockfish	Apr 7, 2018
Sune Fischer	Apr 7, 2014
Sungorus	Apr 11, 2014
Syed Fahad	Jan 1, 2017
Thor's Hammer	Nov 23, 2013
Traversing Subsets of a Set	Oct 14, 2016
Tucano	Dec 16, 2017
Tunguska	Sep 16, 2017
Vadim Demichev	Jul 26, 2013
Vice	Mar 8, 2016
Walter Faxon	Mar 6, 2015
Warrior	Feb 23, 2015
Wasp	Nov 24, 2017
X-ray Attacks (Bitboards)	Mar 31, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
x86-64 Instructions to Include	Feb 12, 2011
Zurichess	Mar 12, 2018

Up one Level

BMI1

GerdIsenberg — Mon, 24 Mar 2014 16:20:29 GMT

Home * Hardware * x86-64 * BMI1

BMI1 (BMI),
an x86-64 expansion of bit-manipulation instructions by Intel, introduced in conjunction with the Advanced Vector Extensions SIMD instruction set. With the Bulldozer microarchitecture, BMI1 as well as AVX are also available on AMD processors under the initial name BMI, along with their Trailing Bit Manipulation Instructions (TBM) ^[1]. Most BMI1 instructions (except LZCNT and TZCNT) employ the VEX prefix encoding to support up to three-operand syntax with non-destructive source operands on 32- or 64-bit general-purpose registers. BMI1 (ANDN, BEXTR, BLSI, BLSMK, BLSR, TZCNT) requires bit 3 set in EBX of CPUID with EAX=07H, ECX=0H. LZCNT, not exactly member of BMI1, requires bit 5 set in ECX of CPUID EAX=80000001H. With the advent of AVX2, some more bit-twiddling on general-purpose registers is proposed with BMI2.

Instructions

BMI1 instructions may speedup various bitboard operations, such as relative complement, and isolation, reset and separation of the least significant one bit, they combine two instructions and reduce register pressure. Leading and trailing zero count are useful for scanning bits with possibly empty sets.

ANDN

Logical And Not, the relative complement, no intrinsic due to compiler support.

dest ::= ~src1 & src2;

BEXTR

Bit Field Extract ^[2]. Nice to extract some consecutive bits from a (rotated) occupancy bitboard, or, as they name suggests, from bit-field structures.

dest ::= (src >> start) & ((1 << len)-1);
 
unsigned __int32 _bextr_u32(unsigned __int32 src, unsigned __int32 start, unsigned __int32 len);
unsigned __int64 _bextr_u64(unsigned __int64 src, unsigned __int32 start, unsigned __int32 len);

A shiftless sign extension might be applied by ^[3]:

dest_signextended ::= (dest ^ signbit) - signbit

BLSI

Extract Lowest Set Isolated Bit ^[4], isolates least significant one bit.

dest ::= src & -src;
 
unsigned __int64 _blsi_u64(unsigned __int64 src);

BLSMSK

Get Mask Up to Lowest Set Bit ^[5], sets all bits below the least significant one bit, and clears all upper bits.

dest ::= (src-1) ^ src;
 
unsigned __int64 _blsmsk_u64(unsigned __int64 src);

BLSR

Reset Lowest Set Bit ^[6], resets least significant one bit.

dest ::= (src-1) & src;
 
unsigned __int64 _blsr_u64(unsigned __int64 src);

LZCNT

Count the Number of Leading Zero Bits ^[7], initially from AMD's SSE4a aka Advanced Bit Manipulations (ABM). If not supported, processor executes BSR ^[8] presumly with xor 63.

unsigned __int64 _lzcnt_u64(unsigned __int64 src);

TZCNT

Count the Number of Trailing Zero Bits ^[9]. If not supported, processor executes BSF ^[10].

unsigned __int64 _tzcnt_u64(unsigned __int64 src);

Manuals

Intel AVX and AVX2 Programming Reference (pdf)
AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions (pdf) ^[11]
Software Optimization Guide for AMD Family 15h Processors (pdf) 9.9 Optimizing with BMI and TBM Instructions, pp. 163

External Links

References

^ AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions (pdf)
^ _bextr_u32/64
^ Sign Extension from The Aggregate Magic Algorithms by Hank Dietz
^ _blsi_u32/64
^ _blsmsk_u32/64
^ _blsr_u32/64
^ _lzcnt_u32/64
^ Intel AVX and AVX2 Programming Reference (pdf), 7-14 LZCNT— Count the Number of Leading Zero Bits
^ _tzcnt_u32/64
^ Intel AVX and AVX2 Programming Reference (pdf), 7-27 TZCNT — Count the Number of Trailing Zero Bits
^ Moved BMI and TBM instructions from Volume 4 to Volume 3 in September 2011

What links here?

Page	Date Edited
AVX	Mar 7, 2017
Bit-Twiddling	Nov 6, 2017
BitScan	Sep 10, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
General Setwise Operations	Feb 25, 2018
Intel	Aug 29, 2015
Robocide	May 11, 2016
Score	Apr 14, 2018
SSE4	Jun 5, 2016
TBM	Jun 28, 2012
x86-64	Mar 6, 2018

Up one Level

BMI2

GerdIsenberg — Tue, 06 Mar 2018 11:06:12 GMT

Home * Hardware * x86-64 * BMI2

BMI2,
an x86-64 expansion of bit-manipulation instructions by Intel. Like BMI1, BMI2 employs VEX prefix encoding to support three-operand syntax with non-destructive source operands on 32- or 64-bit general-purpose registers. Along with AVX2, BMI2 was expected to be part of Intel's Haswell architecture planned for 2013, but was not yet available in one of the first tested Haswell generations of mid 2013 as reported by Andreas Stiller from the German c't magazine ^[1]. BMI2 requires bit 8 set in EBX of CPUID with EAX=07H, ECX=0H ^[2]. In 2017, BMI2 was further incorporated in AMD's Zen-architecture but so far with a slow implementation of critical instructions such as PDEP and PEXT ^[3] ^[4] .

Instructions

Beside the instructions explained in more detail below, there is MULX, Unsigned Multiply, and RORX, SARX/SHLX/SHRX, that is rotate and shifts without affecting processor flags. PEXT and PDEP ^[5] allow for an alternative of kindergarten- or magic bitboards, and clearly makes maintaining rotated bitboards obsolete ^[6].

BZHI

Zero High Bits Starting with Specified Bit Position ^[7].

dest ::= src & ((1 << index)-1);
 
unsigned __int64 _bzhi_u64(unsigned __int64 src, unsigned __int32 index);

PDEP

Parallel Bits Deposit ^[8]. May be used to map first rank attacks to any rank, file, or diagonal on the chess board.

Intrinsic Prototype

unsigned __int64 pdep_u64(unsigned __int64 src, unsigned __int64 mask);

Sample

SRC1   ┌───┬───┬───┬───┬───┐    ┌───┬───┬───┬───┬───┬───┬───┬───┐
       │S63│S62│S61│S60│S59│....│ S7│ S6│ S5│ S4│ S3│ S2│ S1│ S0│ 
       └───┴───┴───┴───┴───┘    └───┴───┴───┴───┴───┴───┴───┴───┘
 
SRC2   ┌───┬───┬───┬───┬───┐    ┌───┬───┬───┬───┬───┬───┬───┬───┐
(mask) │ 0 │ 0 │ 0 │ 1 │ 0 │0...│ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │  (f.i. 4 bits set)
       └───┴───┴───┴───┴───┘    └───┴───┴───┴───┴───┴───┴───┴───┘
 
DEST   ┌───┬───┬───┬───┬───┐    ┌───┬───┬───┬───┬───┬───┬───┬───┐
       │ 0 │ 0 │ 0 │ S3│ 0 │0...│ S2│ 0 │ S1│ 0 │ 0 │ S0│ 0 │ 0 │ 
       └───┴───┴───┴───┴───┘    └───┴───┴───┴───┴───┴───┴───┴───┘

Serial Implementation

in C ^[9]:

U64 _pdep_u64(U64 val, U64 mask) {
  U64 res = 0;
  for (U64 bb = 1; mask; bb += bb) {
    if (val & bb)
      res |= mask & -mask;
    mask &= mask - 1;
  }
  return res;
}

PEXT

Parallel Bits Extract ^[10]. Great to get the inner six bit occupancy of any rank, file, or diagonal as index of six consecutive lower bit, or the up to 12 bits for a magic attack lookup.

Intrinsic Prototype

unsigned __int64 _pext_u64(unsigned __int64 src, unsigned __int64 mask);

Sample

SRC1   ┌───┬───┬───┬───┬───┐    ┌───┬───┬───┬───┬───┬───┬───┬───┐
       │S63│S62│S61│S60│S59│....│ S7│ S6│ S5│ S4│ S3│ S2│ S1│ S0│ 
       └───┴───┴───┴───┴───┘    └───┴───┴───┴───┴───┴───┴───┴───┘
 
SRC2   ┌───┬───┬───┬───┬───┐    ┌───┬───┬───┬───┬───┬───┬───┬───┐
(mask) │ 0 │ 0 │ 0 │ 1 │ 0 │0...│ 1 │ 0 │ 1 │ 0 │ 0 │ 1 │ 0 │ 0 │  (f.i. 4 bits set)
       └───┴───┴───┴───┴───┘    └───┴───┴───┴───┴───┴───┴───┴───┘
 
DEST   ┌───┬───┬───┬───┬───┐    ┌───┬───┬───┬───┬───┬───┬───┬───┐
       │ 0 │ 0 │ 0 │ 0 │ 0 │0...│ 0 │ 0 │ 0 │ 0 │S60│ S7│ S5│ S2│ 
       └───┴───┴───┴───┴───┘    └───┴───┴───┴───┴───┴───┴───┴───┘

Serial Implementation

in C ^[11], quite similar to PDEP in traversing the mask, and only two expressions, "mask & -mask" and "bb" swapped:

U64 _pext_u64(U64 val, U64 mask) {
  U64 res = 0;
  for (U64 bb = 1; mask; bb += bb) {
    if ( val & mask & -mask )
      res |= bb;
    mask &= mask - 1;
  }
  return res;
}

Applications

PEXT Bitboards

Fancy PEXT Bitboards as replacement for Fancy Magic Bitboards. The relevant up to four ray occupancies are mapped to a dense index range by using the PEXT instruction:

U64 arrAttacks  [...]; // ~840 KByte all rook and bishop attacks
U64 arrRookMask  [64]; // 10..12 relevant occupancy bits per rook square
U64 arrBishopMask[64]; //  5.. 9 relevant occupancy bits per bishop square
U32 arrRookBase  [64]; // arrAttacks base offset per rook square
U32 arrBishopBase[64]; // arrAttacks base offset per bishop square
 
U64 rookAttack(U64 occ, enumSquare sq) {
  return arrAttacks[arrRookBase[sq] + _pext_u64(occ, arrRookMask[sq])];
}
 
U64 bishopAttack(U64 occ, enumSquare sq) {
  return arrAttacks[arrBishopBase[sq] + _pext_u64(occ, arrBishopMask[sq])];
}

PEXT/PDEP Bitboards

An idea for denser sliding attack tables is also using PDEP, dividing the table size of the PEXT Bitboards by four but some trailing computation. Looking up 16-bit words instead of bitboards - to get the scattered bits of the up to four ray attacks per square in an extracted form mapped to a 16-bit word, which then becomes the attack bitboard by performing a deposit instruction with an appropriate second mask per square. The technique was introduced by Zach Wegner in CCC ^[12] ^[13] and implemented by Ronald de Man with a table of slightly more than 210 KiB ^[14] ^[15]. Ronald's code was tested by Jean-Francois Romang using Stockfish as testbed, giving promising results ^[16] ^[17].

Syzygy Generator

Ronald de Man's generator for Syzygy Bases can take profit of PDEP and PEXT instructions, or to use their serial implementations to further reduce the size of his already compact endgame tablebases ^[18].

Manuals

Intel AVX and AVX2 Programming Reference (pdf)

Forum Posts

Haswell New Instructions by Zach Wegner, CCC, September 09, 2011
Bit manipulations using BMI2 by Jack Lloyd, / :: bitbashing, June 22, 2012
PEXT Bitboards by Gerd Isenberg, CCC, June 07, 2013
152k rook and bishop attacks using PEXT and PDEP by Lasse Hansen, CCC, October 06, 2013
Stockfish haswell optimized build by Jean-Francois Romang, CCC, April 06, 2014 » Stockfish
smaller tables for PEXT-style attack getters by Wylie Garvin, CCC, January 13, 2016
BMI2 intrinsics in gcc by Álvaro Begué, CCC, May 14, 2017
Ryzen Fritz Chess Benchmarks ? by ralunger, Rybka Forum, March 03, 2017
Ryzen and BMI2: Strange behavior and high latencies by DonnieTinyHands, Reddit, March 20, 2017 » AMD, BMI2 PEXT
BMI2 PEXT idea for attacks generation by Mark Lefler, CCC, September 16, 2017
Re: Komodo 11.3 by Mark Lefler, CCC, March 04, 2018 » AMD, BMI2 PEXT, Komodo 11.3

External Links

References

^ Andreas Stiller (2013). Der Rechenkünstler. c't Magazin für Computertechnik 14/2013, p. 114-119 (German)
^ How to detect New Instruction support in the 4th generation Intel® Core™ processor family | Intel® Developer Zone by Max Locktyukhin, August 05, 2013
^ Ryzen Fritz Chess Benchmarks ? by ralunger, Rybka Forum, March 03, 2017
^ Ryzen and BMI2: Strange behavior and high latencies by DonnieTinyHands, Reddit, March 20, 2017 » AMD, BMI2 PEXT
^ Ruby Lee, Zhijie Shi, Xiao Yang (2001). Efficient Permutation Instructions for Fast Software Cryptography. Micro, IEEE, Vol. 21, No. 6, pdf
^ Haswell New Instructions by Zach Wegner, CCC, September 09, 2011
^ _bzhi_u32/u64
^ _pdep_u32/u64
^ Re: PEXT Bitboards by Ronald de Man, CCC, June 07, 2013
^ _pext_u32/u64
^ Re: PEXT Bitboards by Gerd Isenberg, CCC, June 07, 2013
^ Haswell New Instructions by Zach Wegner, CCC, September 09, 2011
^ Re: Haswell New Instructions by Gerd Isenberg, CCC, September 12, 2011
^ Re: 152k rook and bishop attacks using PEXT and PDEP by Ronald de Man, CCC, October 06, 2013
^ tb/src/bmi2.h at master · syzygy1/tb · GitHub by Ronald de Man
^ Re: Stockfish haswell optimized build by Jean-Francois Romang, CCC, April 06, 2014
^ Stockfish/src/bitboard.h at bmi2 · jromang/Stockfish · GitHub by Jean-Francois Romang
^ Re: PEXT Bitboards by Ronald de Man, CCC, June 07, 2013

What links here?

Page	Date Edited
AMD	Mar 9, 2018
Andscacs	Jan 16, 2018
Arasan	Apr 8, 2018
asmFish	Feb 14, 2018
AVX	Mar 7, 2017
AVX2	Aug 8, 2017
Bit-Twiddling	Nov 6, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Cpp	Oct 24, 2017
Fizbo	Dec 22, 2017
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
GullChess	Jun 27, 2017
Intel	Aug 29, 2015
Komodo	Mar 6, 2018
Lasse Hansen	Sep 1, 2015
Magic Bitboards	Apr 13, 2018
Senpai	Nov 10, 2017
Sliding Piece Attacks	May 27, 2016
Stockfish	Apr 7, 2018
Syzygy Bases	Apr 19, 2018
TBM	Jun 28, 2012
Winter	Jan 23, 2018
x86-64	Mar 6, 2018
Xiphos	Apr 22, 2018

Up one Level

Byte

GerdIsenberg — Fri, 05 Apr 2013 17:31:50 GMT

Home * Programming * Data * Byte

A Byte, more precise an Octet, is a unit of measurement of information storage, consisting of eight bits. In most computer architectures it is the granularity of memory addresses, containing 8-bit numbers, 256 different symbols - interpreted as signed or unsigned numbers, ASCII characters or machine code. Processors provide byte-wise arithmetical and logical units. x86 and x86-64 can address the two lower bytes of each 32 or 64 bit register, for instance AL and AH from EAX or RAX. SIMD instruction sets like MMX, AltiVec and SSE2 provide operations on vectors of eight or sixteen bytes inside appropriate SIMD-registers.

The programming languages C and C++ define a byte as a "addressable unit of data storage large enough to hold any member of the basic character set of the execution environment".

Char

The C-datatype unsigned char cover one byte and has a numerical range of 0 to 255. The primitive char in Java is a signed byte, and ranges from -128 to +127. Same is likely true for signed char in C, though two's complement is not strictly specified. Same is true for signed right shifts, where x86 performs shift arithmetical right, but other processors and their compilers eventually shift in always zeros. Bytes are therefor often type defined as unsigned char in C:

typedef unsigned char BYTE;

Mailbox chess programs often use an array of bytes for a dense Board Representation, where each byte contains piece- or empty square code for each indexed square. A Byte is also sufficient to store usual (0..63), or 0x88 board coordinates. A byte can contain a rank of a bitboard. For pawn-structure issues, filesets are a dense set-wise representation to cover boolean properties for each file.

A byte can be written with two hexadecimal digits, 0x00 to 0xff in C or Java. Take care and compiler warnings serious, if wider types are assigned to bytes - since all upper bits are lost, if wider types are outside the valid signed or unsigned range.

SWAR Bytes

To apply 'add' or 'sub' on vectors of bytes (or any arbitrary structure) SWAR-wise within a 32-bit or 64-bit register, we have to take care carries and borrows don't wrap around. Thus we apply a mask of all most significant bits (H) and 'add' in two steps, one 'add' with MSB clear and one add modulo 2 aka 'xor' for the MSB itself. For byte-wise math of a vector of four bytes inside a 32-bit register, H is 0x80808080 and L is 0x01010101.

SWAR add z = x + y
    z = ((x &~H) + (y &~H)) ^ ((x ^ y) & H)
 
SWAR sub z = x - y
    z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)
 
SWAR average z = (x+y)/2 based on x + y = (x^y) + 2*(x&y)
    z = (x & y) + (((x ^ y) & ~L) >> 1)

External Links

What links here?

Page	Date Edited
More Links
0x88	Nov 28, 2016
10x12 Board	Feb 19, 2018
6502	Dec 25, 2017
6800	Jun 23, 2017
8080	Sep 3, 2017
8086	Sep 18, 2014
8x8 Board	Aug 29, 2017
AltiVec	Jun 7, 2016
Array	Dec 1, 2016
Attack and Defend Maps	Nov 5, 2016
AVX-512	Aug 8, 2017
Backtracking	Dec 16, 2017
Big-endian	Jan 25, 2015
Bit	Oct 29, 2012
Bitboard Serialization	Dec 24, 2014
Byte	Apr 5, 2013
CDC 6600	Oct 8, 2014
Crafty	Jan 28, 2018
CXG Sensor Computachess	Jun 23, 2017
Data	Nov 26, 2017
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Distance	Sep 25, 2015
Double Word	Jan 25, 2015
Edwards' Tablebases	Sep 26, 2016
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Encoding Moves	Mar 27, 2016
Endgame Tablebases	Mar 6, 2018
Endianness	Jan 25, 2015
Eric van Riet Paap	Feb 14, 2017
Fairchild F8	Jul 31, 2015
First Rank Attacks	Aug 28, 2010
Floyd	Sep 11, 2016
Gambiet	Jan 8, 2016
General Setwise Operations	Feb 25, 2018
Graphics Programming	Dec 22, 2017
Hyperbola Quintessence	Mar 25, 2017
i860	Aug 21, 2015
IBM 360	Jan 2, 2016
KIM-1	Oct 9, 2014
Kindergarten Bitboards	Aug 1, 2017
Kurt	Apr 20, 2014
Little-endian	Jan 25, 2015
Magic Bitboards	Apr 13, 2018
Manhattan-Distance	May 19, 2014
Mini Chess	Jun 7, 2013
MMX	Jun 5, 2016
Murka	Nov 11, 2016
Nibble	Jan 25, 2015
Nova	Jan 20, 2016
Novag Micro Chess	Jan 16, 2013
Othello	Jan 4, 2018
Pascal	Nov 28, 2016
Paul Wiereyn	Jun 4, 2015
Pawns and Files (Bitboards)	Jan 16, 2013
Piece-Lists	Feb 13, 2017
Pieces	Feb 19, 2018
Population Count	Sep 3, 2017
Quad Word	Jan 25, 2015
Queue	Apr 4, 2017

Up one Level

Double Word

GerdIsenberg — Sun, 25 Jan 2015 22:17:54 GMT

Home * Programming * Data * Double Word

According to Intel's definition of a x86 16-bit Word, a Double Word refers a 32-bit entity, while IBM 360 and successors with 32-bit words have double words with 64-bit.

Integer and long

Even in x86-64, double words are still considered as default word size. x86 and and x86-64 C-Compiler use double words as signed and unsigned integers, Java integers as well. Microsoft 64 bit compiler long is a 32-bit Double word as well, while with 64-bit GCC uses 64-bit Quad Words as longs.

typedef unsigned int DWORD;

Ranges

type	language	min	max
unsigned int	C, C++	0	4,294,967,295
hexadecimal		0x00000000	0xFFFFFFFF
int	C, C++, Java	-2,147,483,648	2,147,483,647
hexadecimal		0x80000000	0x7FFFFFFF

Alignment

Double Words stored in memory should be stored at byte addresses divisible by four. Otherwise at runtime it will cause a miss-alignment exception on some processors, or a huge penalty on others.

Endianness

Main article: Endianness.

Litte-endian layout

The little-endian memory layout, as typical for Intel x86 cpus.
For instance the double word integer 16909060 or 0x01020304:

Address	Byte	Significance
0x0000	0x04	LS Byte
0x0001	0x03
0x0002	0x02
0x0003	0x01	MS Byte

Big-endian layout

The big-endian memory layout, as typical for Motorola cpus.
For instance the double word integer 16909060 or 0x01020304:

Address	Byte	Significance
0x0000	0x01	MS Byte
0x0001	0x02
0x0002	0x03
0x0003	0x04	LS Byte

External Links

What links here?

Page	Date Edited
AltiVec	Jun 7, 2016
Amundsen	Sep 3, 2013
Avoiding Branches	Dec 16, 2016
AVX-512	Aug 8, 2017
AVX2	Aug 8, 2017
Big-endian	Jan 25, 2015
Bit	Oct 29, 2012
Bitboard Serialization	Dec 24, 2014
Byte	Apr 5, 2013
Data	Nov 26, 2017
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Double Word	Jan 25, 2015
Encoding Moves	Mar 27, 2016
Float	Nov 11, 2016
General Setwise Operations	Feb 25, 2018
Little-endian	Jan 25, 2015
MMX	Jun 5, 2016
Murka	Nov 11, 2016
NoraGrace	Nov 23, 2014
Piece-Sets	Jun 9, 2017
Prophet	Sep 30, 2017
Quad Word	Jan 25, 2015
SIMD and SWAR Techniques	Jun 27, 2017
Spector	Nov 11, 2016
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSSE3	Aug 8, 2017
Transposition Table	Apr 19, 2018
Tucano	Dec 16, 2017
Word	Jan 25, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

General Setwise Operations

GerdIsenberg — Sun, 25 Feb 2018 19:37:00 GMT

Home * Board Representation * Bitboards * General Setwise Operations

		General Setwise Operations, binary and unary operations, essential in testing and manipulating bitboards within a chess program. Relational operators on bitboards test for equality, bitwise boolean operators perform the intrinsic setwise operations ^[1] ^[2], such as intersection, union and complement. Shifting bitboards simulates piece movement, while finally arithmetical operations are used in bit-twiddling applications and to calculate various hash-indicies. Operators are denoted with focus on the C, C++, Java and Pascal programming languages, as well as the mnemonics of x86 or x86-64 Assembly language instructions including bit-manipulation (BMI1, BMI2, TBM) and SIMD expansions (MMX, SSE2, AVX, AVX2, AVX-512, XOP), Mathematical symbols, some Venn diagrams ^[3], Truth tables, and bitboard diagrams where appropriate.
Wassily Kandinsky, Yellow Circle ^[4]

Relational

Relational operators on bitboards are the test for equality whether they are the same or not. Greater or less in the arithmetical sense is usually not relevant with bitboards ^[5] - instead we often compare bit for bit of two bitboards by certain bitwise boolean operations to retrieve bitwise greater, less or equal results.

Equality

In C, C++ or Java "==" is used, to test for equality, "!=" for not equal. Pascal uses "=", "<>" and has ":=" to distinguish relational equal operators from assignment.

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

x86-mnemonics
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.

cmp  rax, rbx ; rax == rbx
je   equal    ; (jz) conditional jump if equal (jne, jnz for not equal)

Empty and Universe

Two important sets are:

The empty set is represented by all bits zero.
The universal set contains all elements by setting all bits to binary one.

The numerical values and setwise representations of those sets:

empty set E       = 0
 set-wise         = {}
 
universal set U   = 2^64 - 1
 signed decimal   = -1
 hexadecimal      = 0xffffffffffffffff
 unsigned decimal = 18,446,744,073,709,551,615
 set-wise         = {a1, b1, c1, d1, ....., e8, f8, g8, h8}

as Venn diagram

or bitboard diagrams

      Empty               Universe
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1
 . . . . . . . .      1 1 1 1 1 1 1 1

Programmers often wonder to use -1 in C, C++ as unsigned constant. See The Two's Complement - alternately one may use ~0 to define the universal set. Since in C or 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 C64 Macro is recommended:

const U64 universe = 0xffffffffffffffffULL;

To test whether a set is empty or not, one may compare with zero or use the logical not operator '!' in C, C++ or Java:

if (a == 0) -> empty set
if (!a)     -> empty set
if (a != 0) -> set is not empty
if (a)      -> set is not empty

To test for the universal set is less likely:

if (a == universe) -> universal set
if (a + 1 == 0)    -> universal set

Bitwise Boolean

Boolean algebra is an algebraic structure ^[6] ^[7] that captures essential properties of both set operations and logical operations. The properties of associativity, commutativity, and absorption, which define an ordered lattice, in conjunction with distributive and complement laws define the Algebra of sets is in fact a Boolean algebra.

Specifically, Boolean algebra deals with the set operations of intersection, union and complement, their equivalents of conjunction, disjunction and negation and their bitwise boolean operations of AND, OR and NOT to implement combinatorial logic in software. Bitwise boolean operations on 64-bit words are in fact 64 parallel operations on each bit performing one setwise operation without any "side-effects". Square mapping don't cares as long all sets use the same.

Intersection

In set theory intersection is denoted as:

$A\cap B$

In boolean algebra conjunction is denoted as:

$a\wedge b$

Bitboard intersection or conjunction is performed by bitwise and (binary operator & in C, C++ or Java, and the keyword "AND" in Pascal).

intersection = a & b

Truth Table
Truth table of and for one bit, for a '1' result both inputs need to be '1':

a	b	a and b
0	0	0
0	1	0
1	0	0
1	1	1

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

x86-mnemonics
x86 has general purpose instruction as well as SIMD-instructions for bitwise and:

and   rax,  rbx        ; rax &= rbx
test  rax,  rbx        ; to determine whether the intersection is empty
pand  mm0,  mm1        ; MMX   mm0 &= mm1
pand  xmm0, xmm1       ; SSE2 xmm0 &= xmm1
vpand xmm0, xmm1, xmm2 ; AVX  xmm0 = xmm1 & xmm2
vpand ymm0, ymm1, ymm2 ; AVX2 ymm0 = ymm1 & ymm2

SSE2-intrinsic _mm_and_si128.
AVX2-intrinsic _mm256_and_si256
AVX-512 has VPTERNLOG

Idempotent
Conjunction is idempotent.

a & a == a

Commutative
Conjunction is commutative

a & b == b & a

Associative
Conjunction is associative.

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

Subset
The intersection of two sets is subset of both.

Assume we have a attack set of a queen, and like to know whether the queen attacks opponent pieces it may capture, we need to 'and' the queen-attacks with the set of opponent pieces.

queen attacks    &  opponent pieces  =  attacked pieces
. . . . . . . .     1 . . 1 1 . . 1     . . . . . . . .
. . . 1 . . 1 .     1 . 1 1 1 1 1 .     . . . 1 . . 1 .
. 1 . 1 . 1 . .     . 1 . . . . . 1     . 1 . . . . . .
. . 1 1 1 . . .     . . . . . . . .     . . . . . . . .
1 1 1 * 1 1 1 .  &  . . . * . . 1 .  =  . . . * . . 1 .
. . 1 1 1 . . .     . . . . . . . .     . . . . . . . .
. . . 1 . 1 . .     . . . . . . . .     . . . . . . . .
. . . 1 . . . .     . . . . . . . .     . . . . . . . .

To prove whether set 'a' is subset of another set 'b', we compare whether the intersection equals the subset:

bool isASubsetOfB(U64 a, U64 b) {return (a & b) == a;}

Disjoint Sets
To test whether two sets are 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:

if ( (a & b) == 0 ) -> a and b are disjoint sets

In chess the bitboards of white and black pieces are obviously always disjoint, same for sets of different piece-types, such as knights or pawns. Of course this is because one square is occupied by one piece only.

Union

In set theory union is denoted as:

$A\cup B$

In boolean algebra disjunction is denoted as:

$a\vee b$

The union or disjunction of two bitboards is applied by bitwise or (binary operator | in C, C++ or Java, or the keyword "OR" in Pascal). The union is superset of the intersection, while the intersection is subset of the union.

union = a | b

Truth Table
Truth table of or for one bit, one set input bits is sufficient to set the output:

a	b	a or b
0	0	0
0	1	1
1	0	1
1	1	1

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-mnemonics
x86 has general purpose instruction as well as SIMD-instructions for bitwise or:

or   rax,  rbx        ;       rax |= rbx
por  mm0,  mm1        ; MMX   mm0 |= mm1
por  xmm0, xmm1       ; SSE2 xmm0 |= xmm1
vpor xmm0, xmm1, xmm2 ; AVX  xmm0  = xmm1 | xmm2
vpor ymm0, ymm1, ymm2 ; AVX2 ymm0  = ymm1 | ymm2

SSE2-intrinsic _mm_or_si128.
AVX2-intrinsic _mm256_or_si256
AVX-512 has VPTERNLOG

Idempotent
Disjunction is idempotent.

a | a == a

Commutative
Disjunction is commutative

a | b == b | a

Associative
Disjunction is associative.

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

Distributive
Disjunction is distributive over conjunction and vice versa:

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

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

white pieces     |  black pieces     =  occupied squares
. . . . . . . .     1 . 1 1 1 1 1 1     1 . 1 1 1 1 1 1
. . . . . . . .     1 1 1 1 . 1 1 1     1 1 1 1 . 1 1 1
. . . . . . . .     . . 1 . . . . .     . . 1 . . . . .
. . . . . . . .     . . . . 1 . . .     . . . . 1 . . .
. . . . 1 . . .  |  . . . . . . . .  =  . . . . 1 . . .
. . . . . 1 . .     . . . . . . . .     . . . . . 1 . .
1 1 1 1 . 1 1 1     . . . . . . . .     1 1 1 1 . 1 1 1
1 1 1 1 1 1 . 1     . . . . . . . .     1 1 1 1 1 1 . 1

Since white and black pieces are always disjoint, one may use addition here as well. That fails for union of attack sets, since squares may be attacked or defended by multiple pieces of course.

Complement Set

In set theory complement set is denoted as:

$A^c$

In boolean algebra negation is denoted as:

$\neg a$

The complement set (absolute complement set), negation or ones' complement has it's equivalent in bitwise not (unary operator '~' in C, C++ or Java, or the keyword "NOT" in Pascal).

Truth Table
Truth table of not for one bit:

a		not a
0		1
1		0

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

x86-mnemonics
Available as general purpose instruction.

not  rax ; rax = ~rax

AVX-512 has VPTERNLOG

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

~occupied squares  =   empty squares
  1 . 1 1 1 1 1 1      . 1 . . . . . .
  1 1 1 1 . 1 1 1      . . . . 1 . . .
  . . 1 . . . . .      1 1 . 1 1 1 1 1
  . . . . 1 . . .      1 1 1 1 . 1 1 1
~ . . . . 1 . . .  =   1 1 1 1 . 1 1 1
  . . . . . 1 . .      1 1 1 1 1 . 1 1
  1 1 1 1 . 1 1 1      . . . . 1 . . .
  1 1 1 1 1 1 . 1      . . . . . . 1 .

Don't confuse bitwise not with logical not-operator '!' in C:

!0 == 1
!(anything != 0) == 0
!1  == 0
!-1 == 0

Complement laws

The union of a set with it's complement is the universal set -1.
The intersection of a set with it's complement is the empty set 0 - both are disjoint.
Empty set and universal set are complement sets.

a  | ~a == -1
a  & ~a ==  0
~0      == -1
~(-1)   ==  0

De Morgan's laws

Complement of union (NOR ) is the intersection of the complements ^[8].
Complement of intersection (NAND or Sheffer stroke ) is the union of the complements.

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

For instance to get the set of empty squares, we can complement the union of white and black pieces. Or we can intersect the complements of white and black pieces.

Relative Complement

In set theory relative complement is denoted as:

$A^c \cap B~=~B \setminus A$

The relative complement is the 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 intersection of 'b' with the absolute complement of 'a'.

not_a_in_b  = ~a &  b
b_without_a =  b & ~a

Truth Table
Truth table of relative complement for one bit:

a	b	b andnot a
0	0	0
0	1	1
1	0	0
1	1	0

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

x86-mnemonics
x86 don't has an own general purpose instruction for relative complement, but x86-64 expansion BMI1, and SIMD-instructions:

andn   rax,  rbx,  rcx  ; BMI1  rax = ~rbx & rcx
pandn  mm0,  mm1        ; MMX   mm0 = ~mm0 & mm1
pandn  xmm0, xmm1       ; SSE2 xmm0 = ~xmm0 & xmm1
vpandn xmm0, xmm1, xmm2 ; AVX  xmm0 = ~xmm1 & xmm2
vpandn ymm0, ymm1, ymm2 ; AVX  xmm0 = ~xmm1 & xmm2

SSE2-intrinsic _mm_andnot_si128.
AVX2-intrinsic _mm256_andnot_si256
AVX-512 has VPTERNLOG

Super minus Sub
In presumption of 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
~a & b == b - ( a & b )

Implication

Logical Implication or Entailment is denoted as:

$A~\Rightarrow~B$

The boolean Material conditional is denoted as:

$~a \rightarrow b$

Logical Implication or the boolean Material conditional 'a' implies 'b' (if 'a' then 'b') is an derived boolean operation, implemented as union of the absolute complement of 'a' with 'b':

a_implies_b ==  ~a | b

Truth Table
Truth table of logical implication for one bit:

a	b	a implies b
0	0	1
0	1	1
1	0	0
1	1	1

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

x86-mnemonics
AVX-512 has VPTERNLOG

Exclusive Or

In set theory symmetric difference is denoted as:

$A~\Delta~B$

In boolean algebra Exclusive or is denoted as:

$~a \oplus b$

Exclusive or, also exclusive disjunction (xor, binary operator '^' in C, C++ or Java, or the keyword "XOR" in Pascal), also called symmetric difference, leaves all elements which are exclusively set in one of the two sets. Xor is really a multi purpose operation with a lot of applications not only bitboards of course.

1 . . . . . . 1     . . . . . . . .     1 . . . . . . 1
. 1 . . . . 1 .     . . . . . . . .     . 1 . . . . 1 .
. . 1 . . 1 . .     . . 1 1 1 1 . .     . . . 1 1 . . .
. . . 1 1 . . .     . . 1 1 1 1 . .     . . 1 . . 1 . .
. . . 1 1 . . .  ^  . . 1 1 1 1 . .  =  . . 1 . . 1 . .
. . 1 . . 1 . .     . . 1 1 1 1 . .     . . . 1 1 . . .
. 1 . . . . 1 .     . . . . . . . .     . 1 . . . . 1 .
1 . . . . . . 1     . . . . . . . .     1 . . . . . . 1

Truth Table
Truth table of exclusive or for one bit:

a	b	a xor b
0	0	0
0	1	1
1	0	1
1	1	0

Xor implements a bitwise (a != b) relation.
It acts like a bitwise addition (modulo 2), since (1 + 1) mod 2 = 0.
It also acts like a bitwise subtraction (modulo 2).

x86-mnemonics
x86 has general purpose instruction as well as SIMD-instructions for bitwise exclusive or:

xor   rax,  rbx        ;       rax ^= rbx
pxor  mm0,  mm1        ; MMX   mm0 ^= mm1
pxor  xmm0, xmm1       ; SSE2 xmm0 ^= xmm1
vpxor xmm0, xmm1, xmm2 ; AVX  xmm0  = xmm1 ^ xmm2
vpxor ymm0, ymm1, ymm2 ; AVX2 ymm0  = ymm1 ^ ymm2

SSE2-intrinsic _mm_xor_si128.
AVX2-intrinsic _mm256_xor_si256
AVX-512 has VPTERNLOG

Commutative
Exclusive disjunction is commutative

a ^ b == b ^ a

Associative
Xor is associative as well.

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

Distributive
Conjunction is distributive over exclusive disjunction - but not vice versa, since conjunction acts like multiplication, while xor acts as addition in the Galois field GF(2) :

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

Own Inverse
If applied two (even) times with the same operand, xor restores the original result. It is own inverse or an involution .

Subset
If one operand is subset of the other, xor (or subtraction) implements the relative complement.

super               sub                 super &~ sub
. . . . . . . .     . . . . . . . .     . . . . . . . .
. 1 1 1 1 1 1 .     . . . . . . . .     . 1 1 1 1 1 1 .
. 1 1 1 1 1 1 .     . . 1 1 1 1 . .     . 1 . . . . 1 .
. 1 1 1 1 1 1 .  ^  . . 1 1 1 1 . .     . 1 . . . . 1 .
. 1 1 1 1 1 1 .     . . 1 1 1 1 . .  =  . 1 . . . . 1 .
. 1 1 1 1 1 1 .  -  . . 1 1 1 1 . .     . 1 . . . . 1 .
. 1 1 1 1 1 1 .     . . . . . . . .     . 1 1 1 1 1 1 .
. . . . . . . .     . . . . . . . .     . . . . . . . .

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

(2**n - 1) - a == a ^ (2**n - 1) with a subset of 2**n - 1

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

 1 - a == a ^  1
 3 - a == a ^  3
 7 - a == a ^  7
15 - a == a ^ 15
31 - a == a ^ 31
63 - a == a ^ 63
...
-1 - a == a ^ -1

Or without And
Xor is the same as a union without the intersection - all the bits different, 0,1 or 1,0. Since the intersection is subset of the 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)

Disjoint Sets
The symmetric difference of disjoint sets is equal to the union or arithmetical addition. Since intersection and symmetric difference are disjoint, the union might defined that way:

a | b = ( a & b ) ^ ( a ^ b )
a | b = ( a & b ) ^   a ^ b
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. 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.

Union of Complements
The symmetric difference is equivalent to the union of both relative complements. Since both relative complements are 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)

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

x ^= mask;

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

a ^ -1 == ~a

Without
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 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 & ~b == a ^ ( a & b ) == a - ( a & b )
a & ~b == b ^ ( a | b ) == ( a | b ) - b

Also note that

a & a == a & -1

Clear
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.

xor  rax, rax   ; same as mov rax, 0
pxor mm0, mm0   ; MMX 64-bit register
pxor xmm0, xmm0 ; SSE2 - 128-bit xmm-register

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

a ^= b
b ^= a
a ^= b

If we provide an intersection by a mask, ...

a = (a ^ b) & mask
b ^= a
a ^= b

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

Bits from two Sources
Getting arbitrary, disjoint bits from two sources by a mask:

// if mask-bit is zero, bit from a, otherwise from b - since a^(a^b) == b
U64 mask = C64(0xFFFF0000FFFF0000);
U64 result = a ^ ((a ^ b) & mask);

This takes one instruction less, than the union of relative complement of the mask in 'a' with intersection of mask with 'b'.

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

XOR-applications and affairs

Calculation of hash-keys based on Zobrist-keys.
Cyclic redundancy check, Parity words or Gray Code
Fredkin gate by Edward Fredkin
Hyperbola Quintessence.
o^(o-2r).
Robert Hyatt's approach of a lockless transposition table
Swapping Bits.
The XOR affair from Perceptrons by Marvin Minsky and Seymour Papert ^[9]

Equivalence

If and only if is denoted as:

$A~\Leftrightarrow~B$

Logical equivalence is denoted as:

$a \leftrightarrow b$

Logical equality, logical equivalence or biconditional (if and only if, XNOR ) is the complement of xor.

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

Truth Table
Truth table of equivalence or for one bit:

a	b	a <=> b
0	0	1
0	1	0
1	0	0
1	1	1

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

x86-mnemonics
AVX-512 has VPTERNLOG

Majority

The 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 intersection. Three inputs require some more computation:

Truth Table
Truth table of majority for three inputs:

a	b	c	maj(a,b,c)
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

major = (a & b) |  (a & c) | (b & c);
major = (a & b) | ((a ^ b ) & c);

See the application of cardinality of multiple sets for more than three inputs.

x86-mnemonics
AVX-512 VPTERNLOG imm8 = 0xe8 implements the majority function.

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 intersection, for three inputs it is the majority function. For more inputs it is the union of all distinct pairwise intersections, which can be expressed with setwise operators that way:

$\bigcup_{\stackrel{i,j\in I}{i > j}}(A_i\cap A_j)$

With four bitboards this is equivalent to:

  (a1 & a0)
 
| (a2 & a1)
| (a2 & a0)
 
| (a3 & a2)
| (a3 & a1)
| (a3 & a0)

with

$n * (n - 1) - 1$

operations - that is 11 for n == 4.

O(n^2) to O(n)
Due to distibutive law one can factor out common sets ...

  (a1 & (      a0))
| (a2 & (   a1|a0))
| (a3 & (a2|a1|a0))

... 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.

In general, as mentioned,

$\bigcup_{\stackrel{i,j\in I}{i > j}}(A_i\cap A_j)$

requires

$n * (n - 1) - 1$

operations, which can be reduced to

$3 * (n - 1) - 2$

operations.

This O(n^2) to O(n) simplification is helpful to determine for instance knight fork target squares from eight distinct knight-wise direction attack sets of potential targets, like king, queen, rooks and hanging bishops or even pawns - or any other form of at least double attacks from n attack bitboards:

U64 attack[n]; // 0..n-1
U64 atLeastDouble = 0;
U64 atLeastSingle = a[0];
for (i=1; i < n; i++) {
  atLeastDouble |= attack[i] & atLeastSingle;
  atLeastSingle |= attack[i];
}

Well, if you need additionally at least triple attacks, you'll get the idea how this would work as well, see also Odd and Major Digit Counts from the Population Count page.

Shifting Bitboards

In the 8*8 board centric world with one scalar square-coordinate 0..63, each of the max eight neighboring squares can be determined by adding an offset for each direction. For border squares one has to care about overflows and wraps from a-file to h-file or vice versa. Some conditional code is needed to avoid that. Such code is usually part of move generation for particular pieces.

  northwest    north   northeast
  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa
  southwest    south   southeast

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

In the setwise world of bitboards, where a square as member of a set is determined by an appropriate one-bit 2^square, the operation to apply such movements is shifting . Unfortunately most architectures don't support a "generalized" shift by signed values but only shift left or shift right. That makes bitboard code less general as one has usually separate code for each direction or at least for the positive and negative directions.

Shift left (<<) is arithmetically a multiplication by power of two.
Shift right (>> or >>> in Java ^[10]) is arithmetically a division by power of two.

Since the square-index is encoded as power of two exponent inside a bitboard, the power of two multiplication or division is adding or subtracting the square-index.

The reason the bitboard type-definintion is unsigned in C, C++ is to avoid so called arithmetical shift right in opposition to 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-mnemonics
x86 has general purpose instruction as well as SIMD-instructions for various shifts:

shr      rax,  cl         ;       rax >>= cl
shl      rax,  cl         ;       rax <<= cl
psrlq    mm0,  mm1        ; MMX   mm0 >>= mm1
psllq    mm0,  mm1        ; MMX   mm0 <<= mm1
psrlq    xmm0, xmm1       ; SSE2 xmm0 >>= xmm1
psllq    xmm0, xmm1       ; SSE2 xmm0 <<= xmm1
vpshlq   xmm0, xmm1, xmm2 ; XOP  xmm0   = xmm1 >>/<< xmm2 ; Individual, generalized shifts
vpshlb   xmm0, xmm1, xmm2 ; XOP  xmm0   = xmm1 >>/<< xmm2 ; Individual, generalized shifts of 16 bytes
vpsrlvq  ymm0, ymm1, ymm2 ; AVX2 ymm0   = ymm1 >> ymm2 ; Individual shifts
vpsllvq  ymm0, ymm1, ymm2 ; AVX2 ymm0   = ymm1 << ymm2 ; Individual shifts

SSE2-intrinsics with variable register or constant immediate shift amounts, working on vectors of two bitboards:

XOP has individual, generalized shifts for each of two bitboards and also has byte-wise shifts

AVX2 has individual shifts for each of four bitboards:

One Step Only

The advantage with bitboards is, that the shift applies to all set bits in parallel, e.g. with all pawns. Vertical shifts by +-8 don't need any under- or overflow conditions since bits simply fall out and disappear.

U64 soutOne (U64 b) {return  b >> 8;}
U64 nortOne (U64 b) {return  b << 8;}

Wraps from a-file to h-file or vice versa may be considered by only shifting subsets which may not wrap.
Thus we can mask off the a- or h-file before or after a +-1,7,9 shift:

const U64 notAFile = 0xfefefefefefefefe; // ~0x0101010101010101
const U64 notHFile = 0x7f7f7f7f7f7f7f7f; // ~0x8080808080808080

Post-shift masks, ...

U64 eastOne (U64 b) {return (b << 1) & notAFile;}
U64 noEaOne (U64 b) {return (b << 9) & notAFile;}
U64 soEaOne (U64 b) {return (b >> 7) & notAFile;}
U64 westOne (U64 b) {return (b >> 1) & notHFile;}
U64 soWeOne (U64 b) {return (b >> 9) & notHFile;}
U64 noWeOne (U64 b) {return (b << 7) & notHFile;}

... and pre-shift, with the mirrored file masks.

U64 eastOne (U64 b) {return (b & notHFile) << 1;}
U64 noEaOne (U64 b) {return (b & notHFile) << 9;}
U64 soEaOne (U64 b) {return (b & notHFile) >> 7;}
U64 westOne (U64 b) {return (b & notAFile) >> 1;}
U64 soWeOne (U64 b) {return (b & notAFile) >> 9;}
U64 noWeOne (U64 b) {return (b & notAFile) << 7;}

SSE2 one step only provides some optimizations according to the wraps on vectors of two bitboards.

Main application of shifts is to get attack sets or move-target sets of appropriate pieces, eg. one step for pawns and king. Applying one step multiple times may used to generate attack sets and moves of pieces like knights and sliding pieces.

For instance all push-targets of white pawns can be determined with one shift left plus intersection with empty squares.

whiteSinglePawnPushTargets = nortOne(whitePawns) & emptySquares;

Square-Mapping is crucial while shifting bitboards. Shifting left inside a computer word may mean shifting right on the board with little-endian file-mapping as used in most sample code here.

Rotate

For the sake of completeness - Rotate is similar to shift but wraps bits around. Rotate does not alter the number of set bits. With x86-64 like shift operand s modulo 64, each bit index i, in the 0 to 63 range, is transposed by

rotateLeft ::=  i := (i + s) mod 64
rotateRight::=  i := (i - s) mod 64

Additionally, following relations hold:

rotateLeft (s) == rotateRight(64-s)
rotateRight(s) == rotateLeft (64-s)

Most processors have rotate instructions, but are not supported by standard programming languages like C or Java. Some compilers provide intrinsic, processor specific functions.

U64 rotateLeft (U64 x, int s) {return _rotl64(x, s);}
U64 rotateRight(U64 x, int s) {return _rotr64(x, s);}

x86-mnemonics

rol  rax, cl
ror  rax, cl

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

U64 rotateLeft (U64 x, int s) {return (x << s) | (x >> (64-s));}
U64 rotateRight(U64 x, int s) {return (x >> s) | (x << (64-s));}

Since x86-64 64-bit shifts are implicitly modulo 64 (and 63), one may replace (64-s) by -s.

Generalized Shift

shifts left for positive amounts, but right for negative amounts.

U64 genShift(U64 x, int s) {
   return (s > 0) ? (x << s) : (x >> -s);
}

If compiler are not able to produce speculative execution of both shifts with a conditional move instruction, one may try an explicit branch-less solution:

/**
 * generalized shift
 * @author Gerd Isenberg
 * @param x any bitboard
 * @param s shift amount -64 < s < +64
 *          left if positive
 *          right if negative
 * @return shifted bitboard
 */
U64 genShift(U64 x, int s) {
   char left  =   (char) s;
   char right = -((char)(s >> 8) & left);
   return (x >> right) << (right + left);
}

Due to the value range of the shift, one may save the arithmetical shift right in assembly:

 ; input
 ;     ecx - shift amount,
 ;           left if positive
 ;           right if negative
 ;     rax - bitboard to shift
 mov   dl,  cl
 and   cl,  ch
 neg   cl
 shr   rax, cl
 add   cl,  dl
 shl   rax, cl

One Step
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 one step. It might be applied to get attacks for both sides with a 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.

// positve left, negative right shifts
int shift[8] = {9, 1,-7,-8,-9,-1, 7, 8};
 
U64 avoidWrap[8] =
{
   0xfefefefefefefe00,
   0xfefefefefefefefe,
   0x00fefefefefefefe,
   0x00ffffffffffffff,
   0x007f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f7f,
   0x7f7f7f7f7f7f7f00,
   0xffffffffffffff00,
};
 
U64 shiftOne (U64 b, int dir8) {
   return _rotl64(b, shift[dir8]) & avoidWrap[dir8];
}

The avoidWrap masks by some arbitrary dir8 enumeration and shift amount:

6 == noWe -> +7     7 == nort -> +8     0 == noEa -> +9
0x7F7F7F7F7F7F7F00  0xFFFFFFFFFFFFFF00  0xFEFEFEFEFEFEFE00
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
5 == west -> -1                         1 == east -> +1
0x7F7F7F7F7F7F7F7F                      0xFEFEFEFEFEFEFEFE
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .                         . 1 1 1 1 1 1 1
 
4 == soWe -> -9     3 == sout -> -8     2 == soEa -> -7
0x007F7F7F7F7F7F7F  0x00FFFFFFFFFFFFFF  0x00FEFEFEFEFEFEFE
. . . . . . . .     . . . . . . . .     . . . . . . . .
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1
1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1

Bit by Square

Since single populated bitboards are always power of two values, shifting 2^0 left implements pow2(square) to convert square-indices to a member of a bitboard.

U64 singleBitset = C64(1) << square; // or lookup[square]

The inverse function square = log2(x), is topic of bitscan and bitboard serialization.

Shift versus Lookup
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 ^[11].

Test
Test a bit of a square-index by intersection-operator 'and'.

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

Set
Set a bit of a square-index by union-operator 'or'.

x |=  singleBitset; // set bit

Toggle
Toggle a bit of square-index by xor.

x ^=  singleBitset; // toggle bit

Reset
Reset a bit of square-index by relative complement of the single bit.

x &= ~singleBitset; // reset bit

Set and toggle (or, xor) might the faster way to reset a bit inside a register (not, and).

x |=  singleBitset; // set bit
x ^=  singleBitset; // resets set bit

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

x86-Instructions
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:

Update by Move

This technique to toggle bits by square is likely used to initialize or update the bitboard board-definition. While making or unmaking moves, the single bit either correspondents with the from- or to-square of the move. Which particular bitboard has to be updated depends on the moving piece or captured piece.

For simplicity we assume piece plus color and captured piece are member or method of a move-structure/class.

Quiet moves toggle both from- and to-squares of the piece-bitboard, as well for the redundant union-sets:

U64 fromBB   = C64(1) << move->from;
U64 toBB     = C64(1) << move->to;
U64 fromToBB = fromBB ^ toBB; // |+
pieceBB[move->piece]  ^=  fromToBB;   // update piece bitboard
pieceBB[move->color]  ^=  fromToBB;   // update white or black color bitboard
occupiedBB            ^=  fromToBB;   // update occupied ...
emptyBB               ^=  fromToBB;   // ... and empty bitboard

Captures need to consider the captured piece of course:

U64 fromBB   = C64(1) << move->from;
U64 toBB     = C64(1) << move->to;
U64 fromToBB = fromBB ^ toBB; // |+
pieceBB[move->piece]  ^=  fromToBB;   // update piece bitboard
pieceBB[move->color]  ^=  fromToBB;   // update white or black color bitboard
pieceBB[move->cPiece] ^=  toBB;       // reset the captured piece
pieceBB[move->cColor] ^=  toBB;       // update color bitboard by captured piece
occupiedBB            ^=  fromBB;     // update occupied, only from becomes empty
emptyBB               ^=  fromBB;     // update empty bitboard

Similar for special moves like castling, promotions and en passant captures.

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

U64 upperBits =  C64(~1) << sq;

for instance d4 (27)

high = ~1 << d4
 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1
 . . . . 1 1 1 1
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .

Lower Squares
Lower squares are simply Bit by Square minus one.

U64 lowerBits = (C64(1 ) << sq) - 1);

for instance d4 (27)

low = (1<<d4)-1
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 . . . . . . . .
 1 1 1 . . . . .
 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1
 1 1 1 1 1 1 1 1

Swapping Bits

Swapping none overlapping bit-sequences in a bitboard is the base of a lot of permutation tricks.

by Position
Suppose we like to swap n 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 union (xor-union due to disjoint bits) is finally exclusive ored with the original bitboard to swap both sequences.

/**
 * swap n none overlapping bits of bit-index i with j
 * @param b any bitboard
 * @param i,j positions of bit sequences to swap
 * @param n number of consecutive bits to swap
 * @return bitboard b with swapped bit-sequences
 */
U64 swapNBits(U64 b, int i, int j, int n) {
   U64     m = ( 1 << n) - 1;
   U64     x = ((b >> i) ^ (b >> j)) & m;
   return  b ^  (x << i) ^ (x << j);
}

For instance swap 6 bits each, from bit-index 9 (bits named ABCDEF, either 0,1) with bit-index 41 (abcdef):

b                                       m = (1<<6) - 1
. . . . . . . .                         . . . . . . . .
* . . . . . . .                         . . . . . . . .
*|a b c d e f|*                         . . . . . . . .
. . . . . . . .                         . . . . . . . .
. . . . . . . .                         . . . . . . . .
. . . . . . . .                         . . . . . . . .
*|A B C D E F|*                         . . . . . . . .
. . . . . . . .                         1 1 1 1 1 1 . .
 
b >> j           ^  b >> i          =>  x = .xor & m       with
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .    r = a ^ A
. . . . . . . .     a b c d e f * *     . . . . . . . .    s = b ^ B
. . . . . . . .  ^  . . . . . . . * =>  . . . . . . . .    t = c ^ C
. . . . . . . .     . . . . . . . .     . . . . . . . .    u = d ^ D
. . . . . . . .     . . . . . . . .     . . . . . . . .    v = e ^ E
a b c d e f * *     A B C D E F * .     r s t u v w . .    w = f ^ F
 
b               ^  x << i | x << j  => swapNBits(9,41,6)
. . . . . . . .    . . . . . . . .     . . . . . . . .
* . . . . . . .    . . . . . . . .     * . . . . . . .
*|a b c d e f|*    . r s t u v w .     *|A B C D E F|*
. . . . . . . .    . . . . . . . .     . . . . . . . .
. . . . . . . . ^  . . . . . . . .  => . . . . . . . .
. . . . . . . .    . . . . . . . .     . . . . . . . .
*|A B C D E F|*    . r s t u v w .     *|a b c d e f|*
. . . . . . . .    . . . . . . . .     . . . . . . . .

Delta Swap
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.

/**
 * swap any none overlapping pairs of bits
 *   that are delta places apart
 * @param b any bitboard
 * @param mask has a 1 on the least significant position
 *             for each pair supposed to be swapped
 * @param delta of pairwise swapped bits
 * @return bitboard b with bits swapped
 */
U64 deltaSwap(U64 b, U64 mask, int delta) {
   U64 x = (b ^ (b >> delta)) & mask;
   return   x ^ (x << delta)  ^ b;
}

To apply the swapping of the swapNBits sample above, we call deltaSwap with delta of 32 and 0x7E00 as mask. But we may apply any arbitrary and often periodic mask pattern, as long as no overlapping occurs. The intersection of mask with (mask << delta) must therefor be empty. But we can also swap odd or even files of a bitboard by calling deltaSwap with delta of one, and mask of 0x5555555555555555:

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

Applications of delta swaps are flipping, mirroring and rotating. In Knuth's The Art of Computer Programming, Vol 4, page 13, bit permutation in general ^[12], he mentions 2^k delta swaps with k = {0,1,2,3,4,5,4,3,2,1,0} to obtain any arbitrary permutation. Special cases might be cheaper.

Arithmetic Operations

At the first glance, arithmetic operations, that is addition, subtraction, multiplication and division, doesn't make much sense with bitboards. Still, there are some bit-twiddling applications related to least significant one bit (LS1B), to enumerate all subsets of a set or sliding attack generation. Multiplication of certain pattern has some applications as well, most likely to calculate hash-indicies of masked occupancies.

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 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 ALU of the CPU. A so called half-adder to add two bits (A, B), requires an And-Gate for the carry (C) and a Xor-Gate for the sum (S):

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

To get an idea of the "complexity" of a simple addition, and how to implement an carry-lookahead adder in software with bitwise boolean and shift instructions only, and presumption on parallel prefix algorithms, this is how a 64-bit Kogge-Stone adder would look like in C:

U64 koggeStoneAdd(U64 a, U64 b) {
   U64 gen = a&b;  // carries
   U64 pro = a^b;  // sum
   gen |= pro & (gen << 1);
   pro  = pro & (pro << 1);
   gen |= pro & (gen << 2);
   pro  = pro & (pro << 2);
   gen |= pro & (gen << 4);
   pro  = pro & (pro << 4);
   gen |= pro & (gen << 8);
   pro  = pro & (pro << 8);
   gen |= pro & (gen <<16);
   pro  = pro & (pro <<16);
   gen |= pro & (gen <<32);
   return a^b ^ (gen << 1);
}

Addition

Addition might be used instead of bitwise 'xor' or 'or' for a union of disjoint (intersection zero) sets, which may yield to simplification of the surrounding expression or may take advantage of certain address calculation instruction such as x86 load effective address (lea).

The enriched algebra with arithmetical and bitwise-boolean operations becomes aware with following relation - the bitwise overflows are the intersection, otherwise the sum modulo two is the symmetric difference - thus the arithmetical sum is the xor-sum plus the carries shifted left one:

x + y = (x ^ y) + 2*(x & y)
x ^ y =  x + y  - 2*(x & y)

This is particular interesting in SWAR-arithmetic, or if we like to compute the average without possible temporary overflows:

(x + y) / 2 = ((x ^ y)>>1) + (x & y)

x86-mnemonics

add  rax, rbx ; rax += rbx
lea  rax, [rcx + rdx + const ] ; rax = rcx + rdx + const

Subtraction

Subtraction (like xor) might be used to implement the relative complement, of a subset inside it's superset. As mentioned, subtraction may be useful in calculating sliding attacks.

x86-mnemonics

sub  rax, rbx ; rax -= rbx

The Two's Complement

A lot of bit-twiddling tricks on bitboards to traverse or isolate subsets, rely on 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.

x86-mnemonics

neg  rax;  rax = -rax; rax *= -1

2^N is used as power operator in this paragraph not xor !

Increment of Complement
The two's complement is defined as a value, we need to add to the original value to get 2^64 which is an "overflowed" zero - since all 64-bit values are implicitly modulo 2^64. Thus, the two's complement is defined as ones' complement plus one:

-x == ~x + 1

That fulfills the condition that x + (-x) == 2 ^ bitsize (2 ^ 64) which overflows to zero:

x + (-x)     == 0
x +  ~x + 1  == 0
==>   x + ~x == -1 the universal set

Complement of Decrement
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)

Thus, we can reduce subtraction by addition and ones' complement:

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

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

Copy bits from source to destination from right to left
- until the first binary "one" is copied.
Then invert each of the remaining higher bits.

Signed-Unsigned
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.

The signed-unsigned "independence" of the two's complement is the reason that processors don't need different add or sub instructions for signed or unsigned integers. The binary pattern of the result is the same, only the interpretation differs and processors flag different overflow- or underflow conditions simultaneously.

Unsigned 64-bit values as used for bitboards have this value range:

       hexadecimal                      decimal    pow2
0x0000000000000000                            0           0
0x0000000000000001                            1           1
..
0x7fffffffffffffff    9,223,372,036,854,775,807    2^63 - 1
0x8000000000000000    9,223,372,036,854,775,808    2^63
..
0xffffffffffffffff   18,446,744,073,709,551,615    2^64 - 1

With signed interpretation, the positive numbers are subset of the unsigned with MSB clear:

       hexadecimal                      decimal    pow2
0x0000000000000000                            0           0
0x0000000000000001                            1           1
..
0x7fffffffffffffff    9,223,372,036,854,775,807    2^63 - 1

Negative numbers have MSB set to one, thus the sign bit interpretation

       hexadecimal                      decimal    pow2
0x8000000000000000   -9,223,372,036,854,775,808  -(2^63)
0x8000000000000001   -9,223,372,036,854,775,807  -(2^63) +1
..
0xfffffffffffffffe                           -2          -2
0xffffffffffffffff                           -1          -1

There is no "negative" zero. What makes the value range of negative values one greater than the positive numbers - and implies that

 -0x8000000000000000 == 0x8000000000000000

Least Significant One

At some point bitboards require serialization, thus isolation of single populated sub-sets which are power of two values if interpreted as number. Dependent on the bitboard-api those values need a further log2(powOfTwo) to convert them into the square index range from 0 to 63. Bitwise boolean operations (and, xor, or) with two's complement or ones' decrement can compute relatives of a set x in several useful ways.

Isolation

The intersection of a none empty bitboard with it's two's complement isolates the LS1B:

LS1B_of_x = x & -x;

With some arbitrary sample set:

      x          &        -x         =     LS1B_of_x
. . . . . . . .     1 1 1 1 1 1 1 1     . . . . . . . .
. . 1 . 1 . . .     1 1 . 1 . 1 1 1     . . . . . . . .
. 1 . . . 1 . .     1 . 1 1 1 . 1 1     . . . . . . . .
. . . . . . . .     1 1 1 1 1 1 1 1     . . . . . . . .
. 1 . . . 1 . .  &  1 . 1 1 1 . 1 1  =  . . . . . . . .
. . 1 . 1 . . .     . . 1 1 . 1 1 1     . . 1 . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .

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

x86-mnemonics
x86-64 expansion BMI1 has LS1B bit isolation:

blsi  rax, rbx ; BMI1  rax = rbx & -rbx

BMI1-intrinsic _blsi_u32/64.

AMD's x86-64 expansion TBM further has a Isolate Lowest Set Bit and Complement instruction, which applies De Morgan's law to get the complement of the LS1B:

blsic rax, rbx ; TBM:  rax = ~rbx | (rbx - 1);

Reset

The intersection of a none empty bitboard with it's ones' decrement resets the LS1B ^[13]:

x_with_reset_LS1B = x & (x-1);

With some arbitrary sample set:

      x          &      (x-1)        =  x_with_reset_LS1B
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . 1 . 1 . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. 1 . . . 1 . .     . 1 . . . 1 . .     . 1 . . . 1 . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. 1 . . . 1 . .  &  . 1 . . . 1 . .  =  . 1 . . . 1 . .
. . 1 . 1 . . .     1 1 . . 1 . . .     . . . . 1 . . .
. . . . . . . .     1 1 1 1 1 1 1 1     . . . . . . . .
. . . . . . . .     1 1 1 1 1 1 1 1     . . . . . . . .

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

x86-mnemonics
x86-64 expansion BMI1 has LS1B bit reset:

blsr  rax, rbx ; BMI1  rax = rbx & (rbx - 1)

BMI1-intrinsic _blsr_u32/64.

Separation

Masks separated by LS1B by xor with two's complement or ones' decrement. Intersection of one's complement with decrement leaves the below mask excluding LS1B:

above_LS1B_mask           =  x ^  -x;
below_LSB1_mask_including =  x ^ (x-1);
below_LSB1_mask           = ~x & (x-1);

With some arbitrary sample set:

      x          ^        -x         =   above_LS1B_mask
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
. . 1 . 1 . . .     1 1 . 1 . 1 1 1     1 1 1 1 1 1 1 1
. 1 . . . 1 . .     1 . 1 1 1 . 1 1     1 1 1 1 1 1 1 1
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
. 1 . . . 1 . .  ^  1 . 1 1 1 . 1 1  =  1 1 1 1 1 1 1 1
. . 1 . 1 . . .     . . 1 1 . 1 1 1     . . . 1 1 1 1 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
      x          ^      (x-1)        =  below_LSB1_mask_including
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . 1 . 1 . . .     . . 1 . 1 . . .     . . . . . . . .
. 1 . . . 1 . .     . 1 . . . 1 . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. 1 . . . 1 . .  ^  . 1 . . . 1 . .  =  . . . . . . . .
. . 1 . 1 . . .     1 1 . . 1 . . .     1 1 1 . . . . .
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
 
     ~x          &      (x-1)        =  below_LSB1_mask
1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .
1 1 . 1 . 1 1 1     . . 1 . 1 . . .     . . . . . . . .
1 . 1 1 1 . 1 1     . 1 . . . 1 . .     . . . . . . . .
1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .
1 . 1 1 1 . 1 1  &  . 1 . . . 1 . .  =  . . . . . . . .
1 1 . 1 . 1 1 1     1 1 . . 1 . . .     1 1 . . . . . .
1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1

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

blsmsk rax, rbx ; BMI1:  rax =  rbx ^ (rbx - 1)
tzmsk  rax, rbx ; TBM:   rax = ~rbx & (rbx - 1)

BMI1-intrinsic _blsmsk_u32/64.

Smearing

To smear the LS1B up and down, we use the union with two's complement or ones' decrement:

smearsLS1BUp   = x |  -x;
smearsLS1BDown = x | (x-1);

With some arbitrary sample set:

      x          |        -x         =  smearsLS1BUp
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
. . 1 . 1 . . .     1 1 . 1 . 1 1 1     1 1 1 1 1 1 1 1
. 1 . . . 1 . .     1 . 1 1 1 . 1 1     1 1 1 1 1 1 1 1
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
. 1 . . . 1 . .  |  1 . 1 1 1 . 1 1  =  1 1 1 1 1 1 1 1
. . 1 . 1 . . .     . . 1 1 . 1 1 1     . . 1 1 1 1 1 1
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
 
      x          |      (x-1)        =  smearsLS1BDown
. . . . . . . .     . . . . . . . .     . . . . . . . .
. . 1 . 1 . . .     . . 1 . 1 . . .     . . 1 . 1 . . .
. 1 . . . 1 . .     . 1 . . . 1 . .     . 1 . . . 1 . .
. . . . . . . .     . . . . . . . .     . . . . . . . .
. 1 . . . 1 . .  |  . 1 . . . 1 . .  =  . 1 . . . 1 . .
. . 1 . 1 . . .     1 1 . . 1 . . .     1 1 1 . 1 . . .
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1
. . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1

x86-mnemonics
AMD's x86-64 expansion TBM has a Fill From Lowest Set Bit instruction:

blsfill  rax, rbx ; TBM:  rax = rbx | (rbx - 1)

Least Significant Zero

Dealing with the least significant zero bit (LS0B) or clear bit can be derived from the complement of the LS1B. AMD's x86-64 expansion TBM has six instructions based on boolean operations with the one's increment:

Isolate Lowest Clear Bit, union with the complement of the increment
Isolate Lowest Clear Bit and Complement, intersection of the complement with the increment
Fill From Lowest Clear Bit, intersection with the increment
Mask From Lowest Clear Bit, exclusive or with the increment
Set Lowest Clear Bit, union with the increment
Inverse Mask From Trailing Ones, union of complement and increment

Most Significant One

The MS1B is not that simple to isolate as long we have no reverse arithmetic with carries propagating from left to right. To isolate MS1B, one needs to set all lower bits below MS1B, shift the resulting mask right by one and finally add one.

Setting all lower bits in the general case requires 63 times x |= x >> 1 which might be done in parallel prefix manner in log2(64) = 6 steps:

x |= x >> 32;
x |= x >> 16;
x |= x >>  8;
x |= x >>  4;
x |= x >>  2;
x |= x >>  1;
MS1B = (x >> 1) + 1;

Still quite expensive - better to traverse sets the other way around or rely on intrinsic functions to use special processor instructions like BitScanReverse or LeadingZeroCount, which implicitly performs not only the isolation but also the log2.

Common MS1B
Two sets have a common MS1B, if the intersection is greater than the xor sum:

if ((a & b) > (a ^ b)) -> a and b have common MS1B

This is because a common MS1B is set in the intersection but cleared in the xor sum. Otherwise, with no common MS1B, the xor-sum is greater except equal for two zero operands.

Multiplication

64-bit Multiplication has become awfully fast on recent processors. Shift left is of course still faster than multiplication by power of two, but if we have more than one bit set in a factor, it already makes sense to replace for instance

y  = (x << 8) + (x << 16);

y  = x * 0x00010100;

Fill-Multiplication
In fact, we can replace parallel prefix left shifts like,

x |= x << 32;
x |= x << 16;
x |= x <<  8;

where x has max one bit per file, and we can therefor safely replace 'or' by 'add'

x += x << 32;
x += x << 16;
x += x <<  8;

by multiplication with 0x0101010101010101 (which is the A-File in little endian mapping):

. . . . . . . .     1 . . . . . . .     . 1 1 . 1 1 . .
. . . . . . . .     1 . . . . . . .     . 1 1 . 1 1 . .
. . . . . . . .     1 . . . . . . .     . 1 1 . 1 1 . .
. . . . . . . .     1 . . . . . . .     . 1 1 . 1 1 . .
. 1 . . . 1 . .  *  1 . . . . . . .  =  . 1 1 . 1 1 . .
. . 1 . 1 . . .     1 . . . . . . .     . . 1 . 1 . . .
. . . . . . . .     1 . . . . . . .     . . . . . . . .
. . . . . . . .     1 . . . . . . .     . . . . . . . .

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

De Bruijn 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.

Division

64-bit Division is still a slow instruction which takes a lot of cycles - it should be avoided at runtime. Division by a power of two is done by right shift.

An interesting application to calculate various masks for delta swaps, e.g. swapping bits, bit-duos, nibbles, bytes, words and double words, is the 2-adic division of the universal set (-1) by 2^(2^i) plus one, which may be done at compile time:

-1 / ( 2^(2^0) + 1) == -1 / (         2 + 1) == 0x5555555555555555
-1 / ( 2^(2^1) + 1) == -1 / (         4 + 1) == 0x3333333333333333
-1 / ( 2^(2^2) + 1) == -1 / (        16 + 1) == 0x0f0f0f0f0f0f0f0f
-1 / ( 2^(2^3) + 1) == -1 / (       256 + 1) == 0x00ff00ff00ff00ff
-1 / ( 2^(2^4) + 1) == -1 / (     65536 + 1) == 0x0000ffff0000ffff
-1 / ( 2^(2^5) + 1) == -1 / (4294967296 + 1) == 0x00000000ffffffff

See generalized flipping, mirroring and reversion. Often used masks and factors are the 2-adic division of the universal set (-1) by 2^(2^i) minus one, which results in the lowest bit of SWAR-wise bits set, bit-duos, nibbles, bytes, words and double words:

-1 / ( 2^(2^0) - 1) == -1 / (         2 - 1) == 0xffffffffffffffff
-1 / ( 2^(2^1) - 1) == -1 / (         4 - 1) == 0x5555555555555555
-1 / ( 2^(2^2) - 1) == -1 / (        16 - 1) == 0x1111111111111111
-1 / ( 2^(2^3) - 1) == -1 / (       256 - 1) == 0x0101010101010101
-1 / ( 2^(2^4) - 1) == -1 / (     65536 - 1) == 0x0001000100010001
-1 / ( 2^(2^5) - 1) == -1 / (4294967296 - 1) == 0x0000000100000001

Modulo

Modular arithmetic with 64-bit modulo by a constant, has applications in Cryptography ^[14], Hashing, and with Bitboards in Bit Scanning, Population Count and Congruent Modulo Bitboards for Sliding Piece Attacks.

Casting out 255

Similar to Casting out nines with decimals and due to the congruence relation

${Base^n} \equiv 1 \pmod{Base-1}$

casting out 255 can be used to add all the eight bytes within a SWAR-wise 64-bit quad word if the sum is less than 255, as mentioned, applicable in Population Count and Congruent Modulo Bitboards - Casting out 255.

Reciprocal Multiplication

Likely 64-bit compiler will optimize modulo (and division) by reciprocal, 2^64 div constant, to perform a 64*64 = 128bit fixed point multiplication to get the quotient in the upper 64-bit, and a second multiplication and subtraction to finally get the remainder. Here some sample x86-64 assembly:

r11d := r10 % 257
 mov    r11d, r10 ; masked diagonal
 mov    rax, ff00ff00ff00ff01H ; 2^(64+8) / 257
 mul    r10
 shr    rdx, 8
 imul   edx, 257 ; 00000101H
 sub    r11d, edx

Power of Two

As a remainder, and to close the cycle to bitwise boolean operations, the well known trick is mentioned, to replace modulo by power of two by intersection with power of two minus one:

 a % 2^n == a & (2^n - 1)

Selected Publications

1847 ...

George Boole (1847). The Mathematical Analysis of Logic, Being an Essay towards a Calculus of Deductive Reasoning. Macmillan, Barclay & Macmillan
George Boole (1848). The Calculus of Logic. Cambridge and Dublin Mathematical Journal, Vol. III
Augustus De Morgan (1860). Syllabus of a Proposed System of Logic. Walton & Malbery
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
Georg Cantor (1874). Ueber eine Eigenschaft des Inbegriffes aller reellen algebraischen Zahlen. Journal für die reine und angewandte Mathematik, No. 77
Charles S. Peirce (1880). On the Algebra of Logic. American Journal of Mathematics, Vol. 3
Charles S. Peirce (1880). On the Algebra of Logic. American Journal of Mathematics, Vol. 3
John Venn (1880). On the Diagrammatic and Mechanical Representation of Propositions and Reasonings. Philosophical Magazine, Vol. 9, No. 5
John Venn (1881). Symbolic Logic. MacMillan & Co.

1950 ...

Lazar A. Lyusternik, Aleksandr A. Abramov, Victor I. Shestakov, Mikhail R. Shura-Bura (1952). Programming for High-Speed Electronic Computers. (Программирование для электронных счетных машин)
Christopher Strachey (1961). Bitwise operations. Communications of the ACM, Vol. 4, No. 3

2000 ...

Henry S. Warren, Jr. (2002, 2012). Hacker's Delight. Addison-Wesley
Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript

Forum Posts

curiosity killed the cat... hi/lo bit C verses Assembly by Dann Corbit, CCC, July 17, 2003
mask of highest bit by Andrew Shapira, CCC, September 21, 2005
How to Shift Left (by) a Negative Number?? by Steve Maughan, CCC, April 05, 2013
To shift or not to shift by thevinenator, OpenChess Forum, September 09, 2015

External Links

Sets

Algebra

Logic

Operations

Modular arithmetic

Misc

Casiopea - Conjunction, Perfect Live (1986), YouTube Video
Hux Flux - Bitshifter, Division by Zero, YouTube Video

References

^ Andrey Ershov, Mikhail R. Shura-Bura (1980). The Early Development of Programming in the USSR. in Nicholas C. Metropolis (ed.) A History of Computing in the Twentieth Century. Academic Press, preprint pp. 43
^ Lazar A. Lyusternik, Aleksandr A. Abramov, Victor I. Shestakov, Mikhail R. Shura-Bura (1952). Programming for High-Speed Electronic Computers. (Программирование для электронных счетных машин)
^ John Venn (1880). On the Diagrammatic and Mechanical Representation of Propositions and Reasonings. Philosophical Magazine, Vol. 9, No. 59
^ Wassily Kandinsky - Yellow Circle, 1926 from Art-postcards and museum-shop, Reisser-Kunstpostkarten.de
^ Greater or less in the arithmetical sense is usually not relevant with bitboards, but see greater condition in Thor's Hammer's move generation
^ George Boole (1847). The Mathematical Analysis of Logic, Being an Essay towards a Calculus of Deductive Reasoning. Macmillan, Barclay & Macmillan
^ Charles S. Peirce (1880). On the Algebra of Logic. American Journal of Mathematics, Vol. 3
^ Augustus De Morgan (1860). Syllabus of a Proposed System of Logic. Walton & Malbery
^ Marvin Minsky, Seymour Papert (1969, 1972). Perceptrons: An Introduction to Computational Geometry. The MIT Press, ISBN 0-262-63022-2
^ Re: Java chess program? by Moritz Berger, rgcc, May 29, 1997 » Shifting Bitboards, Java
^ To shift or not to shift by thevinenator, OpenChess Forum, September 09, 2015
^ Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript
^ Peter Wegner (1960). A technique for counting ones in a binary computer. Communications of the ACM, Volume 3, 1960
^ Modular exponentiation from Wikipedia

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
Alen Shapiro	May 3, 2015
Algorithms	May 5, 2017
All Shortest Paths	Jan 21, 2014
AltiVec	Jun 7, 2016
Andrew Shapira	May 7, 2017
Assembly	Sep 3, 2017
Attack Spans	Mar 4, 2010
AVX-512	Aug 8, 2017
Backtracking	Dec 16, 2017
Bit	Oct 29, 2012
Bit-Twiddling	Nov 6, 2017
Bitboard Board-Definition	Jun 23, 2014
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Bitfoot	Sep 8, 2015
BitScan	Sep 10, 2017
Blockage Detection	Oct 19, 2017
Blockers and Beyond	Mar 21, 2014
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
Board Representation	Dec 11, 2017
Captures	Oct 1, 2017
Chess 0.5	Nov 20, 2016
Classical Approach	Jan 28, 2018
Color Flipping	May 17, 2017
Color of a Square	May 24, 2015
Combinatorial Logic	Apr 6, 2017
Congruent Modulo Bitboards	Jun 26, 2013
Control of Stop and Telestop	Feb 26, 2013
Crafty	Jan 28, 2018
Dictionary	Aug 24, 2017
DirGolem	Jun 5, 2016
Double Attack	Oct 22, 2014
Dumb7Fill	May 27, 2016
Duo Trio Quart (Bitboards)	Aug 18, 2017
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Ferranti Mark 1	Jun 2, 2015
Fill Algorithms	Nov 6, 2013
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
GiuChess	May 8, 2017
Henry S. Warren, Jr.	Oct 14, 2016
Holes	Oct 16, 2017
Horizontal Mirroring	Jun 29, 2013
Houdini	Apr 14, 2018
Hyperbola Quintessence	Mar 25, 2017
Incremental Updates	Sep 6, 2017
Intersection Squares	Oct 4, 2014
Isolated Pawns (Bitboards)	Nov 18, 2012
Ivan Bratko	Aug 16, 2017
Java	Feb 25, 2018
Joker IT	Sep 16, 2017
Jonathan Warkentin	Jun 29, 2014
Kim Walisch	Aug 10, 2017
Kindergarten Bitboards	Aug 1, 2017
King Pattern	Nov 15, 2013
Knight Pattern	Feb 23, 2015
Kogge-Stone Algorithm	Sep 17, 2016
Kurt	Apr 20, 2014
Magic Bitboards	Apr 13, 2018
Make Move	Mar 2, 2016
Mate at a Glance	Sep 24, 2014
Mathematician	Apr 9, 2018
Mikhail R. Shura-Bura	Oct 30, 2013
Moritz Berger	Feb 25, 2018
Moves	Feb 19, 2018
Obstruction Difference	May 27, 2016
Occupancy	Sep 19, 2016
Occupancy of any Line	Sep 16, 2016
OliThink	May 19, 2017
Opposition	Dec 2, 2014
Othello	Jan 4, 2018
Parallel Prefix Algorithms	Jun 22, 2016
Passed Pawn	Oct 11, 2017
Passed Pawns (Bitboards)	Aug 23, 2010
Pawn Attacks (Bitboards)	Mar 4, 2010
Pawn Islands (Bitboards)	May 4, 2017
Pawn Pushes (Bitboards)	Apr 5, 2013
Pawn Rams (Bitboards)	Nov 11, 2017
Pawns and Files (Bitboards)	Jan 16, 2013
Piece-Sets	Jun 9, 2017
Pieces versus Directions	Oct 6, 2016
Pin	Mar 7, 2017
Population Count	Sep 3, 2017
Reverse Bitboards	Aug 29, 2015
Rotated Bitboards	Mar 7, 2017
Ryan Mack	Jan 18, 2011
SBAMG	Dec 4, 2016
Score	Apr 14, 2018
Shared Hash Table	Sep 11, 2017
Shifted Bitboards	Jan 9, 2011
SIMD and SWAR Techniques	Jun 27, 2017
Simona Tancig	Nov 7, 2012
Sliding Piece Attacks	May 27, 2016
Sloppy	Sep 17, 2016
Space-Time Tradeoff	Jun 17, 2015
Square Attacked By	Jan 20, 2018
SSE2	Feb 27, 2018
SSSE3	Aug 8, 2017
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
TBM	Jun 28, 2012
Thor's Hammer	Nov 23, 2013
Transposition Table	Apr 19, 2018
Traversing Subsets of a Set	Oct 14, 2016
Tunguska	Sep 16, 2017
Unmake Move	Jun 10, 2017
Vertical Flipping	Oct 10, 2013
Vice	Mar 8, 2016
x86-64	Mar 6, 2018
XOP	Aug 8, 2017
Zdenek Zdrahal	Apr 4, 2013
Zevra	Mar 12, 2018
Zobrist Hashing	Jan 22, 2018

Up one Level

Hyperbola Quintessence

camleon — Sat, 25 Mar 2017 14:31:28 GMT

Home * Board Representation * Bitboards * Sliding Piece Attacks * Hyperbola Quintessence

Hyperbola Quintessence applies the o^(o-2r)-trick also for vertical or diagonal negative Rays - by reversing the bit-order of up to one bit per rank or byte with a vertical flip aka x86-64 bswap ^[1] . It is somehow a resurrection of the reverse bitboards idea of Ryan Mack's Hyperbola Project on the fly, and was created by Gerd Isenberg. Improvements by Aleks Peshkov ^[2] made it applicable and competitive.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

Samuel Bak - Reflexion, 1990 ^[3]

Reverse Math

Source Code

Generalized set-wise attacks

x86-64 assembly

Java

AMD's SIMD Future in 2011

Reverse Math

Assume following masked occupancy on a file, diagonal or anti-diagonal - for simplicity as a flat byte (in a real bitboard with masked files or diagonals you have 6..8 scratch-bits between the bits of this byte). Thus, vertical flip reverses the bits of this byte.

o' = reverse(o)
r' = reverse(r)
 
       normal    reversed
 o     11010101  10101011 o' occupancy including slider
 r     00010000  00001000 r' slider
 o-r   11000101  10100011 o'-r'  1. sub clears the slider
 o-2r  10110101  10011011 o'-2r' 2. sub borrows "one" from next blocker
       |......|  \....../
normal 10110101   \..../
       11011001 <--XXXX   re-reverse
single
xor    01101100 -> to get the attack set

The first subtraction of (o-2r) is done implicitly by masking off the line, removing the slider from the occupied set. The second subtraction borrows a "one" from the next nearest blocker in msb-direction, falling through all unset bits outside the line. Of course, if no blocker is available, it borrows a "one" in usual arithmetical manner from the hidden 2^N. Only the changed bits (from original o, o') are the appropriate sliding attacks, including the blocker but excluding the slider. The result finally needs to be intersected with the same line mask as previously the occupancy, to clear the wrapped borrow one bits outside the file or diagonal. The fine optimization by Aleks Peshkov covers the final union of positive and negative ray-attacks. Since opposed ray-directions are always disjoint sets, using xor instead of bitwise or safes two instructions per line-attack. That is because bit-reversal or any mirroring or flipping is own inverse and distributive over xor.

reverse(a ^ b) == reverse (a) ^ reverse(b)

thus

lineAttacks = o^(o-2r) ^ reverse((o'-2r')^o')
lineAttacks = o^(o-2r) ^ reverse( o'-2r') ^ reverse(o')
lineAttacks = o^(o-2r) ^ reverse( o'-2r') ^ o

and finally

lineAttacks =   (o-2r) ^ reverse( o'-2r')

Beside shorter code this reduces register pressure - and clearly outperforms kindergarten bitboards - ipc-wise, in code size and memory requirements.

Source Code

C

The three C-routines only differ by the line-mask applied:

U64 diagonalAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward = occ & smsk[sq].diagonalMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].diagonalMaskEx;
   return forward;
}
 
U64 antiDiagAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].antidiagMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].antidiagMaskEx;
   return forward;
}
 
U64 fileAttacks(U64 occ, enumSquare sq) {
   U64 forward, reverse;
   forward  = occ & smsk[sq].fileMaskEx;
   reverse  = _byteswap_uint64(forward);
   forward -= smsk[sq].bitMask;
   reverse -= _byteswap_uint64(smsk[sq].bitMask);
   forward ^= _byteswap_uint64(reverse);
   forward &= smsk[sq].fileMaskEx;
   return forward;
}
 
U64 bishopAttacks(U64 occ, enumSquare sq) {
   return diagonalAttacks (occ, sq)
        + antiDiagAttacks (occ, sq);
}

For better locality of the line-attacks on the otherwise empty board, we may use an properly aligned array of structs.

struct
{
   U64 bitMask;         // 1 << sq for convenience
   U64 diagonalMaskEx;
   U64 antidiagMaskEx;
   U64 fileMaskEx;
} smsk[64]; // 2 KByte

Using x86-64 bswap makes it quite competitive for bishops and files, on AMD K8 or K10 it has a latency of one cycle with a throughput of 1/3, like other cheap instructions. However, Intel is tad slower - while the recent Core 2 duo processors perform 128-bit SIMD-instructions with 128-bit alus, that is bitwise logical instructions with a latency of one cycle and throughput of 1/3, the general purpose bswap-instruction takes four cycles with a throughput of one. In Intel 64 and IA32 Architectures Optimization Reference Manual ^[4] , it is therefor recommend (5.6.5. endian conversion) to use the SSSE3 pshufb instruction to swap bytes, available through intrinsic ^[5] , see SSSE3 Hyperbola Quintessence for bishop attacks.

As long there is no fast bit reversal instruction, there is no general solution for all four lines, and the rook attack-getter still needs some standard technique for the rank-attacks. Tim Cooijmans proposed to map the rank to the main diagonal before applying HQ, and to re-map the calculated attacks back to the original rank ^[6] .

Generalized set-wise attacks

Hyperbola quintessence can be generalized to work on whole sets of sliding pieces instead on individual pieces, whose ranks to be masked. The problem arising, when not masking the rank of the piece is that attacks wrap around the board during subtraction. This is shown below:

     ........       ........                            11111111
     ........       ........                            11111111
     ........       ........                            11111111
 r = ........ , o = ........ this leads to   o - 2*r =  11111111
     ........       ........                            11111111
     ........       ........                            11111111
     ....1...       ....1...                            11111...
     ........       ........                            ........
 
instead of
 
........
........
........
........
........
........
11111...
........

This is not the intended result. It can be avioded, by bitwise adding an overflow barrier on the right-hand side. Afterwards this barrier needs to be removed from the attack set:

u64 right = 0x0101010101010101ULL;
 
     ......1.      1..1..1.                              1...1111
     ....1...      1...1...                              .1111..1
     ......1.      11....1.                              1.111111
r =  .....1..  o = .11..1..   now: ((o | right) - 2*r) = .1.111.1
     ........      ........                              ........
     ......1.      ......1.                              1111111.
     .......1      .......1                              1111111.
     1.......      1.......                              1......1
 
Note, that the 4th rank was not flooded by the subtraction! Next, the blockers are removed as usual:
 
                          ...111.1
                          1111...1
                          .11111.1
o ^ ((o | right) - 2*r) = ..111..1
                          ........
                          111111..
                          11111111
                          .......1
 
The last step is to remove the barrier at the right side that became visible after the last operation.
 
                                     ...111..
                                     1111...
                                     .11111..
(o ^ ((o | right) - 2*r) & ~right =  ..111...
                                     ........
                                     111111..
                                     1111111.
                                     ........
 
This is the correct attack set for the left direction.

the complete algorithm for the left direction is therefore:

const u64 right = 0x0101010101010101ULL;
 
u64 leftAttacks = ((o ^ ((o | right) - 2*r) & ~right);

For the right-hand direction, the bits need to be reversed rank-wise.

x86-64 assembly

The VC2005 generated x86-64 assembly of bishopAttacks indicates what ipc-monster Hyperbola Quintessence is:

occ$ = 16
sq$ = 24
?bishopAttacks@@YA_K_KI@Z PROC
  00000   40 53                push    rbx
  00002   8b c2                mov    eax, edx
  00004   4c 8d 15 00 00 00 00 lea    r10, OFFSET FLAT:?smsk
  0000b   48 c1 e0 05          shl    rax, 5
  0000f   4a 8b 5c 10 08       mov    rbx, QWORD PTR [rax+r10+8]  ; diagonalMaskEx
  00014   4e 8b 4c 10 10       mov    r9,  QWORD PTR [rax+r10+16] ; antidiagMaskEx
  00019   4e 8b 14 10          mov    r10, QWORD PTR [rax+r10]    ; r := 1 << sq
  0001d   4c 8b db             mov    r11, rbx                    ; diagonalMaskEx
  00020   49 8b d1             mov    rdx, r9                     ; antidiagMaskEx
  00023   4d 8b c2             mov    r8, r10                     ; r := 1 << sq
  00026   48 23 d1             and    rdx, rcx                    ; anti & occ
  00029   4c 23 d9             and    r11, rcx                    ; dia  & occ
  0002c   49 0f c8             bswap  r8                          ; r'
  0002f   48 8b c2             mov    rax, rdx                    ; ant
  00032   49 8b cb             mov    rcx, r11                    ; dia
  00035   49 2b d2             sub    rdx, r10                    ; ant - r
  00038   48 0f c8             bswap  rax                         ; ant'
  0003b   48 0f c9             bswap  rcx                         ; dia'
  0003e   4d 2b da             sub    r11, r10                    ; dia - r
  00041   49 2b c0             sub    rax, r8                     ; ant' - r'
  00044   49 2b c8             sub    rcx, r8                     ; dia' - r'
  00047   48 0f c8             bswap  rax                         ;(ant' - r')'
  0004a   48 0f c9             bswap  rcx                         ;(dia' - r')'
  0004d   48 33 c2             xor    rax, rdx                    ; ant := (ant' - r')' ^ (ant - r)
  00050   49 33 cb             xor    rcx, r11                    ; dia := (dia' - r')' ^ (dia - r)
  00053   49 23 c1             and    rax, r9                     ; ant &= antidiagMaskEx
  00056   48 23 cb             and    rcx, rbx                    ; dia &= diagonalMaskEx
  00059   48 03 c1             add    rax, rcx                    ; attacks := dia + ant
  0005c   5b                   pop    rbx
  0005d   c3                   ret    0
?bishopAttacks@@YA_K_KI@Z ENDP

Java

Java programmer may try Long.reverseBytes:

    static private final long[] bitMask = {
        0x0000000000000001, 0x0000000000000002, 0x0000000000000004, 0x0000000000000008,
        0x0000000000000010, 0x0000000000000020, 0x0000000000000040, 0x0000000000000080,
        ...
    };
 
    static private final long[] diagonalMaskEx = {
        0x8040201008040200, 0x0080402010080400, 0x0000804020100800, 0x0000008040201000,
        0x0000000080402000, 0x0000000000804000, 0x0000000000008000, 0x0000000000000000,
        ...
    };
 
    /**
     * @param occ - occupancy
     *        sq  - from square
     * @return diagonal attacks from sq with occupancy occ
     */
    static public long diagonalAttacks(long occ, int sq)
    {
       long forward = occ & diagonalMaskEx[sq];
       long reverse = Long.reverseBytes(forward);
       forward -= bitMask[sq];
       reverse -= bitMask[sq^56];
       forward ^= Long.reverseBytes(reverse);
       forward &= diagonalMaskEx[sq];
       return forward;
    }

Long.reverse for a generalized attack getter even for ranks is too expensive, except a JVM can use a machine instruction rather than a bit-reversal routine:

    /**
     * @param occ  - occupancy
     *        line - {0..3} {rank, file, diagonal, antidiagonal}
     *        sq   - from square
     * @return attacks from sq on line with occupancy occ
     */
    static public long attacks(long occ, int line, int sq)
    {
       long forward = occ & maskEx[sq][line];
       long reverse = Long.reverse(forward);
       forward -= bitMask[sq];
       reverse -= bitMask[sq^63];
       forward ^= Long.reverse(reverse);
       forward &= maskEx[sq][line];
       return forward;
    }

AMD's SIMD Future in 2011

In 2007 AMD announced the hypothetical SSE5 instruction set ^[7] with a PPERM instruction ^[8] , which would be able to reverse vectors of two bitboards. In May 2009 AMD revised SSE5, to become more compatible with Intel's Advanced Vector Extensions, and also expanding the SIMD-register width from 128 to 256-bit, the renamed XOP instruction set ^[9] . However, the successor of the planned PPERM SSE5-instruction is now called VPPERM, but still works on 128-bit XMM registers ^[10] . VPPERM instruction requires four operands (xmm-registers):

 VPPERM dest, src1, src2, selector

For each of 16 destination bytes the corresponding selector-byte addresses one of 32 input bytes (from src1, src2) and a logical operation including bit-reversal:

char src[32];   // src2:src1
char select[16];
char dest[16];
for (int i = 0; i < 16; i++) {
   char opera = select[i] >>> 5; // unsigned shift
   char idx32 = select[i] & 31;
 
   switch ( opera ) {
      case 0: dest[i] =  src[idx32]; break;
      case 1: dest[i] = ~src[idx32]; break;
      case 2: dest[i] =  bitreverse( src[idx32]); break;
      case 3: dest[i] = ~bitreverse( src[idx32]); break;
      case 4: dest[i] = 0x00; break;
      case 5: dest[i] = 0xFF; break;
      case 6: dest[i] =  src[idx32] >> 7;  break; // signed shift
      case 7: dest[i] = ~src[idx32] >> 7;  break; // signed shift
   }
}

Since VPPERM can simultaneously reverse bits and bytes, it can for instance reverse two bitboards in one run, even from different sources, to make Hyperbola Quintessence work for all four lines.

Forum Posts

Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Aleks Peshkov, CCC, August 25, 2007
Hyperbola Quiesscene: hardly any improvement by trojanfoe, CCC, January 13, 2009
Comparison of bitboard attack-getter variants by Sven Schüle, CCC, January 04, 2016
Re: The wrong way by Aleks Peshkov, CCC, January 05, 2016 » SSSE3 Hyperbola Quintessence

External Links

Sliding Pieces (Part 1) - Advanced Java Chess Engine Tutorial 8 by Jonathan Warkentin
Hyperbola Quintessence for rooks along ranks by Tim Cooijmans, April 6, 2014 ^[11]

Hyperbola

Quintessence

Misc

Focus - Hocus Pocus, Pinkpop Festival 1972, Geleen, YouTube Video

References

^ _byteswap_uint64 Visual C++ Developer Center - Run-Time Library Reference
^ Re: BitBoard Tests Magic v Non-Rotated 32 Bits v 64 Bits by Aleks Peshkov, CCC, August 25, 2007
^ The Game of War from Samuel Bak - represented by Pucker Gallery since 1969
^ Intel 64 and IA32 Architectures Optimization Reference Manual (pdf)
^ _mm_shuffle_epi8 Visual C++ Developer Center - Run-Time Library Reference
^ Hyperbola Quintessence for rooks along ranks by Tim Cooijmans, April 6, 2014
^ 128-Bit SSE5 Instruction Set from AMD Developer Central
^ SSE5 permutations
^ XOP instruction set from Wikipedia
^ Volume 6: 128-Bit and 256-Bit XOP, FMA4 and CVT16 Instructions (pdf), see VPPERM pg. 221
^ Re: Comparison of bitboard attack-getter variants by Matthew R. Brades, CCC, January 04, 2016

What links here?

Page	Date Edited
Aleks Peshkov	Jan 13, 2016
Amoeba	Mar 19, 2018
Dumb	Mar 10, 2018
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Endianness	Jan 25, 2015
Fill Algorithms	Nov 6, 2013
First Rank Attacks	Aug 28, 2010
Flipping Mirroring and Rotating	Oct 14, 2016
General Setwise Operations	Feb 25, 2018
Hiding the Implementation	Feb 3, 2011
Hyperbola Quintessence	Mar 25, 2017
Java	Feb 25, 2018
Jonathan Warkentin	Jun 29, 2014
Karlo Bala Jr.	Feb 19, 2017
Kindergarten Bitboards	Aug 1, 2017
Kogge-Stone Algorithm	Sep 17, 2016
Parallel Prefix Algorithms	Jun 22, 2016
Reverse Bitboards	Aug 29, 2015
Ryan Mack	Jan 18, 2011
SBAMG	Dec 4, 2016
SIMD techniques	Nov 26, 2017
Sliding Piece Attacks	May 27, 2016
SSSE3	Aug 8, 2017
Subtracting a Rook from a Blocking Piece	Dec 2, 2016
Syed Fahad	Jan 1, 2017
XOP	Aug 8, 2017

Up one Level

MMX

GerdIsenberg — Sun, 05 Jun 2016 21:59:15 GMT

Home * Hardware * x86 * MMX

		MMX is a SIMD (Single instruction, multiple data) instruction set of x86 processors, starting in 1996 with Intel's Pentium MMX. In 1998, AMD enhanced Intel's MMX with the 3DNow! extension, mostly related to the Float data type. MMX instructions are available through Assembly language, inline assembly and C-Compiler intrinsics along with the _m64 intrinsic data type ^[1] .
Pentium MMX 166 MHz ^[2]

MMX and 64-bit Windows

Register File

MMX uses eight 64-bit registers MM0 through MM7, treated each as vector of eight bytes, four words, two double words or one quad word. The eight registers were aliased for the existing x87 FPU stack registers, and are therefor implicitly saved and restored during context switch in existing operating systems. The drawback is, it is somewhat difficult to work with x87 floating point and MMX data in the same application, since the original emms-instruction to switch the register file was relatively slow.

MMX and 64-bit Windows

Since 64-bit Windows applications merely use SSE for floating point arithmetic, there was some early confusion whether MMX/x87 registers are safe to use due to context switching. Quote from Agner Fog's Calling conventions manual: ^[3]

6.1 Can floating point registers be used in 64-bit Windows?

There has been widespread confusion about whether 64-bit Windows allows the use of the floating point registers ST(0)-ST(7) and the MM0 - MM7 registers that are aliased upon these. One early technical document found at Microsoft's website says x87/MMX registers are unavailable to Native Windows64 applications" (Rich Brunner: Technical Details Of Microsoft® Windows® For The AMD64 Platform, Dec. 2003). An AMD document says: "64-bit Microsoft Windows does not strongly support MMX and 3Dnow! instruction sets in the 64-bit native mode" (Porting and Optimizing Multimedia Codecs for AMD64 architecture on Microsoft® Windows®, July 21, 2004). A document in Microsoft's MSDN says: "A caller must also handle the following issues when calling a callee: [...] Legacy Floating-Point Support: The MMX and floating-point stack registers (MM0-MM7/ST0-ST7) are volatile. That is, these legacy floating-point stack registers do not have their state preserved across context switches" (MSDN: Kernel-Mode Driver Architecture: Windows DDK: Other Calling Convention Process Issues. Preliminary, June 14, 2004; February 18, 2005).

This description is nonsense because it confuses saving registers across function calls and saving registers across context switches. Some versions of the Microsoft assembler ml64 (e.g. v. 8.00.40310) gives the following message when attempts are made to use floating point registers in 64 bit mode: "error A2222: x87 and MMX instructions disallowed; legacy FP state not saved in Win64". However, a public discussion forum quotes the following answers from Microsoft engineers regarding this issue: "From: Program Manager in Visual C++ Group, Sent: Thursday, May 26, 2005 10:38 AM. It does preserve the state. It's the DDK page that has stale information, which I've requested it to be changed. Let them know that the OS does preserve state of x87 and MMX registers on context switches." and "From: Software Engineer in Windows Kernel Group, Sent: Thursday, May 26, 2005 11:06 AM. For user threads the state of legacy floating point is preserved at context switch. But it is not true for kernel threads. Kernel mode drivers can not use legacy floating point instructions."

The issue has finally been resolved with the long overdue publication of a more detailed ABI for x64 Windows in the form of a document entitled "x64 Software Conventions", well hidden in the bin directory (not the help directory) of some compiler packages. This document says: "The MMX and floating-point stack registers (MM0-MM7/ST0-ST7) are preserved across context switches. There is no explicit calling convention for these registers. The use of these registers is strictly prohibited in kernel mode code." The same text has later appeared at the Microsoft website ^[4].

Applications

Almost the same bitboard applications as mentioned in the SSE2 application samples are possible with MMX, despite with scalar bitboards rather than vector of two.

East Fill

For instance East Attacks based on SIMD-wise Fill by Subtraction.

__m64 eastAttacks (__m64 occ, __m64 rooks) {
   __m64 tmp;
   occ  = _mm_or_si64 (occ, rooks);  //  make rooks member of occupied
   tmp  = _mm_xor_si64(occ, rooks);  // occ - rooks
   tmp  = _mm_sub_pi8 (tmp, rooks);  // occ - 2*rooks
   return _mm_xor_si64(occ, tmp);    // occ ^ (occ - 2*rooks)
}

MMX Popcount

AMD's proposed Efficient 64-Bit Population Count using MMX, 3DNow! and inline assembly ^[5] :

#include "amd3d.h"
 
__declspec (naked) unsigned int __stdcall popcount64 (unsigned __int64 v)
{
   static const __int64 C55 = 0x5555555555555555;
   static const __int64 C33 = 0x3333333333333333;
   static const __int64 C0F = 0x0F0F0F0F0F0F0F0F;
   __asm {
      MOVD      MM0, [ESP+4] ;v_low
      PUNPCKLDQ MM0, [ESP+8] ;v
      MOVQ      MM1, MM0     ;v
      PSRLD     MM0, 1       ;v >> 1
      PAND      MM0, [C55]   ;(v >> 1) & 0x55555555
      PSUBD     MM1, MM0     ;w = v - ((v >> 1) & 0x55555555)
      MOVQ      MM0, MM1     ;w
      PSRLD     MM1, 2       ;w >> 2
      PAND      MM0, [C33]   ;w & 0x33333333
      PAND      MM1, [C33]   ;(w >> 2) & 0x33333333
      PADDD     MM0, MM1     ;x = (w & 0x33333333) + ((w >> 2) & 0x33333333)
      MOVQ      MM1, MM0     ;x
      PSRLD     MM0, 4       ;x >> 4
      PADDD     MM0, MM1     ;x + (x >> 4)
      PAND      MM0, [C0F]   ;y = (x + (x >> 4) & 0x0F0F0F0F)
      PXOR      MM1, MM1     ; 0
      PSADBW    MM0, MM1     ;sum across all 8 bytes
      MOVD      EAX, MM0     ;result in EAX per calling
      ; convention
      FEMMS ;clear MMX state
      RET 8 ;pop 8-byte argument off
   }
}

Manuals

Intel

Intel Architecture Software Developer’s Manual, Volume 1: Basic Architecture (pdf)

AMD

Forum Posts

Using mmx instructions by Frans Morsch, comp.lang.asm.x86, February 03, 2000
Re: Atomic write of 64 bits by Frans Morsch, comp.lang.asm.x86, September 25, 2000
Re: Chezzz 1.0.1 - problem solved - for David Rasmussen by David Rasmussen, CCC, February 05, 2003 » Population Count, Chezzz

External Links

References

^ MMX Technology Intrinsic Groups
^ Intel P5 (microarchitecture) from Wikipedia
^ Calling conventions for different C++ compilers and operating systems (pdf) by Agner Fog
^ Legacy Floating-Point Support (C++) from MSDN Library
^ AMD Athlon Processor x86 Code Optimization Guide (pdf) Efficient 64-Bit Population Count Using MMX™ Instructions Page 184

What links here?

Page	Date Edited
Aart Bik	Mar 1, 2018
AltiVec	Jun 7, 2016
AMD	Mar 9, 2018
AVX	Mar 7, 2017
AVX2	Aug 8, 2017
Axon	Jul 14, 2013
Byte	Apr 5, 2013
Chezzz	Jan 20, 2013
David Rasmussen	Dec 16, 2017
Float	Nov 11, 2016
Frans Morsch	Jun 23, 2017
Freccia	Dec 26, 2017
General Setwise Operations	Feb 25, 2018
Gunnar Andersson	Jun 23, 2011
HansDamf	Jun 27, 2012
i860	Aug 21, 2015
Intel	Aug 29, 2015
MMX	Jun 5, 2016
Othello	Jan 4, 2018
Papa	Jan 11, 2018
Population Count	Sep 3, 2017
Rabbit	Oct 5, 2014
Reverse Bitboards	Aug 29, 2015
SIMD and SWAR Techniques	Jun 27, 2017
SIMD techniques	Nov 26, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSSE3	Aug 8, 2017
Transposition Table	Apr 19, 2018
Windows	Nov 2, 2017
Word	Jan 25, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018

Up one Level

Population Count

GerdIsenberg — Sun, 03 Sep 2017 19:37:48 GMT

Home * Board Representation * Bitboards * Population Count

		Population count determines the cardinality of a bitboard, also called Hamming weight or sideways sum ^[1]. How many one bits exists in a 64-bit computer word? In computer chess, population count is used to evaluate the mobility of pieces from their attack sets, as already applied in Chess 4.6 on the CDC 6600 and CDC Cyber. Future or recent x86-64 processors (AMD K10 - SSE4a, Intel Nehalem - SSE4.2) provide a 64-bit popcount instruction ^[2], available via C++ compiler intrinsic ^[3]^[4]^[5]^[6] or inline assembly ^[7]. Despite different Intrinsic prototypes (_mm_popcnt_u64 vs. popcnt64), Intel and AMD popcnt instructions are binary compatible, have same encoding (F3 [REX] 0F B8 /r), and both require bit 23 set in RCX of the CPUID function 0000_0001h.
Visualization of Hamming distance ^[8]

Code samples in C / C++, see Defining Bitboards

Recurrence Relation

The recursive recurrence relation of population counts can be transformed to iteration as well, but lacks an arithmetical sum-formula:

$popcnt(0) = 0$
$popcnt(n) = {popcnt({n} \div {2}) + ({n} \mod {2})}$

However, it is helpful to initialize a lookup table, i.e. for bytes:

unsigned char popCountOfByte256[];
 
void initpopCountOfByte256()
{
   popCountOfByte256[0] = 0;
   for (int i = 1; i < 256; i++)
      popCountOfByte256[i] = popCountOfByte256[i / 2] + (i & 1);
}

Empty or Single?

Often one has to deal with sparsely populated or even empty bitboards. To determine whether a bitboard is empty or a single populated power of two value, one may use simple boolean statements rather than a complete population count.

Empty Bitboards

To test a bitboard is empty, one compares it with zero, or use the logical not operator:

if ( x == 0 ) -> bitboard is empty
if ( !x )     -> bitboard is empty

The inverse condition (not empty) is of course

if ( x != 0 ) -> bitboard is not empty
if ( x )      -> bitboard is not empty

Single Populated Bitboards

If the bitboard is not empty, we can extract the LS1B to look whether it is equal with the bitboard. Alternatively and faster, we can reset the LS1B to look whether the bitboard becomes empty.

if ( x != 0 && (x & (x-1)) == 0 ) -> population count is one, power of two value

One can skip the leading x != 0 condition to test popcount <= 1:

if ( (x & (x-1)) == 0 ) -> population count is less or equal than one

Again the inverse relation tests, whether a bitboard has more than one bit set:

if ( x & (x-1) ) -> population count is greater than one

An alternative approach to determine single populated sets, aka power of two values is based on Inclusive LS1B separation divided by two equals the ones' decrement ^[9]:

if ( ((x ^ (x-1)) >> 1) == (x-1) ) -> population count is one, power of two value

Loop-Approaches

Too Slow

Brute force adding all 64-bits

int popCount (U64 x) {
   int count = 0;
   for (int i = 0; i < 64; i++, x >>= 1)
      count += (int)x & 1;
   return count;
}

Of course, this is a slow algorithm, which might be improved by testing x not empty rather than i < 64. But unrolled in parallel prefix manner it already reminds on this one.

Brian Kernighan's way

Consecutively reset LS1B in a loop body and counting loop cycles until the bitset becomes empty. Brian Kernighan ^[10] mentioned the trick in his and Ritchie's book The C Programming_Language, 2nd Edition 1988, exercise 2-9. However, the method was first published in 1960 by Peter Wegner ^[11], discovered independently by Derrick Henry Lehmer, published in 1964 ^[12]:

int popCount (U64 x) {
   int count = 0;
   while (x) {
       count++;
       x &= x - 1; // reset LS1B
   }
   return count;
}

Despite branches - this is still one of the fastest approaches for sparsely populated bitboards. Of course the more bits that are set, the longer it takes.

Lookup

Of course we can not use the whole bitboard as index to a lookup table - since it's size would be 18,446,744,073,709,551,616 bytes! If it is about the population count of a byte, we can simply construct a table lookup with 256 elements. For a bitboard that takes eight byte lookups we can add together:

unsigned char popCountOfByte256[];
 
void initpopCountOfByte256()
{
   popCountOfByte256[0] = 0;
   for (int i = 1; i < 256; i++)
      popCountOfByte256[i] = popCountOfByte256[i / 2] + (i & 1);
}
 
int popCount (U64 x) {
   return popCountOfByte256[ x        & 0xff] +
          popCountOfByte256[(x >>  8) & 0xff] +
          popCountOfByte256[(x >> 16) & 0xff] +
          popCountOfByte256[(x >> 24) & 0xff] +
          popCountOfByte256[(x >> 32) & 0xff] +
          popCountOfByte256[(x >> 40) & 0xff] +
          popCountOfByte256[(x >> 48) & 0xff] +
          popCountOfByte256[ x >> 56];
}

Looks quite expensive - one may use four 16-bit word-lookups with a pre-calculated 64KByte table though, but that pollutes the memory caches quite a bit. One can also treat the bitboard as array of bytes or words in memory, since endian issues don't care here - that safes all the shifts and 'ands', but has to read byte for byte from memory.

int popCount (U64 x) {
   unsigned char * p = (unsigned char *) &x;
   return popCountOfByte256[p[0]] +
          popCountOfByte256[p[1]] +
          popCountOfByte256[p[2]] +
          popCountOfByte256[p[3]] +
          popCountOfByte256[p[4]] +
          popCountOfByte256[p[5]] +
          popCountOfByte256[p[6]] +
          popCountOfByte256[p[7]];
}

SWAR-Popcount

The divide and conquer SWAR-approach deals with counting bits of duos, to aggregate the duo-counts to nibbles and bytes inside one 64-bit register in parallel, to finally sum all bytes together. According to Donald Knuth ^[13], a parallel population count routine was already introduced in 1957 due to Donald B. Gillies and Jeffrey C. P. Miller in the first textbook on programming, second edition: The Preparation of Programs for an Electronic Digital Computer, by Maurice Wilkes, David Wheeler and Stanley Gill, pages 191–193 ^[14] ^[15].

Counting Duo-Bits

A bit-duo (two neighboring bits) can be interpreted with bit 0 = a, and bit 1 = b as

$duo := 2b + a$

The duo population is

$popcnt(duo) := b + a$

which can be archived by

$(2b + a) - {(2b + a)} \div {2}$

$(2b + a) - b$

The bit-duo has up to four states with population count from zero to two as demonstrated in following table with binary digits:

x	-	x div 2	→	popcnt(x)
00	-	00	→	00
01	-	00	→	01
10	-	01	→	01
11	-	01	→	10

Only the lower bit is needed from x div 2 - and one don't has to worry about borrows from neighboring duos. SWAR-wise, one needs to clear all "even" bits of the div 2 subtrahend to perform a 64-bit subtraction of all 32 duos:

x = x - ((x >> 1) & 0x5555555555555555);

Note that the popcount-result of the bit-duos still takes two bits.

Counting Nibble-Bits

The next step is to add the duo-counts to populations of four neighboring bits, the 16 nibble-counts, which may range from zero to four. SWAR-wise it is done by masking odd and even duo-counts to add them together:

 x = (x & 0x3333333333333333) + ((x >> 2) & 0x3333333333333333);

Note that the popcount-result of the nibbles takes only three bits, since 100B is the maximum population (of the nibble 1111B).

Byte-Counts

You already got the idea? Now it is about to get the byte-populations from two nibble-populations. Maximum byte-population of 1000B only takes four bits, so it is safe to mask all those four bits of the sum, rather than to mask the summands:

x = (x + (x >> 4)) & 0x0f0f0f0f0f0f0f0f;

Adding the Byte-Counts

Parallel Prefix Adds

We may continue with mask-less parallel prefix SWAR-adds for byte-counts, word-counts and finally double-word-counts, to mask the least significant 8 (or 7) bits for final result in the 0..64 range:

x += (x >>  8);
x += (x >> 16);
x += (x >> 32);
return x & 255;

Multiplication

With todays fast 64-bit multiplication one can multiply the vector of 8-byte-counts with 0x0101010101010101 to get the final result in the most significant byte, which is then shifted right:

x = (x * 0x0101010101010101) >> 56;

Casting out

Interestingly, there is another approach to add the bytes together. As demonstrated with decimal digits (base 10) and Casting out nines ^[16], casting out by modulo base minus one is equivalent to taking the digit sum, which might be applied here with low range 0..8 "base 256" digits:

x = x % 255;

However, since division and modulo are usually slow instructions and modulo by constant is likely replaced by reciprocal multiplication anyway by the compiler, the multiplication by 0x0101010101010101 aka the 2-adic fraction -1/255 is the preferred method.

The PopCount routine

The Constants

Putting all together, the various SWAR-Masks and factors as defined by Donald Knuth as 2-adic fractions ^[17]:

const U64 k1 = C64(0x5555555555555555); /*  -1/3   */
const U64 k2 = C64(0x3333333333333333); /*  -1/5   */
const U64 k4 = C64(0x0f0f0f0f0f0f0f0f); /*  -1/17  */
const U64 kf = C64(0x0101010101010101); /*  -1/255 */

represented as bitboards:

k1  -1/3            k2  -1/5            k4  -1/17           kf  -1/255              
0x5555555555555555  0x3333333333333333  0x0f0f0f0f0f0f0f0f  0x0101010101010101
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .   
1 . 1 . 1 . 1 .     1 1 . . 1 1 . .     1 1 1 1 . . . .     1 . . . . . . .

popCount

This is how the complete routine looks in C:

int popCount (U64 x) {
    x =  x       - ((x >> 1)  & k1); /* put count of each 2 bits into those 2 bits */
    x = (x & k2) + ((x >> 2)  & k2); /* put count of each 4 bits into those 4 bits */
    x = (x       +  (x >> 4)) & k4 ; /* put count of each 8 bits into those 8 bits */
    x = (x * kf) >> 56; /* returns 8 most significant bits of x + (x<<8) + (x<<16) + (x<<24) + ...  */
    return (int) x;
}

Advantage: no branches, no memory lookups, constant runtime - independent from population
Drawback: dependency chain, not much parallel speedup

slowmul_popCount

And as stated before, for computers with relatively slower multiplication, the addition can be done manually:

int slowmul_popCount (U64 x) {
    x =  x       - ((x >> 1)  & k1); /* put count of each 2 bits into those 2 bits */
    x = (x & k2) + ((x >> 2)  & k2); /* put count of each 4 bits into those 4 bits */
    x = (x       +  (x >> 4)) & k4 ; /* put count of each 8 bits into those 8 bits */
    x += x >>  8;  /* put count of each 16 bits into their lowest 8 bits */
    x += x >> 16;  /* put count of each 32 bits into their lowest 8 bits */
    x += x >> 32;  /* put count of the final 64 bits into the lowest 8 bits */
    return (int) x & 255;
}

For likely sparsely populated bitboards, the loop-wise Brian Kernighan's way might be the faster one.

HAKMEM 169

A similar technique was proposed by Bill Gosper et al. from Massachusetts Institute of Technology, as published 1972 in Memo 239 (HAKMEM) ^[18] ^[19], 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 octal (base-8) digits, originally written in Assembly for the PDP-6 ^[20]. An expanded 64-bit version, casting out 511 or 4095, is slightly less efficient than the binary SWAR version above.

int hakmem169_32(unsigned int x) {
   x = x  - ((x >> 1)  & 033333333333)
          - ((x >> 2)  & 011111111111);
   x = (x +  (x >> 3)) & 030707070707 ;
   return x % 63; /* casting out 63 */
}

Miscellaneous

Cardinality of Multiple Sets

If we like to count arrays of sets, we can reduce 2^N-1 popcounts to N popcounts, by applying the odd-major-trick. For three sets to count we safe one, with five additional cheap instructions.

  odd   =  (x ^ y)  ^ z;
  major = ((x ^ y ) & z) | (x & y);
 
  popCount(x) + popCount(y) + popCount(z) == 2*popCount(major) + popCount(odd)

The combined popCount3 likely gains more parallel speedup, since there are two independent chains to calculate. Possible Application is to pass the union of both bishops (since usually bishops cover disjoint sets due to different square colors) plus the up to two knight move-target sets.

// return popCount(x) + popCount(y) + popCount(z)
int popCount3 (U64 x, U64 y, U64 z) {
    U64 maj = ((x ^ y ) & z) | (x & y);
    U64 odd = ((x ^ y ) ^ z);
    maj =  maj - ((maj >> 1) & k1 );
    odd =  odd - ((odd >> 1) & k1 );
    maj = (maj & k2) + ((maj >> 2) & k2);
    odd = (odd & k2) + ((odd >> 2) & k2);
    maj = (maj + (maj >> 4)) & k4;
    odd = (odd + (odd >> 4)) & k4;
    odd = ((maj + maj + odd) * kf ) >> 56;
    return (int) odd;
}

Odd and Major 7-15

Of course - reducing seven popcount to three, or even 15 popcounts to four sounds even more promising.
For N = 2^n - 1 it takes N - n odd-major pairs. Thus one add-major pair - five instructions - per saved popCount.

That is 7 - 3 = 4 pairs:

one1,two1 := oddMaj(x1,x2,x3)
one2,two2 := oddMaj(x4,x5,x6)
ones,two3 := oddMaj(x7,one1,one2)
twos,four := oddMaj(two1,two2,two3)

Or 15 - 4 = 11 pairs:

one1,two1  := oddMaj(x1,x2,x3)
one2,two2  := oddMaj(x4,x5,x6)
one3,two3  := oddMaj(x7,x8,x9)
one4,two4  := oddMaj(x10,x11,x12)
one5,two5  := oddMaj(x13,x14,x15)
one6,two6  := oddMaj(one1,one2,one3)
ones,two7  := oddMaj(one4,one5,one6)
two8,four1 := oddMaj(two1,two2,two3)
two9,four2 := oddMaj(two4,two5,two6)
twos,four3 := oddMaj(two7,two8,two9)
four,eight := oddMaj(four1,four2,four3)

Odd and Major Digit Counts

Odd-Major is probably also useful to determine digit count sets of attacks or other stuff:

U64 odd(U64 x, U64 y, U64 z) {return x^y^z;}
U64 maj(U64 x, U64 y, U64 z) {return ((x^y)&z)|(x&y);}
 
void attackCounts(U64 t[3], const U64 s[7]) {
   one1 = odd(s[0], s[1], s[2]);
   two1 = maj(s[0], s[1], s[2]);
   one2 = odd(s[3], s[4], s[5]);
   two2 = maj(s[3], s[4], s[5]);
   t[0] = odd(s[6], one1, one2);
   two3 = maj(s[6], one1, one2);
   t[1] = odd(two1, two2, two3);
   t[2] = maj(two1, two2, two3);
}

with following semantics:

exactly7attacks :=   t[2] &  t[1] &  t[0]
exactly6attacks :=   t[2] &  t[1] & ~t[0]
exactly5attacks :=   t[2] & ~t[1] &  t[0]
exactly4attacks :=   t[2] & ~t[1] & ~t[0]
exactly3attacks :=  ~t[2] &  t[1] &  t[0]
exactly2attacks :=  ~t[2] &  t[1] & ~t[0]
exactly1attack  :=  ~t[2] & ~t[1] &  t[0]
noAttack        :=  ~t[2] & ~t[1] & ~t[0]
 
atLeast4attacks :=                   t[2]
atLeast2attacks := atLeast4attacks | t[1]
atLeast1attack  := atLeast2attacks | t[0]
noAttack        := ~atLeast1attack
exactly1attack  :=  atLeast1attack  ^ atLeast2attacks

Popcount as log2 of LS1B

Assuming an architecture has a fast popcount-instruction (but no bitscan). One can isolate the LS1B, decrement it and count the remaining trailing "ones" to perform the logarithm dualis:

log2(LS1B) = popCount( LS1B - 1 );
bitIndexOfLS1B(x) = popCount( (x & -x) - 1 );

For instance, LS1B is 2^44, decrementing leaves a below LSB1 mask with exactly 44 bits set:

0x0000100000000000   0x00000FFFFFFFFFFF
. . . . . . . .      . . . . . . . .
. . . . . . . .      . . . . . . . .
. . . . 1 . . .      1 1 1 1 . . . .
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1
. . . . . . . .      1 1 1 1 1 1 1 1

Hamming Distance

The hamming distance of two words is defined as the number of corresponding different bits.

int hammingDistance (U64 a, U64 b) {return popcnt( a ^ b);}

Hamming distance greater than one or two is an important property of codes to detect or even correct one-bit errors.

The minimum and average hamming distance over all Zobrist keys was considered as "quality"-measure of the keys. However, as long the minimum hamming distance is greater zero, linear independence (that is a small subset of all keys doesn't xor to zero), is much more important than hamming distance ^[21]. Maximizing the minimal hamming distance leads to very poor Zobrist keys ^[22].

Weighted PopCount

For a SIMD-wise kind of weighted population count, see the SSE2 dot-product.

Pre-calculated Mobility

Similar to Attacks by Occupancy Lookup to determine attack sets of sliding pieces, we may use pre-calculated population count or even center-weighted population count as a rough estimate on piece mobility ^[23]. It may not consider subsets of let say safe target squares.

Piece Attacks Count

As pointed out by Marco Costalba ^[24] ^[25], specialized routines to count the population (Mobility) of attack sets of king, knight and line-wise sub-sets of sliding pieces can be done more efficiently than the general SWAR-Popcount. This is similar to Flipping Mirroring and Rotating the whole bitboard versus Rank, File and Diagonal, and is based on mapping the up to eight scattered occupied bits to one byte, to perform a single byte lookup. For various mapping techniques, see:

Popcount in Hardware

Publications

1949 ...

Alan Turing (1949). Alan Turing's Manual for the Ferranti Mk. I. transcribed in 2000 by Robert Thau, pdf from The Computer History Museum, 9.4 The position of the most significant digit » Ferranti Mark 1
Maurice Wilkes, David Wheeler, Stanley Gill (1957). The Preparation of Programs for an Electronic Digital Computer. Addison-Wesley Press; 2nd edition, amazon.com, Donald B. Gillies and Jeffrey C. P. Miller on SWAR-Popcount, pages 191–193
Peter Wegner (1960). A technique for counting ones in a binary computer. Communications of the ACM, Volume 3, 1960
David A. Wagner, Steven M. Bellovin (1994). A Programmable Plaintext Recognizer. ^[26]

2000 ...

Simon Y. Berkovich, Gennadi M. Lapir, Marilyn Mack (2000). A Bit-Counting Algorithm Using the Frequency Division Principle. Software, Practice and Experience Vol. 30, No. 14, 2000, pp. 1531-1540
Eyas El-Qawasmeh (2001). Beating the Popcount. International Journal of Information Technology, Singapore, Vol. 9. No. 1
Henry S. Warren, Jr. (2002). Hacker's Delight. Addison-Wesley Professional
Eyas El-Qawasmeh, Wafa'a Al-Qarqaz (2006). Reducing Lookup Table Size used for Bit-Counting Algorithm. Computer Science Dept. Jordan University of Science and Technology, pdf
Henry S. Warren, Jr. (2007). The Quest for an Accelerared Population Count. in Andy Oram & Greg Wilson (eds.) (2007). Beautiful code: Leading Programmers Explain How They Think. O'Reilly, amazon.com
Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, Sideways addition, pp 11

2010 ...

Henry S. Warren, Jr. (2012). Hacker's Delight, 2nd Edition. Addison-Wesley Professional, More coverage of population count and counting leading zeros, Array population count
Andreas Stiller (2013). Spezialkommando - Intrinsic __popcnt() zählt die Einsen. c't Magazin für Computertechnik 5/2013, p. 180 (German)
Wojciech Muła, Nathan Kurz, Daniel Lemire (2016). Faster Population Counts Using AVX2 Instructions. arXiv:1611.07612 ^[27] » AVX2, AVX-512

Postings

1998 ...

Bean counters Part1 by Peter Fendrich, CCC, August 19, 1998
Bean counters Part2 by Peter Fendrich, CCC, August 19, 1998
Countbits() Function by Roberto Waldteufel, CCC, January 03, 1999
Sideways Add / Population Count by Jitze Couperus, Steve Bellovin and Axel H. Horns, cryptography@c2.net, January 28, 1999 » CDC 6600 ^[28]

2000 ...

fast bit counting by Flemming Rodler, CCC, April 19, 2000
Bit counting revisited by Flemming Rodler, CCC, April 19, 2000
PowerPC BitCounting Functions Speed by William Bryant, CCC, April 20, 2000 » PowerPC
Counting the number of bits in a 32-bit word by George Marsaglia, comp.lang.c, December 7, 2000
Re: Chezzz 1.0.1 - problem solved - for David Rasmussen by David Rasmussen, CCC, February 05, 2003 ^[29]
Counting bits by Andreas Herrmann, CCC, April 17, 2003
Hamming distance and lower hash table indexing by Tom Likens, CCC, September 02, 2003
PopCount optimization by milix, CCC, March 11, 2004

2005 ...

Population count in SSE2, again by James Van Buskirk, comp.lang.asm.x86, April 12, 2008
core2 popcnt by Frank Phillips, CCC, February 13, 2009
Piece attacks count by Marco Costalba, CCC, May 18, 2009 » Attack and Defend Maps
Bit twiddlement question: greater of two popcounts by Zach Wegner, CCC, August 06, 2009

2010 ...

Stockfish POPCNT support with gcc by Marco Costalba, CCC, January 31, 2010
Yet another handmade POPCNT by hopcode, comp.lang.asm.x86, January 05, 2011
A brief history of the popcnt instruction by Steven Edwards, CCC, March 22, 2011
Introduction and (hopefully) contribution - bitboard methods by Alcides Schulz, CCC, June 03, 2011 » BitScan
using Popcount and Prefetch with SSE4 hardware support by Engin Üstün, CCC, May 19, 2012 » Memory, SSE4
64 bits for 64 squares ? by Thomas Petzke, mACE Chess, April 28, 2013
Stockfish 32-bit and hardware instructions on MSVC++ by Syed Fahad, CCC, December 30, 2014 » Stockfish, BitScan, Population Count

2015 ...

Re: Linux Version of Maverick 1.5 by Michael Dvorkin, CCC, November 12, 2015 » OS X, Maverick
syzygy users (and Ronald) by Robert Hyatt, CCC, September 29, 2016 » BitScan

External Links

Hamming weight from Wikipedia
Population count (POPCNT) - CompArch
Crazy On Tap - Secret Opcodes ^[30]
Blender: POPCNT for counting bits
HAKMEM - ITEM 169 To count the ones in a PDP-6/10 word (in order of one-ups-manship: Gosper, Mann, Lenard, [Root and Mann]) ^[31]
HAKMEMC -- HAKMEM Programming hacks in C by Alan Mycroft
popcount C samples from Henry S. Warren, Jr. (2002, 2012). Hacker's Delight. Addison-Wesley
The Aggregate Magic Algorithms -Population Count (Ones Count) by Hank Dietz
Counting bits set from Bit Twiddling Hacks by Sean Eron Anderson
Optimising Bit Counting using Iterative, Data-Driven Development from Necessary and Sufficient by Damien Wintour
Count bits set in parallel a.k.a. Population Count from the bit twiddler by Stephan Brumme
Benchmarking CRC32 and PopCnt instructions - strchr.com by Peter Kankowski
SSSE3: fast popcount by Wojciech Muła, May 24, 2008 » SSSE3
Speeding up bit-parallel population count by Wojciech Muła, April 13, 2015
Population count using XOP instructions by Wojciech Muła, December 16, 2016 » XOP
GitHub - WojciechMula/sse-popcount: SIMD (SSE) population count by Wojciech Muła
GitHub - kimwalisch/libpopcnt: Fast C/C++ bit population count library » libpopcnt by Kim Walisch
Census from Wikipedia
John Abercrombie 4tet - One, one, one + Spring song, Subway, Cologne, April 12, 1999, 3sat broadcast ^[32], YouTube Video
John Abercrombie, Bobo Stenson, Lars Danielsson, Jon Christensen

References

^ Cryptography is also a significant application of the /R function symbol, which counts the number of one bits in a word; Turing refers to this as the "sideways adder" in his quick-reference summary. from Alan Turing (1949). Alan Turing's Manual for the Ferranti Mk. I. transcribed in 2000 by Robert Thau, pdf from The Computer History Museum, 9.4 The position of the most significant digit » Ferranti Mark 1
^ Extending the World’s Most Popular Processor Architecture by R.M. Ramanathan, Intel, covers SSE4 and popcnt
^ _mm_popcnt_u64
^ _popcnt16, _popcnt, _popcnt64 C-Intrinsic MSDN Library
^ Miscellaneous Intrinsic
^ __builtin_popcountll GCC Intrinsic
^ Stockfish POPCNT support with gcc by Marco Costalba, CCC, January 31, 2010
^ Color of each pixel is Hamming distance between the binary representations of its x and y coordinates, modulo 16, in the 16-color system, by Josiedraus, June 8, 2007, Richard Hamming from Wikipedia
^ Matters Computational - ideas, algorithms, source code (pdf) Ideas and Source Code by Jörg Arndt, 1.7 Functions related to the base-2 logarithm, function one_bit_q(), pp 18
^ Counting bits set, Brian Kernighan's way from Bit Twiddling Hacks by Sean Eron Anderson
^ Peter Wegner (1960). A technique for counting ones in a binary computer. Communications of the ACM, Volume 3, 1960
^ Edwin Ford Beckenbach (editor) (1964). Applied combinatorial mathematics, John Wiley
^ Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, Sideways addition, p 11
^ Maurice Wilkes, David Wheeler, Stanley Gill (1951). The Preparation of Programs for an Electronic Digital Computer. Addison-Wesley Press; 1st edition, amazon.com; 2nd edition 1957, amazon.com
^ Electronic Delay Storage Automatic Calculator from Wikipedia
^ Casting Out Nines by Bill the Lizard, June 13, 2009
^ Donald Knuth (2009). The Art of Computer Programming, Volume 4, Fascicle 1: Bitwise tricks & techniques, as Pre-Fascicle 1a postscript, p 9
^ HAKMEM - ITEM 169 To count the ones in a PDP-6/10 word (in order of one-ups-manship: Gosper, Mann, Lenard, [Root and Mann])
^ HAKMEMC -- HAKMEM Programming hacks in C by Alan Mycroft
^ HAKMEM 169 for PDP-6/PDP-10 36-bit words
^ Re: About random numbers and hashing by Sven Reichard, CCC, December 05, 2001
^ Zobrist key random numbers by Robert Hyatt from CCC, January 21, 2009
^ Magic and precomputation by Onno Garms from Winboard Programming Forum, September 23, 2007
^ fast mobility count through hashing by Marco Costalba from CCC, May 09, 2009
^ Piece attacks count by Marco Costalba from CCC, May 18, 2009
^ Sideways Add / Population Count by Jitze Couperus and Steve Bellovin et al., cryptography@c2.net, January 28, 1999
^ sse-popcount/popcnt-avx512-harley-seal.cpp at master · WojciechMula/sse-popcount · GitHub
^ David A. Wagner, Steven M. Bellovin (1994). A Programmable Plaintext Recognizer.
^ AMD Athlon Processor x86 Code Optimization Guide (pdf) Efficient 64-Bit Population Count Using MMX™ Instructions Page 184
^ National Security Agency from Wikipedia
^ Michael Beeler, Bill Gosper and Rich Schroeppel (1972). HAKMEM, Memo 239, Artificial Intelligence Laboratory, Massachusetts Institute of Technology, made Web-available by Henry Baker
^ Ali Haurand from Wikipedia.de (German)

What links here?

Page	Date Edited
Alcides Schulz	Mar 29, 2018
Algorithms	May 5, 2017
Amundsen	Sep 3, 2013
Anastasios Milikas	Nov 29, 2017
Andreas Herrmann	Nov 7, 2014
Assembly	Sep 3, 2017
Asterisk	Mar 24, 2016
Attack and Defend Maps	Nov 5, 2016
AVX-512	Aug 8, 2017
AVX2	Aug 8, 2017
Beaches	Jun 10, 2017
Best Magics so far	Apr 13, 2018
Bill Gosper	Aug 20, 2014
Bison	Sep 29, 2016
Bit-Twiddling	Nov 6, 2017
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
BitScan	Sep 10, 2017
BlackMamba	Nov 26, 2016
Blockage Detection	Oct 19, 2017
Bobcat	Jun 27, 2017
Bouquet	May 17, 2016
Brainless	Jun 24, 2017
Cassandre	Jul 5, 2013
CDC 6600	Oct 8, 2014
CDC Cyber	Dec 22, 2017
Cheng	Jul 30, 2017
Chess 0.5	Nov 20, 2016
Chezzz	Jan 20, 2013
Congruent Modulo Bitboards	Jun 26, 2013
CookieCat	Nov 15, 2016
Cray-1	Dec 25, 2017
David Rasmussen	Dec 16, 2017
DEC Alpha	Aug 15, 2015
DirGolem	Jun 5, 2016
Dispersion and Distortion	Nov 11, 2017
Djinn	Feb 8, 2016
Double and Triple (Bitboards)	May 12, 2016
Engin Üstün	Jan 21, 2018
Ferranti Mark 1	Jun 2, 2015
Fizbo	Dec 22, 2017
Frank Phillips	Sep 26, 2016
General Setwise Operations	Feb 25, 2018
Georg von Zimmermann	May 29, 2017
Gk	Oct 9, 2017
Hakkapeliitta	Apr 26, 2016
HeavyChess	Feb 14, 2014
Henry S. Warren, Jr.	Oct 14, 2016
Ifrit	Feb 7, 2016
Itanium	Aug 29, 2015
Joker IT	Sep 16, 2017
Kim Walisch	Aug 10, 2017
Leila	May 8, 2017
Little Wing	Oct 26, 2017
Mac OS	Mar 25, 2016
Marco Costalba	Feb 28, 2018
Material Tables	May 5, 2017
Mathematician	Apr 9, 2018
Michael Dvorkin	Jan 8, 2016
Mikhail R. Shura-Bura	Oct 30, 2013
MMX	Jun 5, 2016
Mobility	Jan 17, 2018
Nebula	Feb 7, 2015
Nibble	Jan 25, 2015
Paladin	Jan 29, 2017
Parallel Prefix Algorithms	Jun 22, 2016
Pawn Islands (Bitboards)	May 4, 2017
PDP-10	Apr 20, 2018
PDP-6	Jan 19, 2018
Peter Fendrich	May 19, 2017
Population Count	Sep 3, 2017
PowerPC	Oct 6, 2017
Prophet	Sep 30, 2017
Recursion	Nov 18, 2017
RedQueen	Nov 13, 2017
Robert Hyatt	Dec 25, 2017
Robocide	May 11, 2016
Senpai	Nov 10, 2017
SIMD and SWAR Techniques	Jun 27, 2017
Simona Tancig	Nov 7, 2012
Space-Time Tradeoff	Jun 17, 2015
Spector	Nov 11, 2016
SSE2	Feb 27, 2018
SSE4	Jun 5, 2016
SSSE3	Aug 8, 2017
Steven Edwards	Aug 26, 2017
Steven M. Bellovin	Dec 14, 2017
Stockfish	Apr 7, 2018
Sungorus	Apr 11, 2014
Syed Fahad	Jan 1, 2017
Texel	Oct 9, 2017
Tornado	Dec 14, 2017
Transposition Table	Apr 19, 2018
Tucano	Dec 16, 2017
Vadim Demichev	Jul 26, 2013
Vice	Mar 8, 2016
Warrior	Feb 23, 2015
Wasp	Nov 24, 2017
Wojciech Muła	Aug 10, 2017
x86-64	Mar 6, 2018
x86-64 Instructions to Include	Feb 12, 2011
Zobrist Hashing	Jan 22, 2018

Up one Level

Quad Word

GerdIsenberg — Sun, 25 Jan 2015 22:19:50 GMT

Home * Programming * Data * Quad Word

According to Intel's definition of a x86 16-bit Word, a Quad Word refers a 64-bit word.

long long or long

Microsoft 64-bit C-compiler long is still 32-bit Double Word, while 64-bit GCC uses 64-bit Quad Words as longs. Other compiler require "long long" for 64-bit types.

typedef unsigned long QWORD;
typedef unsigned long long QWORD;

Bitboards

Quad words are used as bitboard datatype:

typedef QWORD U64;
typedef QWORD Bitboard;

Ranges

type	language	min	max
unsigned long long	C, C++	0	18,446,744,073,709,551,615
hexadecimal		0x0000000000000000	0xFFFFFFFFFFFFFFFF
long long	C, C++, Java	-9,223,372,036,854,775,808	9,223,372,036,854,775,807
hexadecimal		0x8000000000000000	0x7FFFFFFFFFFFFFFF

Alignment

Quad Words stored in memory should be stored at byte addresses divisible by eight. Otherwise at runtime it will cause a miss-alignment exception on some processors, or a huge penalty on others.

Endianness

Main article: Endianness.

Litte-endian layout

The little-endian memory layout, as typical for Intel cpus.
For instance the quad word integer 0x0102030405060708

Address	Byte	Significance
0x0000	0x08	LS Byte
0x0001	0x07
0x0002	0x06
0x0003	0x05
0x0004	0x04
0x0005	0x03
0x0006	0x02
0x0008	0x01	MS Byte

Big-endian layout

The big-endian memory layout, as typical for Motorola cpus.
For instance the quad word integer 0x0102030405060708

Address	Byte	Significance
0x0000	0x01	MS Byte
0x0001	0x02
0x0002	0x03
0x0003	0x04
0x0004	0x05
0x0005	0x06
0x0006	0x07
0x0007	0x08	LS Byte

External Links

What links here?

Page	Date Edited
AVX-512	Aug 8, 2017
AVX2	Aug 8, 2017
Big-endian	Jan 25, 2015
Bit	Oct 29, 2012
Bitboard Serialization	Dec 24, 2014
Bitboards	Nov 14, 2017
Byte	Apr 5, 2013
Data	Nov 26, 2017
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Double	May 30, 2016
Double Word	Jan 25, 2015
General Setwise Operations	Feb 25, 2018
King Pattern	Nov 15, 2013
Little-endian	Jan 25, 2015
MMX	Jun 5, 2016
Quad Word	Jan 25, 2015
Shared Hash Table	Sep 11, 2017
SIMD and SWAR Techniques	Jun 27, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE4	Jun 5, 2016
Transposition Table	Apr 19, 2018
Tucano	Dec 16, 2017
Word	Jan 25, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

SSE2

GerdIsenberg — Tue, 27 Feb 2018 10:33:25 GMT

SSE2 Population Count

Home * Hardware * x86 * SSE2

SSE2 (Streaming SIMD Extensions 2) and further x86- or x86-64 streaming SIMD extensions, like SSE3, SSSE3, SSE4 and AMD's announced SSE5, as major enhancement to SSE, provide an instruction set on 128-bit registers, namely on vectors of four floats or two doubles, as well since SSE2 as vectors of 16 bytes, eight words, four double words or two quad words ^[1] . In 64-bit mode there are 16 xmm registers available, xmm0..xmm15, in 32-bit mode only eight, xmm0..xmm7. SSE is explicitly available through C-Compiler intrinsics ^[2] or (inline) assembly. Some compiler implicitly use SSE-float and double instructions for floating point data types, others even provide automatic SSE2 vectorization, while processing arrays of various integer types. SSE- and SSE2-intrinsic functions are available in Visual C ^[3] or Intel-C ^[4] ^[5].

Integer Instructions

x86 and x86-64 - SSE2 C-integer intrinsic reference from MSDN Library, the intrinsic data type _m128i refers a xmm-register or memory location:

Mnemonic	Description		C-Intrinsic
bitwise logical		return		parameter
pand	packed and, r := a & b	_m128i	_mm_and_si128	(_m128i a, _m128i b)
pandn	packed and not, r := ~a & b	_m128i	_mm_andnot_si128	(_m128i a, _m128i b)
por	packed or, r := a \| b	_m128i	_mm_or_si128	(_m128i a, _m128i b)
pxor	packed xor, r:= a ^ b	_m128i	_mm_xor_si128	(_m128i a, _m128i b)
quad word shifts
psrlq	packed shift right logical quad	_m128i	_mm_srl_epi64	(_m128i a, _m128i cnt)
	immediate	_m128i	_mm_srli_epi64	(_m128i a, int cnt)
psllq	packed shift left logical quad	_m128i	_mm_sll_epi64	(_m128i a, _m128i cnt)
	immediate	_m128i	_mm_slli_epi64	(_m128i a, int cnt)
arithmetical
paddb	packed add bytes	_m128i	_mm_add_epi8	(_m128i a, _m128i b)
psubb	packed subtract bytes	_m128i	_mm_sub_epi8	(_m128i a, _m128i b)
psadbw	packed sum of absolute differences of bytes into a word	_m128i	_mm_sad_epu8	(_m128i a, _m128i b)
pmaxsw	packed maximum signed words	_m128i	_mm_max_epi16	(_m128i a, _m128i b)
pmaxub	packed maximum unsigned bytes	_m128i	_mm_max_epu8	(_m128i a, _m128i b)
pminsw	packed minimum signed words	_m128i	_mm_min_epi16	(_m128i a, _m128i b)
pminub	packed minimum unsigned bytes	_m128i	_mm_min_epu8	(_m128i a, _m128i b)
pcmpeqb	packed compare equal bytes	_m128i	_mm_cmpeq_epi8	(_m128i a, _m128i b)
pmullw	packed multiply mow signed (unsigned) word	_m128i	_mm_mullo_epi16	(_m128i a, _m128i b)
pmulhw	packed multiply high signed word	_m128i	_mm_mulhi_epi16	(_m128i a, _m128i b)
pmulhuw	packed multiply high unsigned word	_m128i	_mm_mulhi_epu16	(_m128i a, _m128i b)
pmaddwd	packed multiply words and add doublewords	_m128	_mm_madd_epi16	(_m128i a, _m128i b)
unpack, shuffle
punpcklbw	unpack and interleave low bytes `gGhHfFeE:dDcCbBaA :=` `xxxxxxxx:GHFEDCBA #` `xxxxxxxx:ghfedcba`	_m128i	_mm_unpacklo_epi8	(_m128i A, _m128i a)
punpckhbw	unpack and interleave high bytes `gGhHfFeE:dDcCbBaA :=` `GHFEDCBA:xxxxxxxx #` `ghfedcba:xxxxxxxx`	_m128i	_mm_unpackhi_epi8	(_m128i A, _m128i a)
punpcklwd	unpack and interleave low words `dDcC:bBaA := xxxx:DCBA#xxxx:dcba`	_m128i	_mm_unpacklo_epi16	(_m128i A, _m128i a)
punpckhwd	unpack and interleave high words `dDcC:bBaA := DCBA:xxxx#dcba:xxxx`	_m128i	_mm_unpackhi_epi16	(_m128i A, _m128i a)
punpckldq	unpack and interleave low doublewords `bB:aA := xx:BA # xx:ba`	_m128i	_mm_unpacklo_epi32	(_m128i A, _m128i a)
punpckhdq	unpack and interleave high doublewords `bB:aA := BA:xx # ba:xx`	_m128i	_mm_unpackhi_epi32	(_m128i A, _m128i a)
punpcklqdq	unpack and interleave low quadwords `a:A := x:A # x:a`	_m128i	_mm_unpacklo_epi64	(_m128i A, _m128i a)
punpckhqdq	unpack and interleave high quadwords `a:A := A:x # a:x`	_m128i	_mm_unpackhi_epi64	(_m128i A, _m128i a)
pshuflw	packed shuffle low words	_m128i	_mm_shufflelo_epi16	(_m128i a, int imm)
pshufhw	packed shuffle high words	_m128i	_mm_shufflehi_epi16	(_m128i a, int imm)
pshufd	packed shuffle doublewords	_m128i	_mm_shuffle_epi32	(_m128i a, int imm)
load, store, moves
movdqa	move aligned double quadword xmm := *p	_m128i	_mm_load_si128	(_m128i *p)
movdqu	move unaligned double quadword xmm := *p	_m128i	_mm_loadu_si128	(_m128i *p)
movdqa	move aligned double quadword *p := xmm	void	_mm_store_si128	(_m128i *p, _m128i a)
movdqu	move unaligned double quadword *p := xmm	void	_mm_storeu_si128	(_m128i *p, _m128i a)
movq	move quadword, xmm := gp64	_m128i	_mm_cvtsi64_si128	(_int64 a)
movq	move quadword, gp64 := xmm	_int64	_mm_cvtsi128_si64	(_m128i a)
movd	move double word or quadword xmm := gp64	_m128i	_mm_cvtsi64x_si128	(_int64 value)
movd	move doubleword, xmm := gp32	_m128i	_mm_cvtsi32_si128	(int a)
movd	move doubleword, gp32 := xmm	int	_mm_cvtsi128_si32	(_m128i a)
pextrw	extract packed word, gp16 := xmm[i]	int	_mm_extract_epi16	(_m128i a, int imm)
pinsrw	packed insert word, xmm[i] := gp16	_m128i	_mm_insert_epi16	(_m128i a, int b, int imm)
pmovmskb	packed move mask byte, gp32 := 16 sign-bits(xmm)	int	_mm_movemask_epi	(_m128i a)
cache support
prefetch		void	_mm_prefetch	(char * p , int i )

Applications

Some vc2005 tested, sample SSE2 bitboard routines:

One Step Only

Since 128-bit xmm registers may treated as vector of 16 bytes, shifting techniques such as one step in all eight directions can be done more efficiently with respect to wraps from a- to the h-file or vice versa. It is recommend to write a own SSE2-wrapper class with overloaded operators in C++ to encapsulate a vector of two bitboards.

  northwest    north   northeast
  noWe         nort         noEa
          +7    +8    +9
              \  |  /
  west    -1 <-  0 -> +1    east
              /  |  \
          -9    -8    -7
  soWe         sout         soEa
  southwest    south   southeast

Veritcal steps as usual with 64-byte shift a rank each:

__m128i nortOne(__m128i b) {
   b = _mm_slli_epi64 (b, 8);
   return b;
}
 
__m128i soutOne(__m128i b) {
   b = _mm_srli_epi64 (b, 8);
   return b;
}

Unfortunately there is no byte-wise shift in the SSE2-instruction set (as well as MMX), but using byte-wise parallel add avoids using the wrap masks, which need otherwise load from memory or computed. Applying the wraps mask takes two instructions.

__m128i butNotA(__m128i b) {
   b = _mm_srli_epi64 (b, 1);
   b = _mm_add_epi8   (b, b);
   return b;
}
 
__m128i butNotH(__m128i b) {
   b = _mm_add_epi8   (b, b);
   b = _mm_srli_epi64 (b, 1);
   return b;
}

This is how the east direction are computed based on parallel byte-wise add. Either one or two SSE2-instructions:

__m128i eastOne(__m128i b) {
   b = _mm_add_epi8   (b, b);
   return b;
}
 
__m128i noEaOne (__m128i b) {
   b = _mm_add_epi8   (b, b);
   b = _mm_slli_epi64 (b, 8);
   return b;
}
 
__m128i soEaOne (__m128i b) {
   b = _mm_add_epi8   (b, b);
   b = _mm_srli_epi64 (b, 8);
   return b;
}

West directions need a leading not A-file and take three instructions each:

__m128i westOne(__m128i b) {
   b = _mm_srli_epi64 (b, 1);
   b = _mm_add_epi8   (b, b);
   b = _mm_srli_epi64 (b, 1);
   return b;
}
 
__m128i soWeOne (__m128i b) {
   b = _mm_srli_epi64 (b, 1);
   b = _mm_add_epi8   (b, b);
   b = _mm_srli_epi64 (b, 9);
   return b;
}
 
__m128i noWeOne (__m128i b) {
   b = _mm_srli_epi64 (b, 1);
   b = _mm_add_epi8   (b, b);
   b = _mm_slli_epi64 (b, 7);
   return b;
}

East Attacks

SIMD-wise Fill by Subtraction with byte- or rank-wise arithmetic takes only a few instructions with SSE2:

__m128i eastAttacks (__m128i occ, __m128i rooks) {
   __m128i tmp;
   occ  = _mm_or_si128 (occ, rooks);  //  make rooks member of occupied
   tmp  = _mm_xor_si128(occ, rooks);  // occ - rooks
   tmp  = _mm_sub_epi8 (tmp, rooks);  // occ - 2*rooks
   return _mm_xor_si128(occ, tmp);    // occ ^ (occ - 2*rooks)
}

SSE2 dot product

The dot product ^[6] of a vector of bits by a weight vector of bytes might be used in determining mobility for evaluation purposes. The vector of bits is a bitboard of all squares attacked by one (or multiple) piece(s), while the the weight vector considers the "importance" of squares, like center control, or even square controls near the opponent king, e.g. by providing 64 weight vectors for each king square.

$\mathbf{bb}\cdot \mathbf{weights} = \sum_{i=1}^{64} bb_iweights_i = bb_1weights_1 + \cdots + bb_{64}weights_{64}$

The 64-bit times 64-byte dot product implements a kind of weighted population count similar than following loop approach, but completely unrolled and branchless:

int dotProduct(U64 bb, BYTE weights[])
{
   U64 bit  = 1;
   int accu = 0;
   for (int sq=0; sq < 64; sq++, bit += bit) {
      if ( bb & bit) accu += weights[sq];
      // accu += weights[sq] & -((  bb & bit) == bit); // branchless 1
      // accu += weights[sq] & -(( ~bb & bit) == 0);   // branchless 2
   }
   return accu;
}

The SSE2 routine expands a bitboard as a vector of 64 bits into 64-bytes inside four 128-bit xmm registers, and performs the multiplication with the byte-vector by bitwise 'and', before it finally adds all bytes together. The bitboard is therefor manifolded eight times with a sequence of seven unpack and interleave instructions to remain the same expanded byte-order of the bits from the bitboards, before to mask and compare them with a vector of bytes with one appropriate bit set each.

The dot product is designed for unsigned weights in the 0..63 range, so that vertical bytewise adds of the four weights can not overflow. Nevertheless, three PADDUSB - packed add unsigned byte with saturation instructions (_mm_adds_epu8) are used to limit the maximum four byte sum to 255 to make the routine more "robust" for cases with average weights greater than 63. The horizontal add of both quad words of the 128-bit xmmregister is performed by the PSADBW - packed sum of absolute differences of bytes into a word instruction (_mm_sad_epu8) with zero, while the final add of the two resulting word sums in the high and low quad word of the xmm register is done with general purpose registers.

#include <emmintrin.h>
#define XMM_ALIGN __declspec(align(16))
 
/* for average weights < 64 */
int dotProduct64(U64 bb, BYTE weights[] /* XMM_ALIGN */)
{
   static const U64 XMM_ALIGN sbitmask[2] = {
     C64(0x8040201008040201),
     C64(0x8040201008040201)
   };
   __m128i x0, x1, x2, x3, bm;
   __m128i* pW = (__m128i*) weights;
   bm = _mm_load_si128 ( (__m128i*) sbitmask);
   x0 = _mm_cvtsi64x_si128(bb);        // 0000000000000000:8040201008040201
   // extend bits to bytes
   x0 = _mm_unpacklo_epi8  (x0, x0);   // 8080404020201010:0808040402020101
   x2 = _mm_unpackhi_epi16 (x0, x0);   // 8080808040404040:2020202010101010
   x0 = _mm_unpacklo_epi16 (x0, x0);   // 0808080804040404:0202020201010101
   x1 = _mm_unpackhi_epi32 (x0, x0);   // 0808080808080808:0404040404040404
   x0 = _mm_unpacklo_epi32 (x0, x0);   // 0202020202020202:0101010101010101
   x3 = _mm_unpackhi_epi32 (x2, x2);   // 8080808080808080:4040404040404040
   x2 = _mm_unpacklo_epi32 (x2, x2);   // 2020202020202020:1010101010101010
   x0 = _mm_and_si128      (x0, bm);
   x1 = _mm_and_si128      (x1, bm);
   x2 = _mm_and_si128      (x2, bm);
   x3 = _mm_and_si128      (x3, bm);
   x0 = _mm_cmpeq_epi8     (x0, bm);
   x1 = _mm_cmpeq_epi8     (x1, bm);
   x2 = _mm_cmpeq_epi8     (x2, bm);
   x3 = _mm_cmpeq_epi8     (x3, bm);
   // multiply by "and" with -1 or 0
   x0 = _mm_and_si128      (x0, pW[0]);
   x1 = _mm_and_si128      (x1, pW[1]);
   x2 = _mm_and_si128      (x2, pW[2]);
   x3 = _mm_and_si128      (x3, pW[3]);
   // add all bytes (with saturation)
   x0 = _mm_adds_epu8      (x0, x1);
   x0 = _mm_adds_epu8      (x0, x2);
   x0 = _mm_adds_epu8      (x0, x3);
   x0 = _mm_sad_epu8       (x0, _mm_setzero_si128 ());
   return _mm_cvtsi128_si32(x0)
        + _mm_extract_epi16(x0, 4);
}

Rotated Dot Product

A little bit cheaper is to expand the bitboard to a vector or 90 degree rotated {0,255} bytes, which requires a rotated weight vector as well ^[7].

/* for average weights < 64 */
int dotProduct64(U64 bb, BYTE weightsRot90[] /* XMM_ALIGN */)
{
   static const U64 CACHE_ALIGN masks[8] = {
      C64(0x0101010101010101), C64(0x0202020202020202),
      C64(0x0404040404040404), C64(0x0808080808080808),
      C64(0x1010101010101010), C64(0x2020202020202020),
      C64(0x4040404040404040), C64(0x8080808080808080),
   };
   __m128i x0, x1, x2, x3, zr; U32 cnt;
   __m128i * pM = (__m128i*) masks;
   __m128i * pW = (__m128i*) weightsRot90;
   x0 = _mm_cvtsi64x_si128 (bb);
   x0 = _mm_unpacklo_epi64 (x0, x0);
   zr = _mm_setzero_si128  ();
   x3 = _mm_andnot_si128   (x0, pM[3]);
   x2 = _mm_andnot_si128   (x0, pM[2]);
   x1 = _mm_andnot_si128   (x0, pM[1]);
   x0 = _mm_andnot_si128   (x0, pM[0]);
   x3 = _mm_cmpeq_epi8     (x3, zr);
   x2 = _mm_cmpeq_epi8     (x2, zr);
   x1 = _mm_cmpeq_epi8     (x1, zr);
   x0 = _mm_cmpeq_epi8     (x0, zr);
   // multiply by "and" with -1 or 0
   x3 = _mm_and_si128      (x3, pW[3]);
   x2 = _mm_and_si128      (x2, pW[2]);
   x1 = _mm_and_si128      (x1, pW[1]);
   x0 = _mm_and_si128      (x0, pW[0]);
   // add all bytes (with saturation)
   x3 = _mm_adds_epu8      (x3, x2);
   x0 = _mm_adds_epu8      (x0, x1);
   x0 = _mm_adds_epu8      (x0, x3);
   x0 = _mm_sad_epu8       (x0, zr);
   return _mm_cvtsi128_si32(x0)
        + _mm_extract_epi16(x0, 4);
}

SSE2 Population Count

Following proposal of a SWAR-Popcount combined with a dot product might be quite competitive on recent x86-64 processors with a throughput of up to three simd-instructions per cycle ^[8] ^[9] . It determines the cardinalities of eight bitboards, multiplies them with a corresponding weight, a signed 16-bit word, to finally add all together as integer. However, Wojciech Muła's SSSE3 PopCnt would save some more cycles, even more with doubled or fourfold register widths using AVX2 or AVX-512.

/**
 * popCountWeight8
 * @author Gerd Isenberg
 * @param bb vector of eight bitboards
 *        weight vector of eight short weights
 * @return sum(0,7) popcnt(bb[i]) * weight[i]
 */
int popCountWeight8(const U64 bb[8], const short weight[8]) {
   static const U64 XMM_ALIGN masks[6] = {
      C64(0x5555555555555555), C64(0x5555555555555555),
      C64(0x3333333333333333), C64(0x3333333333333333),
      C64(0x0f0f0f0f0f0f0f0f), C64(0x0f0f0f0f0f0f0f0f)
   };
   const __m128i* pM = (const __m128i*) masks;
   const __m128i* pb = (const __m128i*) bb;
   __m128i v = pb[0], w = pb[1], x = pb[2], y = pb[3];
   v = _mm_sub_epi8(v, _mm_and_si128(_mm_srli_epi64(v, 1), pM[0]));
   w = _mm_sub_epi8(w, _mm_and_si128(_mm_srli_epi64(w, 1), pM[0]));
   x = _mm_sub_epi8(x, _mm_and_si128(_mm_srli_epi64(x, 1), pM[0]));
   y = _mm_sub_epi8(y, _mm_and_si128(_mm_srli_epi64(y, 1), pM[0]));
 
   v = _mm_add_epi8(_mm_and_si128(v, pM[1]), _mm_and_si128(_mm_srli_epi64(v, 2), pM[1]));
   w = _mm_add_epi8(_mm_and_si128(w, pM[1]), _mm_and_si128(_mm_srli_epi64(w, 2), pM[1]));
   x = _mm_add_epi8(_mm_and_si128(x, pM[1]), _mm_and_si128(_mm_srli_epi64(x, 2), pM[1]));
   y = _mm_add_epi8(_mm_and_si128(y, pM[1]), _mm_and_si128(_mm_srli_epi64(y, 2), pM[1]));
 
   v = _mm_and_si128(_mm_add_epi8 (v, _mm_srli_epi64(v, 4)), pM[2]);
   w = _mm_and_si128(_mm_add_epi8 (w, _mm_srli_epi64(w, 4)), pM[2]);
   x = _mm_and_si128(_mm_add_epi8 (x, _mm_srli_epi64(x, 4)), pM[2]);
   y = _mm_and_si128(_mm_add_epi8 (y, _mm_srli_epi64(y, 4)), pM[2]);
 
   __m128i z = _mm_setzero_si128();
   v = _mm_packs_epi16(_mm_sad_epu8(v, z), _mm_sad_epu8(w, z));
   x = _mm_packs_epi16(_mm_sad_epu8(x, z), _mm_sad_epu8(y, z));
   const __m128i* pW = (const __m128i*) weight;
   v = _mm_madd_epi16 (_mm_packs_epi16(v, x), pW[0]);
   v = _mm_add_epi32  (v, _mm_srli_si128(v, 4));
   v = _mm_add_epi32  (v, _mm_srli_si128(v, 8));
   return _mm_cvtsi128_si32(v);
}

SSE2-Wrapper in C++

C++ quite efficiently allows to wrap all the intrinsics and to write classes with appropriate operators overloaded - the proposal here overloads + and - operators for byte- or rank-wise arithmetic, shifts work on 64-bit entities as often used in mentioned SSE2-routines or Kogge-Stone fill-stuff. A base class for the memory layout and two derivations provide to implement routines with SSE2 or general purpose instructions - or any other available SIMD-architecture like AltiVec. For instance a quad-bitboard attack-getter:

// T is either XMM or GPR
template <class T> inline
void eastAttacks(QBB& t, const QBB& s, U64 occ) {
   T* pt = (T*)&t;
   T r0(s.bb[0]);
   T r1(s.bb[2]);
   T o0(occ, occ);
   T o1  = o0 | r1;
   o0    = o0 | r0;
   pt[0] = o0 ^ ((o0 ^ r0) - r0);
   pt[1] = o1 ^ ((o1 ^ r1) - r1);
}

A proposal for a class skeleton:

class DBB
{
   friend class XMM;
   friend class GPR;
public:
   DBB(){}
   ... more constructors
public:
   union
   {
      __m128i x; // this intrinsice type is wrapped here
      u64 b[2];
   };
};
 
// intrinsic sse2 xmm wrapper
class XMM : public DBB
{
public:
   XMM(){}
   XMM(U64 b) {x = _mm_cvtsi64x_si128(b);}
   XMM(__m128i a){x = a;}
   XMM(U64 high, U64 low) ...
   ... more constructors
 
   XMM& operator>>=(int sh) {x = _mm_srli_epi64(x, sh); return *this;}
   XMM& operator<<=(int sh) {x = _mm_slli_epi64(x, sh); return *this;}
   XMM& operator&=(const XMM &a) {x = _mm_and_si128(x, a.x); return *this;}
   XMM& operator|=(const XMM &a) {x = _mm_or_si128 (x, a.x); return *this;}
   XMM& operator^=(const XMM &a) {x = _mm_xor_si128(x, a.x); return *this;}
 
   // byte- or rankwise arithmetic
   XMM& operator+=(const XMM &a) {x = _mm_add_epi8(x, a.x); return *this;}
   XMM& operator-=(const XMM &a) {x = _mm_sub_epi8(x, a.x); return *this;}
 
   friend XMM operator>>(const XMM &a, int sh) {return XMM(_mm_srli_epi64(a.x, sh));}
   friend XMM operator<<(const XMM &a, int sh) {return XMM(_mm_slli_epi64(a.x, sh));}
   friend XMM operator& (const XMM &a, const XMM &b) {return XMM(_mm_and_si128(a.x, b.x));}
   friend XMM operator| (const XMM &a, const XMM &b) {return XMM(_mm_or_si128(a.x, b.x));}
   friend XMM operator^ (const XMM &a, const XMM &b) {return XMM(_mm_xor_si128(a.x, b.x));}
   friend XMM operator+ (const XMM &a, const XMM &b) {return XMM(_mm_add_epi8(a.x, b.x));}
   friend XMM operator- (const XMM &a, const XMM &b) {return XMM(_mm_sub_epi8(a.x, b.x));}
   ...
};
 
// pure C wrapper
class GPR : public DBB
{
   ...
};

Manuals

Forum Posts

A SIMD idea, eg. Piece/Gain of a capture target by Gerd Isenberg, CCC, January 21, 2004 » Move Ordering
SSE2 bit[64] * byte[64] dot product by Gerd Isenberg, CCC, July 17, 2004
SSE2-Sort within a register by Gerd Isenberg, comp.lang.asm.x86, January 08, 2005
planning a SSE-optimized chess engine by Aart Bik, CCC, January 12, 2005
On SSE2-Intrinsics by Gerd Isenberg, CCC, March 28, 2005
Problem with functions not inlining by Gregory Strong, CCC, November 04, 2009

External Links

References

^ AMD64 Architecture, Programmer’s Manual, Volume 4 128-Bit Media Instructions (pdf), has detailed explanations on all SSE2 128-Bit Media Instructions.
^ Integer Intrinsics Using Streaming SIMD Extensions 2 Visual C++ Developer Center - Run-Time Library Reference
^ Instruction Reference Visual C++ Developer Center - Run-Time Library Reference
^ Intel(R) C++ Compiler User and Reference Guides covers Intrinsics
^ Intel C++ Compiler for Linux Intrinsics Reference (pdf)
^ Dot Product - from Wolfram MathWorld
^ SSE2 bit[64] * byte[64] dot product by Gerd Isenberg, Computer Chess Forums, July 17, 2004
^ Intel 64 and IA32 Architectures Optimization Reference Manual (pdf) Appendix C Instruction Latencies
^ Software Optimization Guide for AMD Family 10h and 12h Processors (pdf) Appendix C Instruction Latencies
^ Kraan homepage (German)

What links here?

Page	Date Edited
Aart Bik	Mar 1, 2018
AltiVec	Jun 7, 2016
AMD	Mar 9, 2018
AVX	Mar 7, 2017
AVX-512	Aug 8, 2017
AVX2	Aug 8, 2017
Byte	Apr 5, 2013
Cpp	Oct 24, 2017
Dictionary	Aug 24, 2017
DirGolem	Jun 5, 2016
Double	May 30, 2016
Fill by Subtraction	Mar 5, 2010
Float	Nov 11, 2016
General Setwise Operations	Feb 25, 2018
Gregory Strong	Apr 24, 2017
HansDamf	Jun 27, 2012
Intel	Aug 29, 2015
King Pattern	Nov 15, 2013
Kogge-Stone Algorithm	Sep 17, 2016
MMX	Jun 5, 2016
Mobility	Jan 17, 2018
Move Ordering	Feb 27, 2018
Papa	Jan 11, 2018
Population Count	Sep 3, 2017
Quad-Bitboards	Jan 30, 2017
Shared Hash Table	Sep 11, 2017
SIMD and SWAR Techniques	Jun 27, 2017
SIMD techniques	Nov 26, 2017
Sjaak (Glebbeek)	Oct 4, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE2 Instructions to Include	Jan 17, 2011
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
Windows	Nov 2, 2017
Word	Jan 25, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

SSE3

GerdIsenberg — Sun, 05 Jun 2016 22:00:11 GMT

Home * Hardware * x86 * SSE3

SSE3 (Streaming SIMD Extensions 3), is Intel's third iteration for the SSE x86 instruction set, introduced in 2004 with the Prescott revision of the Pentium 4 CPU. In April 2005 AMD introduced a subset of SSE3 in revision E (Venice and San Diego) of their Athlon 64 CPUs. The 13 new instructions are most processing vectors of floats or doubles, most notable horizontal add and sub inside one 128-bit xmm-register, LDDQU, an alternative misaligned load, which is even quite fast for loads that cross cacheline boundaries ^[1]^[2], and FISTTP, which is a new x87 instruction ^[3].

Publications

Daisuke Takahashi (2007). An Implementation of Parallel 1-D FFT Using SSE3 Instructions on Dual-Core Processors. Proc. Workshop on State-of-the-Art in Scientific and Parallel Computing (PARA 2006), Lecture Notes in Computer Science, No. 4699, pp. 1178-1187, Springer

External Links

References

What links here?

Page	Date Edited
Aart Bik	Mar 1, 2018
AltiVec	Jun 7, 2016
AMD	Mar 9, 2018
AVX	Mar 7, 2017
AVX2	Aug 8, 2017
Intel	Aug 29, 2015
SIMD and SWAR Techniques	Jun 27, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

SSE5

GerdIsenberg — Sun, 05 Jun 2016 22:00:33 GMT

Instructions

Some of the new instructions are quite interesting for computer chess, with applications in evaluation and byte shuffling of bitboards. Their XOP successors still work on 128-bit XMM registers ^[2], and implicitly clear the upper 128 bit of a 256-bit YMM register. Some of the instructions, like VPPERM, have as many as 4 operands.

XOP Instructions

External Links

References

^ AMD Fusion now pushed back to 2011 by Joel Hruska, November 14, 2008
^ Volume 6: 128-Bit and 256-Bit XOP, FMA4 and CVT16 Instructions (pdf)

What links here?

Page	Date Edited
AMD	Mar 9, 2018
Hyperbola Quintessence	Mar 25, 2017
SIMD and SWAR Techniques	Jun 27, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

SSSE3

GerdIsenberg — Tue, 08 Aug 2017 19:51:47 GMT

_m128i _mm_sign_epi8 (_m128i a, _m128i b);
_m128i _mm_sign_epi16 (_m128i a, _m128i b);
_m128i _mm_sign_epi32 (_m128i a, _m128i b);

Pseudocode

/* type := {char, short, int}, N = {16, 8, 4} */
#define N (sizeof(__m128i)/sizeof(type))
type a[N]; // input a
type b[N]; // input b
type r[N]; // output r
 
for (i=0; i < N; i++)
   r[i] = (b[i] < 0) ? -a[i] : ((b[i] == 0) ? 0 : a[i])

Applications

SSE3 Population Count

In 2008, Wojciech Muła introduced a SSSE3 Population Count performing a pair of PSHUFB 16 parallel nibble in-xmm lookups ^[4], in the meantime due to AVX2 or AVX-512 even possible with doubled or fourfold register widths, competing the native x86-64 popcount instruction ^[5]

/**
 * popCount2 
 * @author Wojciech Muła
 * @param v vector of two bitboards
 * @return quad word vector of two popcounts
*/
__m128i popCount(__m128i v) {
  __m128i lu = _mm_setr_epi8(0,1,1,2,1,2,2,3,1,2,2,3,2,3,3,4);
  __m128i lm = _mm_set1_epi8(0x0f);
  __m128i lo = _mm_and_si128(v, lm);
  __m128i hi = _mm_and_si128(_mm_srli_epi16(v, 4), lm);
  __m128i cl = _mm_shuffle_epi8(lu, lo); /* 16 low nibble counts */
  __m128i ch = _mm_shuffle_epi8(lu, hi); /* 16 high nibble counts */
  __m128i cb = _mm_add_epi8(cl, ch); /* 16 byte counts */
  return _mm_sad_epu8(cb, _mm_setzero_si128());
}

Byte-wise Dot-Product

This SSSE3-dot-product multiplies a vector of 64 unsigned chars with a vector of 64 signed char, and adds all 64 intermediate signed 16-bit products with saturation. It uses the pmaddubsw and phaddsw SSSE3 instructions, in total 11 SSE instructions.

int dotProduct(unsigned char features[], char weights[] /* XMM_ALIGN */) {
   __m128i r0, r1, r2, r3;
   __m128i* a = (__m128i*) features;
   __m128i* b = (__m128i*) weights;
   r0 = _mm_maddubs_epi16 (a[0], b[0]);
   r1 = _mm_maddubs_epi16 (a[1], b[1]);
   r2 = _mm_maddubs_epi16 (a[2], b[2]);
   r3 = _mm_maddubs_epi16 (a[3], b[3]);
   r0 = _mm_adds_epi16    (r0, r1);
   r2 = _mm_adds_epi16    (r2, r3);
   r0 = _mm_adds_epi16    (r0, r2); // 8 shorts
   r0 = _mm_hadds_epi16   (r0, r0); // 4 shorts
   r0 = _mm_hadds_epi16   (r0, r0); // 2 shorts
   r0 = _mm_hadds_epi16   (r0, r0); // 1 final short
   short s = (short)_mm_extract_epi16(r0, 0);
   return (int) s; // sign extended
}

SSSE3 Hyperbola Quintessence

Following routine calculates bishop attacks performing the Hyperbola Quintessence. Both anti-diagonal and diagonal attacks are processed in parallel, using both halves of a 128-bit xmm register and pre-calculated arrays of bitboard pairs for line-masks, single- and eventually reversed bits. PSHUFB is used to swap bytes inside a bitboard ^[6] .

Intrinsic Version

__m128i diaAntiMaskXMM[64]; // 1 KByte  antidiag : diagonal, excluding square
__m128i singleBitsXMM [64]; // 1 KByte    1<<sq  : 1<<sq
__m128i swapMaskXMM; // needs to be initialized to swap the bytes in both quad-words
 
// SSSE3 Hyperbola Quintessence
U64 bishopAttacks(U64 occ, enumSquare sq) {
   __m128i o, r, m, b, s;
   m = diaAntiMaskXMM[sq];         // antidiag : diagonal, excluding square
   b = singleBitsXMM [sq];         // bishop bits, equal qwords
   s = swapMaskXMM;
   o = _mm_cvtsi64x_si128  (occ) ; // general purpose 64 bit to xmm low qword
   o = _mm_unpacklo_epi64  (o, o); // occ : occ
   o = _mm_and_si128       (o, m); // o (antidiag : diagonal)
   r = _mm_shuffle_epi8    (o, s); // o'(antidiag : diagonal)
   o = _mm_sub_epi64       (o, b); // o - bishop
   b = _mm_shuffle_epi8    (b, s); // bishop', one may also use singleBitsXMM [sq^56]
   r = _mm_sub_epi64       (r, b); // o'- bishop'
   r = _mm_shuffle_epi8    (r, s); // re-reverse
   o = _mm_xor_si128       (o, r); // attacks
   o = _mm_and_si128       (o, m); // antidiag : diagonal
   r = _mm_unpackhi_epi64  (o, o); // antidiag : antidiag
   o = _mm_add_epi64       (o, r); // diagonal + antidiag
   return _mm_cvtsi128_si64(o);    // convert xmm to general purpose 64 bit
}

Peshkov's Optimization

The pioneer of Hyperbola Quintessence, Aleks Peshkov, applies a more sophisticated, optimized C++ approach, further utilizing disjoint ray-attacks, and xor instruction is own inverse and distributive over mirroring or flipping. Once per node he instantiates an occupied object based on a type-safe curiously recurring template pattern aka the Barton–Nackman trick to encapsulate the SSE intrinsic data types, to keep a twin of normal and flipped occupancy as base for further file-, diagonal or anti-diagonal attack generations, which then requires only one final shuffle per piece attack getter, whether it is a bishop or even a queen.

class Occupied : public BitSet<Occupied, char_x16_t> {
    typedef BitSet<Occupied, char_x16_t> Base;
 
    struct Mask {
        value_type singleton;
        value_type file;
        value_type diagonal;
        value_type antidiag;
 
        Mask operator () (Square);
    };
    typedef Square::const_array<Mask, Mask> CACHE_ALIGN AttackMask;
    static const AttackMask mask;
 
    struct Shuffle {
        value_type hyperbola;
        value_type flipShift;
        Shuffle ();
    };
    static const Shuffle shuffle;
 
    static BitBoard bitboard(value_type value) {
        return BitBoard(static_cast<BitBoard::value_type>(_mm_cvtsi128_si64(value)));
    }
 
    static BitBoard hyperbola(value_type value) {
        value_type reverse = _mm_shuffle_epi8(value, shuffle.hyperbola);
        return bitboard(value ^ reverse); //xor is principal here
    }
 
    INLINE BitBoard bishopAttack(Square from) const {
        value_type d = value;
        value_type a = value;
        d &= mask[from].diagonal;
        a &= mask[from].antidiag;
        d = _mm_sub_epi64(d, mask[from].singleton);
        a = _mm_sub_epi64(a, mask[from].singleton);
        d &= mask[from].diagonal;
        a &= mask[from].antidiag;
        return hyperbola(d ^ a);
    }
 
    ...
public:
    Occupied (const BitBoard& myB, const BitBoard& opB) {
        value_type my = _mm_cvtsi64_si128(reinterpret_cast<const U64&>(myB));
        value_type op = _mm_cvtsi64_si128(reinterpret_cast<const U64&>(opB));
        op = _mm_shuffle_epi8(op, shuffle.flipShift);
        assert (Occupied(my & op) == empty()); //no intersection
        this->value = my ^ op;
    }
 
    ...
};

External Links

SSSE3 from Wikipedia
SSEPlus Project Documentation
Agner`s CPU blog by Agner Fog
SSSE3: fast popcount by Wojciech Muła, May 24, 2008 » Population Count
Intel Intrinsics Guide

References

^ Supplemental Streaming SIMD Extensions 3 Instructions
^ Intel C++ Compiler for Linux Intrinsics Reference (pdf)
^ fixing SSSE3 pmaddubsw description from the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project
^ SSSE3: fast popcount by Wojciech Muła, May 24, 2008
^ Wojciech Muła, Nathan Kurz, Daniel Lemire (2016). Faster Population Counts Using AVX2 Instructions. arXiv:1611.07612
^ Re: Plain and fancy magic on modern hardware by Robert Purves, CCC, August 23, 2010

What links here?

Page	Date Edited
Aart Bik	Mar 1, 2018
Aleks Peshkov	Jan 13, 2016
AltiVec	Jun 7, 2016
AVX	Mar 7, 2017
AVX2	Aug 8, 2017
Hyperbola Quintessence	Mar 25, 2017
Intel	Aug 29, 2015
Population Count	Sep 3, 2017
Reverse Bitboards	Aug 29, 2015
SIMD and SWAR Techniques	Jun 27, 2017
SIMD techniques	Nov 26, 2017
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
Windows	Nov 2, 2017
Wojciech Muła	Aug 10, 2017
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017

Up one Level

TBM

GerdIsenberg — Thu, 28 Jun 2012 17:56:56 GMT

Instructions

Least Significant One Bit

BLSFILL

BLSIC

TZMSK

Least Significant Zero Bit

Home * Hardware * x86-64 * TBM

TBM (Trailing Bit Manipulation Instructions),
an x86-64 expansion of bit-manipulation instructions, introduced by AMD with the Bulldozer microarchitecture, which also comprises the AVX, BMI1 and XOP instruction sets. TBM requires bit 21 set in ECX of CPUID EAX=80000001H ^[1].

Instructions

TBM offers various bit-manipulations based on the least significant one or zero bit. In general they combine two or three operations on 32- or 64-bit general purpose registers, expanding the BMI type of operations of BLSI, BLSMSK, BLSR. In C and C++, these instructions should be emitted by an optimizing compiler for this target platform, rather than using intrinsics. Instructions are given with mnemonics with 64-bit destination and source register according to Intel Syntax, C like definition, and some arbitrary bitboard diagrams with little-endian rank-file mapping (least significant bit 0 as square a1 bottom-left) to illustrate the operations.

Code samples and bitboard diagrams rely on Little endian file and rank mapping.

Least Significant One Bit

BLSFILL

Fill From Lowest Set Bit. Union with the decrement.

BLSFILL reg64, reg/mem64
dest ::= src | (src - 1);
 
       src         |     (src - 1)     =       dest
0x0040201008040200  0x00402010080401FF  0x00402010080403FF
  . . . . . . . .     . . . . . . . .     . . . . . . . .
  . . . . . . 1 .     . . . . . . 1 .     . . . . . . 1 .
  . . . . . 1 . .     . . . . . 1 . .     . . . . . 1 . .
  . . . . 1 . . .     . . . . 1 . . .     . . . . 1 . . .
  . . . 1 . . . .  |  . . . 1 . . . .  =  . . . 1 . . . .
  . . 1 . . . . .     . . 1 . . . . .     . . 1 . . . . .
  . 1 . . . . . .     1 . . . . . . .     1 1 . . . . . .
  . . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1

BLSIC

Isolate Lowest Set Bit and Complement. Union of complement and decrement.

BLSIC reg64, reg/mem64
dest ::= ~src | (src - 1);
 
       src        ->       ~src        |     (src - 1)     =       dest
0x0040201008040200  0x00402010080401FF  0x00402010080403FF  0xFFFFFFFFFFFFFDFF
  . . . . . . . .     1 1 1 1 1 1 1 1     . . . . . . . .     1 1 1 1 1 1 1 1
  . . . . . . 1 .     1 1 1 1 1 1 . 1     . . . . . . 1 .     1 1 1 1 1 1 1 1
  . . . . . 1 . .     1 1 1 1 1 . 1 1     . . . . . 1 . .     1 1 1 1 1 1 1 1
  . . . . 1 . . .     1 1 1 1 . 1 1 1     . . . . 1 . . .     1 1 1 1 1 1 1 1
  . . . 1 . . . . ->  1 1 1 . 1 1 1 1  |  . . . 1 . . . .  =  1 1 1 1 1 1 1 1
  . . 1 . . . . .     1 1 . 1 1 1 1 1     . . 1 . . . . .     1 1 1 1 1 1 1 1
  . 1 . . . . . .     1 . 1 1 1 1 1 1     1 . . . . . . .     1 . 1 1 1 1 1 1
  . . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1

TZMSK

Mask From Trailing Zeros. Intersection of complement and decrement sets all bits below the least significant one bit, and clears all other bits, including the LS1B itself.

dest ::= ~src & (src - 1);
       src        ->       ~src        &     (src - 1)     =       dest
0x0040201008040200  0x00402010080401FF  0x00402010080403FF  0x00000000000001FF
  . . . . . . . .     1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .
  . . . . . . 1 .     1 1 1 1 1 1 . 1     . . . . . . 1 .     . . . . . . . .
  . . . . . 1 . .     1 1 1 1 1 . 1 1     . . . . . 1 . .     . . . . . . . .
  . . . . 1 . . .     1 1 1 1 . 1 1 1     . . . . 1 . . .     . . . . . . . .
  . . . 1 . . . . ->  1 1 1 . 1 1 1 1  &  . . . 1 . . . .  =  . . . . . . . .
  . . 1 . . . . .     1 1 . 1 1 1 1 1     . . 1 . . . . .     . . . . . . . .
  . 1 . . . . . .     1 . 1 1 1 1 1 1     1 . . . . . . .     1 . . . . . . .
  . . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1

Least Significant Zero Bit

BLCFILL

Fill From Lowest Clear Bit. Intersection with the increment.

BLCFILL reg64, reg/mem64
dest ::= src & (src + 1);
 
       src         &     (src + 1)     =       dest
0x80C0E0F0F8FCFEFF  0x80C0E0F0F8FCFF00  0x80C0E0F0F8FCFE00
  . . . . . . . 1     . . . . . . . 1     . . . . . . . 1  
  . . . . . . 1 1     . . . . . . 1 1     . . . . . . 1 1  
  . . . . . 1 1 1     . . . . . 1 1 1     . . . . . 1 1 1  
  . . . . 1 1 1 1     . . . . 1 1 1 1     . . . . 1 1 1 1  
  . . . 1 1 1 1 1  &  . . . 1 1 1 1 1  =  . . . 1 1 1 1 1  
  . . 1 1 1 1 1 1     . . 1 1 1 1 1 1     . . 1 1 1 1 1 1  
  . 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     . 1 1 1 1 1 1 1  
  1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .

BLCI

Isolate Lowest Clear Bit. Union with the complement of the increment.

BLCI reg64, reg/mem64
dest ::= src | ~(src + 1);
 
       src         |    ~(src + 1)     =       dest
0x80C0E0F0F8FCFEFF  0x7F3F1F0F070300FF  0xFFFFFFFFFFFFFEFF
  . . . . . . . 1     1 1 1 1 1 1 1 .     1 1 1 1 1 1 1 1  
  . . . . . . 1 1     1 1 1 1 1 1 . .     1 1 1 1 1 1 1 1  
  . . . . . 1 1 1     1 1 1 1 1 . . .     1 1 1 1 1 1 1 1  
  . . . . 1 1 1 1     1 1 1 1 . . . .     1 1 1 1 1 1 1 1  
  . . . 1 1 1 1 1  |  1 1 1 . . . . .  =  1 1 1 1 1 1 1 1  
  . . 1 1 1 1 1 1     1 1 . . . . . .     1 1 1 1 1 1 1 1  
  . 1 1 1 1 1 1 1     . . . . . . . .     . 1 1 1 1 1 1 1  
  1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1

BLCIC

Isolate Lowest Clear Bit and Complement. Intersection of the complement with the increment.

BLCIC reg64, reg/mem64
dest ::= ~src & (src + 1);
 
       src        ->       ~src        &     (src + 1)     =       dest
0x80C0E0F0F8FCFEFF  0x7F3F1F0F07030100  0x80C0E0F0F8FCFF00  0x0000000000000100
  . . . . . . . 1     1 1 1 1 1 1 1 .     . . . . . . . 1     . . . . . . . . 
  . . . . . . 1 1     1 1 1 1 1 1 . .     . . . . . . 1 1     . . . . . . . .  
  . . . . . 1 1 1     1 1 1 1 1 . . .     . . . . . 1 1 1     . . . . . . . .  
  . . . . 1 1 1 1     1 1 1 1 . . . .     . . . . 1 1 1 1     . . . . . . . .  
  . . . 1 1 1 1 1 ->  1 1 1 . . . . .  &  . . . 1 1 1 1 1  =  . . . . . . . .  
  . . 1 1 1 1 1 1     1 1 . . . . . .     . . 1 1 1 1 1 1     . . . . . . . .  
  . 1 1 1 1 1 1 1     1 . . . . . . .     1 1 1 1 1 1 1 1     1 . . . . . . .  
  1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .     . . . . . . . .

BLCMSK

Mask From Lowest Clear Bit. Exclusive or with the increment.

BLCMSK reg64, reg/mem64
dest ::= src ^ (src + 1);
 
       src         ^     (src + 1)     =       dest
0x80C0E0F0F8FCFEFF  0x80C0E0F0F8FCFF00  0x00000000000001FF
  . . . . . . . 1     . . . . . . . 1     . . . . . . . .  
  . . . . . . 1 1     . . . . . . 1 1     . . . . . . . .  
  . . . . . 1 1 1     . . . . . 1 1 1     . . . . . . . .  
  . . . . 1 1 1 1     . . . . 1 1 1 1     . . . . . . . .  
  . . . 1 1 1 1 1  ^  . . . 1 1 1 1 1  =  . . . . . . . .  
  . . 1 1 1 1 1 1     . . 1 1 1 1 1 1     . . . . . . . .  
  . 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 . . . . . . .  
  1 1 1 1 1 1 1 1     . . . . . . . .     1 1 1 1 1 1 1 1

BLCS

Set Lowest Clear Bit. Union with the increment.

BLCS reg64, reg/mem64
dest ::= src | (src + 1);
 
       src         |     (src + 1)     =       dest
0x80C0E0F0F8FCFEFF  0x80C0E0F0F8FCFF00  0x80C0E0F0F8FCFFFF
  . . . . . . . 1     . . . . . . . 1     . . . . . . . 1  
  . . . . . . 1 1     . . . . . . 1 1     . . . . . . 1 1  
  . . . . . 1 1 1     . . . . . 1 1 1     . . . . . 1 1 1  
  . . . . 1 1 1 1     . . . . 1 1 1 1     . . . . 1 1 1 1  
  . . . 1 1 1 1 1  |  . . . 1 1 1 1 1  =  . . . 1 1 1 1 1  
  . . 1 1 1 1 1 1     . . 1 1 1 1 1 1     . . 1 1 1 1 1 1  
  . 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1  
  1 1 1 1 1 1 1 1     . . . . . . . .     1 1 1 1 1 1 1 1

T1MSKC

Inverse Mask From Trailing Ones. Union of complement and increment.

T1MSKC reg64, reg/mem64
dest ::= ~src | (src + 1);
 
       src        ->       ~src        |     (src + 1)     =       dest
0x80C0E0F0F8FCFEFF  0x7F3F1F0F07030100  0x80C0E0F0F8FCFF00  0xFFFFFFFFFFFFFF00
  . . . . . . . 1     1 1 1 1 1 1 1 .     . . . . . . . 1     1 1 1 1 1 1 1 1  
  . . . . . . 1 1     1 1 1 1 1 1 . .     . . . . . . 1 1     1 1 1 1 1 1 1 1  
  . . . . . 1 1 1     1 1 1 1 1 . . .     . . . . . 1 1 1     1 1 1 1 1 1 1 1  
  . . . . 1 1 1 1     1 1 1 1 . . . .     . . . . 1 1 1 1     1 1 1 1 1 1 1 1  
  . . . 1 1 1 1 1 ->  1 1 1 . . . . .  |  . . . 1 1 1 1 1  =  1 1 1 1 1 1 1 1  
  . . 1 1 1 1 1 1     1 1 . . . . . .     . . 1 1 1 1 1 1     1 1 1 1 1 1 1 1  
  . 1 1 1 1 1 1 1     1 . . . . . . .     1 1 1 1 1 1 1 1     1 1 1 1 1 1 1 1  
  1 1 1 1 1 1 1 1     . . . . . . . .     . . . . . . . .     . . . . . . . .

Misc

BEXTR

An immediate form of the variable BMI1 Bit Field Extract.

BEXTR reg32, reg/mem32, imm32
BEXTR reg64, reg/mem64, imm32

Manuals

AMD64 Architecture Programmer’s Manual Volume 3: General-Purpose and System Instructions (pdf) ^[2]
Software Optimization Guide for AMD Family 15h Processors (pdf) 9.9 Optimizing with BMI and TBM Instructions, pp. 163

References

^ AMD CPUID Specification (pdf)
^ Moved BMI and TBM instructions from Volume 4 to Volume 3 in September 2011

What links here?

Page	Date Edited
Bit-Twiddling	Nov 6, 2017
BMI1	Mar 24, 2014
BMI2	Mar 6, 2018
General Setwise Operations	Feb 25, 2018
SSE4	Jun 5, 2016
TBM	Jun 28, 2012
x86-64	Mar 6, 2018

Up one Level

Word

GerdIsenberg — Sun, 25 Jan 2015 22:21:42 GMT

Home * Programming * Data * Word

A Word or Computer Word, is a term for the natural unit of data used by a particular computer architecture. Modern computers usually have a word size to be a power of 2 multiple of the unit of address resolution, likely a Byte, that is two, four, or eight Bytes, which are 16, 32, or 64 bits. Many other sizes have been used in the past, including 8 (a Byte), 9, 12, 18, 24, 36, 39, 40, 48, and 60 bits. Some of the early computers were decimal rather than binary, having a word size of 10 or 12 decimal digits, and some of them had no fixed word length at all.

16-bit Word

Often the size of a word is defined to be a value for compatibility with earlier computers, such as Intel's x86 and x86-64 architecture, which referes a Word from the original 8086 16-bit µ-Processor. Subsequently Intel used the terms Double Word (dword) for 32-bit words, a quadruple word or Quad Word (qword) for 64-bits words, and even a Double Quad Word for 128-bit words. x86 and x86-64 registers may still treated as word registers (ax versus eax or even rax) , while it is recommend to use the native 32-bit double word, because the word-wise access requires a prefix byte to overwrite the default width. SIMD instruction sets like MMX, AltiVec and SSE2 provide operations on vectors of four or eight words inside appropriate SIMD-registers. IBM 360 and successors with 32-bit words, refer 16-bit size as halfword.

Short

On recent 32-bit and 64-bit processors the primitive C datatype short and unsigned short refers to 16-bit words by most compilers for those architectures. In Java, short is guaranteed to have 16-bit. Signed short in C is assumed to use Twos' Complement, but not strictly specified. A Word-type, explicitly type-defined in C, is therefor usually treated as unsigned, also to avoid arithmetical right shift issues:

typedef unsigned char  BYTE;
typedef unsigned short WORD;

Ranges

type	language	min	max
unsigned short	C, C++	0	65535
hexadecimal		0x0000	0xFFFF
#include <limits.h>			USHRT_MAX
short	C, C++, Java	-32768	32767
hexadecimal		0x8000	0x7FFF
#include <limits.h>		SHRT_MIN	SHRT_MAX

Alignment

Words stored in memory should be stored at even byte addresses. Otherwise at runtime it will cause a miss-alignment exception on some processors, or a huge penalty on others.

Endianness

Main article: Endianness.
An issue with words consisting of two or more bytes, is the order, bytes may appear inside a word of memory. According to their usual arithmetical significance, there is a low and a high byte of a 16-bit word, which may either be stored at the lower or higher byte-address in memory. Intel processors were always so called little-endian machines, the least significant byte (LSB) is at the lowest address. Other processors, including the IBM 370 family, the PDP-10 (36 bit), the Motorola microprocessor families, and most of the various RISC designs are big-endian, and store the ‘big-end-first’.

Extracting Bytes

Following C union to extract or synthesize bytes from/in words, is not portable and should be avoided.

union {
   BYTE b[2];
   WORD s;
} u;
 
u.s = 0xaa55;
assert (u.b[0] == 0x55); // fails, if big-endian

The portable way in C can be done with inlined functions or C preprocessor macros, using arithmetical divide or modulo by 256, aka shift and mask by bitwise 'and' - or for the synthesis multiplication of high byte by 256 plus low byte:

BYTE lowByte (WORD s) {return (BYTE)(s & 255);} // mod 256
BYTE highByte(WORD s) {return (BYTE)(s >>  8);} // div 256
 
WORD makeWORD (BYTE high, BYTE low) {
   WORD  s = high;
   return (s << 8) + low; // high * 256 + low
}

External Links

Word from Wikipedia
Byte from Wikipedia
Endianness from Wikipedia
Understanding Big and Little Endian Byte Order
IEN 137 - DAV's Endian FAQ - On Holy Wars and a Plea for Peace by Danny Cohen, U S C/I S I, April 1, 1980
Mahavishnu Orchestra - One Word, 1973, YouTube Video
John McLaughlin, Billy Cobham, Rick Laird, Jan Hammer, Jerry Goodman

What links here?

Page	Date Edited
More Links
6502	Dec 25, 2017
6800	Jun 23, 2017
8080	Sep 3, 2017
8086	Sep 18, 2014
AltiVec	Jun 7, 2016
Array	Dec 1, 2016
AVX-512	Aug 8, 2017
Big-endian	Jan 25, 2015
Bit	Oct 29, 2012
Bitboard Serialization	Dec 24, 2014
BMI2	Mar 6, 2018
Byte	Apr 5, 2013
Checkmate	Apr 13, 2018
CHEOPS	Apr 18, 2015
CookieCat	Nov 15, 2016
Cray-1	Dec 25, 2017
Data	Nov 26, 2017
DEC Alpha	Aug 15, 2015
Dictionary	Aug 24, 2017
Double Word	Jan 25, 2015
Encoding Moves	Mar 27, 2016
Endianness	Jan 25, 2015
Fairchild F8	Jul 31, 2015
General Setwise Operations	Feb 25, 2018
Graphics Programming	Dec 22, 2017
HP 2100	Jan 3, 2018
i860	Aug 21, 2015
IBM 704	Jan 2, 2016
Little-endian	Jan 25, 2015
MMX	Jun 5, 2016
Murka	Nov 11, 2016
Nova	Jan 20, 2016
PDP-11	Jan 5, 2016
Quad Word	Jan 25, 2015
Score	Apr 14, 2018
SIMD and SWAR Techniques	Jun 27, 2017
Spector	Nov 11, 2016
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSSE3	Aug 8, 2017

Up one Level

x86

GerdIsenberg — Thu, 04 Jan 2018 20:27:06 GMT

Home * Hardware * x86

		x86, also called IA-32, is an architecture referred to the 32-bit instruction set of the Intel 80386 processor released in 1985 - the successor of Intel's 16-bit 8086 until 80286 processors. x86 could address up to 4GByte physical memory, had virtual memory pages and a mode to protect them over process boundaries - a requirement for multitasking operating systems, despite 16-bit MS-DOS was still popular. While the initial x86 was Complex Instruction Set Computing (CISC), the RISC versus CISC issue had become indistinct with more recent x86 processors, internally processing RISC like micro opcode. Over the time, modern architectural features, such as Out-of-order execution, Pipelining, Register Renaming and Branch Predication became an issue. 80386 was once clocked by about 25MHz. The RAM access speed could not keep up with higher and higher clock frequency of later processors - small but faster cache memory became necessary and strategies to make them efficient, nowadays even with three cache levels with different size and speed.
Die shot of Intel 80386 DX-25 ^[1]

see x86-64 for x86 64-bit

Security Vulnerability

References

What links here?

Computer Chess

A lot of commercial and amateur PC chess programs, notably under the operating systems MS-DOS and later Windows and Linux, were developed for this widespread architecture, often taking advantage of 32-bit registers and new instructions, for instance bsf and btr for bitscanning 2 * 32-bit Bitboards and 32-bit Piece-Sets. Those instructions were usually not available through high level programming languages, but through Assembly language, later often as inline assembly of various high level language compilers, for instance Microsoft Visual C and the GNU C Compiler. Under the 16-bit real mode operating system MS-DOS, it was quite common in chess programming to use the unreal mode ^[2] ^[3] to allocate much more physical memory for the Transposition Table, the 16 bit operating system, not aware of the huge address space, could access. Other DOS programs relied on memory extenders.

Architectures

While the 80386 represented the third microarchitecture (after 8086, 80286), 80486 and Pentium were the fourth and fifth, later called P5 microarchitecture. In 1995 with Pentium Pro, Intel introduced the P6 microarchitecture, eventually revived in the Pentium M line of microprocessors and the predecessor of Intel's Core 2 microarchitecture. Intel's NetBurst microarchitecture with the advent of the Pentium 4 processor, was famous for its clock speed, but no good reputation by most chess programmers, who favored the AMD K6- and K7-architecture, namely the Athlon processor at that time. To begin with the rebirth of P6 and Intel Core 2 architecture in 2006, things changed in favor to Intel again. In November 2008 the Nehalem microarchitecture appeared.

Intel's IA-64 architecture is a complete new and incompatible instruction set to IA-32. It is used by the Itanium line of processors. The backward compatible 64-bit successor was designed by AMD with the advent of Hammer or AMD64, later cloned by Intel and together referred to the x86-64 architecture.

Register Files

x86 has eight 32-bit general purpose registers:

General Purpose

The eight general purpose registers may be treated as 32-bit Double Word, 16-bit Word and high and low Byte:

32	16	8 high	8 low	Purpose
EAX	AX	AH	AL	GP, Accumulator
EBX	BX	BH	BL	GP, Index Register
ECX	CX	CH	CL	GP, Counter, variable shift, rotate via CL
EDX	DX	DH	DL	GP, high Accumulator mul/div
ESI	SI	-	-	GP, Source Index
EDI	DI	-	-	GP, Destination Index
ESP	SP	-	-	Stack Pointer
EBP	BP	-	-	GP, Base Pointer

MMX

MMX was introduced with Pentium MMX in 1996, adopted by AMD's K6 in 1997.
Eight 64-bit MMX-Registers: MM0 - MM7.
Treated as Double or Quad Word, vector of two Floats or Double Words, and as vector if four Words or eight Bytes.

3DNow!

An MMX-floating point extension by AMD, introduced in the K6-2 processor, 1998.
It uses the eight 64-bit MMX-Registers: MM0 - MM7.

SSE/SSE2

SSE was introduced by Pentium III in 1997, SSE2 by Pentium 4 in 2000
Eight 128-bit XMM-Registers: XMM0 - XMM7.
Treated as vector of two Doubles (SSE) or Quad Words (SSE2), as vector of four Floats (SSE) or Double Words (SSE2), and as vector if eight Words (SSE2) or 16 Bytes (SSE2).

CPUS

Intel

80386 1985
80486 1989
Pentium 1993 ^[4]
Pentium with P54C core
Pentium MMX 1993
P6 microarchitecture
- Pentium Pro 1995
- Pentium II 1997
- Pentium III 1999
NetBurst microarchitecture
- Pentium 4 2000
Intel Core microarchitecture
- Pentium M
Intel Atom 2008

Cyrix

Cyrix 6x86 1996

AMD

K5 March 1996
K6 1997
K6-2 1998
Athlon (K7) 1999
- Athlon XP ^[5]
  AMD Athlon XP (Thoroughbred)
- Athlon MP
AMD has continued the name with the Athlon 64, featuring AMD64 64-bit technology, later called x86-64.

Software

Operating Systems

Development

Assembly

Pascal

C-Compiler

Extensions

Manuals

Intel

AMD

AMD Athlon Processor x86 Code Optimization Guide (pdf)

Forum Posts

Question for Eugene Nalimov by James Robertson, CCC, December 21, 1998
why loop unrolling isn't as useful on x86 as it once was by Wylie Garvin, CCC, February 07, 2002
Programmer challenge by Ed Schröder, CCC, February 20, 2003
Expert Assembler Question by Ed Schröder, CCC, August 26, 2005
Intel CPU performance-loss by security-patch?!? by Stefan Pohl, CCC, January 03, 2018

External Links

Assembly

Modes

Instruction Sets

Bugs

Security Vulnerability

References

^ Die shot of Intel 80386 DX-25 microprocessor (SX215) by Pauli Rautakorpi, October 28, 2013, Wikimedia Commons
^ Flat real / real big / unreal mode (v1.2) from Programmer's Heaven
^ Unreal mode by Safronov's family, comp.lang.asm.x86, June 5, 2003
^ Die shot of Intel Pentium with P54C core by Pauli Rautakorpi, June 11, 2013, Wikimedia Commons
^ Die shot of AMD Athlon XP microprocessor with Thoroughbred core (AXDA1800DLT3C) by Pauli Rautakorpi, February 14, 2014, Wikimedia Commons

What links here?

Page	Date Edited
14th Computer Olympiad	Jul 23, 2017
2nd Computer Olympiad	Jul 12, 2017
4th Computer Olympiad	Jul 15, 2017
68000	Jun 7, 2016
68030	Jun 7, 2016
8086	Sep 18, 2014
Aart Bik	Mar 1, 2018
ABK	Feb 1, 2017
ACM 1987	Dec 5, 2017
ACM 1988	Dec 5, 2017
ACM 1989	Jun 7, 2016
ACM 1990	Jun 7, 2016
ACM 1991	Nov 25, 2017
ACM 1993	Oct 30, 2017
ACM 1994	May 5, 2017
Acorn Atom	Dec 11, 2016
Adam	Feb 24, 2015
Alexander Naumov	Sep 19, 2014
AltiVec	Jun 7, 2016
Alybadix	Apr 26, 2016
AMD	Mar 9, 2018
AnMon	Nov 17, 2017
Artem Petakov	Jan 14, 2017
Assembly	Sep 3, 2017
Aubervilliers Rapid Open	Mar 25, 2017
Avoiding Branches	Dec 16, 2016
AVX	Mar 7, 2017
AVX2	Aug 8, 2017
Awari	Feb 14, 2017
Axon	Jul 14, 2013
Bareev versus Hiarcs 2003	Aug 18, 2016
BB	Jan 8, 2016
Bitboard Board-Definition	Jun 23, 2014
Bitboards	Nov 14, 2017
BitScan	Sep 10, 2017
Bookup	Feb 4, 2018
BootChess	May 16, 2017
Bouquet	May 17, 2016
BP	Jan 7, 2016
Bruno Bras	Jul 3, 2017
Buzz	Jun 22, 2016
Byte	Apr 5, 2013
Carey Bloodworth	Jul 19, 2016
Center Manhattan-Distance	Nov 26, 2016
Check Check	Jan 8, 2016
Chess Genius	Feb 26, 2018
Chess Wizard	Dec 22, 2014
ChessBase (Database)	Feb 26, 2018
ChessLin	May 17, 2017
Color of a Square	May 24, 2015
Crafty	Jan 28, 2018
Dappet	Dec 12, 2016
Debugging	Jan 20, 2018
Delfi	Jan 7, 2016
Delphi	Dec 16, 2016
Dictionary	Aug 24, 2017
DOCCC 1992	Dec 12, 2016
DOCCC 1993	Dec 12, 2016
DOCCC 1995	Jun 7, 2016
DOCCC 1996	Jun 7, 2016
Double	May 30, 2016
Double Word	Jan 25, 2015
Ed Schroder	Feb 26, 2018
Efficient Generation of Sliding Piece Attacks	Nov 5, 2016
Encoding Moves	Mar 27, 2016
Eric van Riet Paap	Feb 14, 2017
Eugen	Jan 7, 2016
Evaluator	Jun 5, 2013
Explorer	Dec 8, 2016
FCCC 1995	Jul 27, 2015
Fencer	Jan 20, 2013
Float	Nov 11, 2016
Freccia	Dec 26, 2017
Gambiet	Jan 8, 2016
Gandalf	Jan 21, 2018
General Setwise Operations	Feb 25, 2018
Genesis NL	Dec 12, 2016
Gk	Oct 9, 2017
Gunda-1	Jan 8, 2016
Hardware	Jan 20, 2018
Hiarcs	Feb 25, 2018
Houdini	Apr 14, 2018
Huib-Jan Imbens	Aug 20, 2015
Hydra 97	Jan 1, 2017
i860	Aug 21, 2015
IBM PC	Dec 9, 2016
Intel	Aug 29, 2015
IPCCC 1991	Jun 9, 2016
Itanium	Aug 29, 2015
Joker IT	Sep 16, 2017
Kallisto	Oct 28, 2017
Kasparov's Gambit	Dec 7, 2016
KBNK Endgame	Nov 26, 2016
Kim Walisch	Aug 10, 2017
Knight-Distance	Oct 20, 2013
Kristy Lenix	Nov 28, 2015
LChess	Jan 7, 2016
Leonid Liberman	May 23, 2015
Linux	Jan 21, 2018
Little-endian	Jan 25, 2015
LL Chess	May 23, 2015
Mac OS	Mar 25, 2016
Macintosh	Dec 7, 2016
Matt Taylor	Feb 17, 2013
Matthias Engelbach	Jan 7, 2016
Memory	Dec 8, 2017
Mephisto	Dec 18, 2017
Mephisto Genius 68030	Sep 2, 2017
Mephisto Wundermaschine	Sep 2, 2017
Milobarus	Nov 23, 2016
MMX	Jun 5, 2016
MS-DOS	Feb 3, 2018
Naum	Nov 23, 2017
Nero	May 5, 2017
Nightmare GER	Dec 12, 2016
NUMA	Mar 29, 2017
OliThink	May 19, 2017
Olivier Poudade	May 16, 2017
Oracle	Sep 4, 2016
P.ConNerS	Dec 22, 2016
Pandix	Feb 4, 2017
Papa	Jan 11, 2018
Pascal	Nov 28, 2016
Pastime	Nov 3, 2015
Paul Hsieh	Aug 14, 2015
Petunia	Aug 21, 2015
Philippe Fabiani	Sep 15, 2016
PicoChess	Mar 12, 2018
Pioneer	Dec 23, 2017
Population Count	Sep 3, 2017
PowerPC	Oct 6, 2017
Prochess	Jan 7, 2016
Psycho	Nov 7, 2016
Pulsar	May 4, 2017
Quad Word	Jan 25, 2015
Rabbit	Oct 5, 2014
RDChess	May 3, 2013
Rebel	Feb 25, 2018
Requiem	Feb 5, 2018
Rex	Jan 7, 2016
RexChess	Dec 7, 2016
Robert Cullum	Jan 7, 2016
Schach	Jan 7, 2016
Schach (US)	Jul 21, 2016
Scid on the Go	Jan 26, 2015
Shared Hash Table	Sep 11, 2017
Shrike	Dec 30, 2012
SIMD and SWAR Techniques	Jun 27, 2017
SIMD techniques	Nov 26, 2017
Socrates	Jul 3, 2018
Spector	Nov 11, 2016
SSE	Mar 7, 2017
SSE2	Feb 27, 2018
SSE2 Instructions to Include	Jan 17, 2011
SSE3	Jun 5, 2016
SSE4	Jun 5, 2016
SSE5	Jun 5, 2016
SSSE3	Aug 8, 2017
Stack	Nov 18, 2016
Stan Arts	Nov 21, 2014
TascBase	Dec 7, 2016
Terra	Feb 11, 2015
The King	Jan 21, 2018
Thomas Kreitmair	Feb 12, 2016
Thor's Hammer	Nov 23, 2013
Titan	Jul 3, 2018
Toledo	Sep 23, 2017
Turning Point	Apr 6, 2012
UPCCC 1992	Mar 9, 2012
USOCCC 1987	Nov 30, 2017
Vector Attacks	Dec 15, 2017
Warrior	Feb 23, 2015
WCCC 1989	Dec 5, 2017
WCCC 1992	Feb 26, 2018
WCCC 1995	Jul 12, 2017
WCCC 1999	Jul 13, 2017
WChess	Jan 7, 2016
Wilhelm	Oct 6, 2015
Windows	Nov 2, 2017
WMCCC 1986	Jan 7, 2016
WMCCC 1989	Oct 27, 2016
WMCCC 1990	Oct 27, 2016
WMCCC 1991	Sep 18, 2016
WMCCC 1993	Dec 30, 2017
WMCCC 1995	Jan 3, 2018
WMCCC 1996	Sep 15, 2016
WMCCC 1997	Apr 4, 2017
WMCCC 2000	Feb 27, 2018
Word	Jan 25, 2015
x86	Jan 4, 2018
x86-64	Mar 6, 2018
XOP	Aug 8, 2017
YChess	Feb 25, 2018
Zugzwang (Program)	Dec 19, 2016

Up one Level

Wikispaces : chessprogramming - items matching description

AVX

Table of Contents

Advantages of AVX

AVX on non-Intel CPUs

Mixing AVX and SSE

AVX2

See also

Manuals

External Links

References

What links here?

AVX-512

Table of Contents

Extensions

Selected Instructions

VPTERNLOG

VPLZCNT

VPOPCNT

See also

Manuals

External Links

Blog Postings

Compiler Support

References

What links here?

Bitboard Serialization

Table of Contents

Isolating Subsets

Single Bits

Multiple Bits

Converting Sets to Lists

Square Index Serialization

Scanning Forward

Scanning Reverse

Scanning with Reset

Intrinsic Version

Black or White

STL Iterator

Hashing Multiple Bits

See also

Forum Posts

External Links

References

What links here?

BitScan

Table of Contents

Hardware vs. Software

Non Empty Sets

Bitscan forward

Trailing Zero Count

De Bruijn Multiplication

With isolated LS1B

With separated LS1B

Matt Taylor's Folding trick

Walter Faxon's magic Bitscan

Bitscan by Modulo

Divide and Conquer

Double conversion of LS1B

Index of LS1B by Popcount

Bitscan reverse

Divide and Conquer

Tribute to Frank Zappa

De Bruijn Multiplication

Double conversion

Leading Zero Count

Bitscan versus Zero Count

Bitscan with Reset

Generalized Bitscan

Processor Instructions for Bitscans

x86

Emulating Intrinsics

Intrinsics versus asm

Bsf/Bsr x86-64 Timings

Bsf/Bsr behavior with zero source

ARM

Engine Samples

See also

Publications

Forum Posts