📄 bitboard infrastructure.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0053)http://wwwipd.ira.uka.de/Tichy/DarkThought/node7.html -->
<!--Converted with LaTeX2HTML 98.1p1 release (March 2nd, 1998)originally by Nikos Drakos (nikos@cbl.leeds.ac.uk), CBLU, University of Leeds* revised and updated by: Marcus Hennecke, Ross Moore, Herb Swan* with significant contributions from: Jens Lippmann, Marek Rouchal, Martin Wilck and others --><HTML><HEAD><TITLE>Bitboard Infrastructure</TITLE>
<META content="Bitboard Infrastructure" name=description>
<META content=dt name=keywords>
<META content=document name=resource-type>
<META content=global name=distribution>
<META content="text/html; charset=iso-8859-1" http-equiv=Content-Type><LINK
href="Bitboard Infrastructure.files/dt.css" rel=STYLESHEET>
<META content="MSHTML 5.00.2014.210" name=GENERATOR></HEAD>
<BODY>
<H3><A name=SECTION00124100000000000000> </A> <A
name=bboard-infra> </A> <BR>Bitboard Infrastructure </H3>
<P>D<SMALL>ARK</SMALL>T<SMALL>HOUGHT</SMALL> makes extensive use of bitboards
stored as 64bit unsigned integers where each bit represents a square of the
chess board numbered from a8 = 63 to h1 = 0. Because the bit
length of integers differs between compilers, machines, and operating systems,
D<SMALL>ARK</SMALL>T<SMALL>HOUGHT</SMALL> defines a set of portable data types
like <TT>unsigned<U> </U>8</TT>, ..., <TT>unsigned<U> </U>64</TT> that
are automatically mapped to the appropriate types of the target platform (e.g.
<TT>unsigned<U> </U>64</TT> defaults to <TT>unsigned long long</TT> in
GNU C).
<P>In order to simplify the handling of bitboards,
D<SMALL>ARK</SMALL>T<SMALL>HOUGHT</SMALL> contains an abundant collection of
functions and macros that provide efficient implementations of all the needed
bitboard operations. Beside the basic bitwise AND, OR, XOR etc. the collection
includes cascaded combinations thereof because they are frequently used and may
even be executed in one cycle on some machines. The expression <TT>(x
&</TT> ~<TT>y)</TT>,<A
href="http://wwwipd.ira.uka.de/Tichy/DarkThought/footnode.html#foot398"
name=tex2html17><SUP>1.2</SUP></A> for instance, corresponds to a single DEC
Alpha instruction. Other important bitboard operations enjoy marvelously simple
yet non-obvious formulations due to the wonders of binary subtraction and the
two's complement. Two famous members of this class are the expressions
<TT>(b & -b)</TT> which clears all but the least significant 1-bit
of a bitboard and <TT>(b & (b - 1))</TT> that clears
only the least significant 1-bit.
<P>Unfortunately, the central find-bit and population-count operations have
higher algorithmic complexity. Although a few CPUs like Motorola PowerPC, Sun
UltraSparc and the forthcoming DEC Alpha-21264 feature instruction-level support
of these operations, most current machines still require software
implementations. The efficiency of the implementations in terms of speed and
memory consumption is of crucial importance for bitboard-based chess programs
because it tends to limit their overall performance. In this respect, the short
expression for clearing the least significant 1-bit gives rise to a neat
formulation of an iterative population-count function.
<P><PRE>unsigned int iterative_popcount(unsigned_64 b) {
unsigned int n;
for (n = 0; b != 0; n++, b &= (b - 1));
return n;
}
</PRE>
<P>If the given bitboard contains few 1-bits, the loop terminates quickly thus
making this short and easily inlinable function run fast. Otherwise,
D<SMALL>ARK</SMALL>T<SMALL>HOUGHT</SMALL> prefers the following non-iterative
formulation that stems from the well-known ``Hacker's Memory'' collection of
programming tricks. It performs better than intuitive methods with lookup tables
because the tables get either too large or need too many lookups.<A
href="http://wwwipd.ira.uka.de/Tichy/DarkThought/footnode.html#foot405"
name=tex2html18><SUP>1.3</SUP></A>
<P><PRE>#define m1 ((unsigned_64) 0x5555555555555555)
#define m2 ((unsigned_64) 0x3333333333333333)
unsigned int non_iterative_popcount(const unsigned_64 b) {
unsigned_32 n;
const unsigned_64 a = b - ((b >> 1) & m1);
const unsigned_64 c = (a & m2) + ((a >> 2) & m2);
n = ((unsigned_32) c) + ((unsigned_32) (c >> 32));
n = (n & 0x0F0F0F0F) + ((n >> 4) & 0x0F0F0F0F);
n = (n & 0xFFFF) + (n >> 16);
n = (n & 0xFF) + (n >> 8);
return n;
}
</PRE>
<P>The idea of this population-count trick can also be applied to the find-bit
problem yielding a find-function without any memory accesses. Unfortunately,
however, this find-bit function is slower than fine-tuned table lookups. As
executed by D<SMALL>ARK</SMALL>T<SMALL>HOUGHT</SMALL> the lookups generate
negligible memory traffic and compile to roughly 15 machine instructions on a
DEC Alpha while relying on the conditional data-move capabilities of modern
CPUs. This clever find-bit implementation further exploits the fact that the
number of the least significant 1-bit of a bitboard is equal to the number of
the most significant 1-bit of the bitboard xor'ed with itself minus one:
<TT>FIND<U> </U>LSB(b)</TT> = <TT>FIND<U> </U>MSB(b ^ (b -
1))</TT>.
<P><BR>
<HR>
<ADDRESS>Created by <A href="mailto:heinze@ira.uka.de">Ernst A. Heinz</A>, Thu
Feb 4 14:12:12 MET 1999 </ADDRESS></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -