#include "bit.h"
#include "util.h"

Functions
DLL_API int	bit_count (unsigned long long b)
	Count the number of bits set to one in an unsigned long long. More...

int	bit_weighted_count (const unsigned long long v)
	count the number of discs, counting the corners twice. More...

DLL_API int	first_bit (unsigned long long b)
	Search the first bit set. More...

int	next_bit (unsigned long long *b)
	Search the next bit set. More...

DLL_API int	last_bit (unsigned long long b)
	Search the last bit set (same as log2()). More...

unsigned long long	transpose (unsigned long long b)
	Transpose the unsigned long long (symetry % A1-H8 diagonal). More...

unsigned long long	vertical_mirror (unsigned long long b)
	Mirror the unsigned long long (exchange the lines A - H, B - G, C - F & D - E.). More...

unsigned long long	horizontal_mirror (unsigned long long b)
	Mirror the unsigned long long (exchange the line 1 - 8, 2 - 7, 3 - 6 & 4 - 5). More...

unsigned short	bswap_short (unsigned short s)
	Swap bytes of a short (little <-> big endian). More...

unsigned int	bswap_int (unsigned int i)
	Mirror the unsigned int (little <-> big endian). More...

int	get_rand_bit (unsigned long long b, Random *r)
	Get a random set bit index. More...

void	bitboard_write (const unsigned long long b, FILE *f)
	Print an unsigned long long as a board. More...

Variables
const unsigned long long	X_TO_BIT []

const unsigned long long	NEIGHBOUR []

Detailed Description

Bitwise operations. Several algorithms manipulating bits are presented here. Quite often, a macro needs to be defined to chose between different flavors of the algorithm.

Date: 1998 - 2017

Author: Richard Delorme

Version: 4.4

Function Documentation

◆ bit_count()

DLL_API int bit_count ( unsigned long long b )

Count the number of bits set to one in an unsigned long long.

This is the classical popcount function. Since 2007, it is part of the instruction set of some modern CPU, (>= barcelona for AMD or >= nelhacem for Intel). Alternatively, a fast SWAR algorithm, adding bits in parallel is provided here. This function is massively used to count discs on the board, the mobility, or the stability.

Parameters

b	64-bit integer to count bits of.

Returns: the number of bits set.

◆ bit_weighted_count()

int bit_weighted_count ( const unsigned long long v )

count the number of discs, counting the corners twice.

This is a variation of the above algorithm to count the mobility and favour the corners. This function is useful for move sorting.

Parameters

v	64-bit integer to count bits of.

Returns: the number of bit set, counting the corners twice.

◆ bitboard_write()

void bitboard_write	(	const unsigned long long	b,
		FILE *	f
	)

Print an unsigned long long as a board.

Write a 64-bit long number as an Othello board.

Parameters

b	The unsigned long long.
f	Output stream.

◆ bswap_int()

unsigned int bswap_int ( unsigned int i )

Mirror the unsigned int (little <-> big endian).

Parameters

i	An unsigned int.

Returns: The mirrored int.

◆ bswap_short()

unsigned short bswap_short ( unsigned short s )

Swap bytes of a short (little <-> big endian).

Parameters

s	An unsigned short.

Returns: The mirrored short.

◆ first_bit()

DLL_API int first_bit ( unsigned long long b )

Search the first bit set.

On CPU with AMD64 or EMT64 instructions, a fast asm code is provided. Alternatively, a fast algorithm based on magic numbers is provided.

Parameters

b	64-bit integer.

Returns: the index of the first bit set.

◆ get_rand_bit()

int get_rand_bit	(	unsigned long long	b,
		Random *	r
	)

Get a random set bit index.

Parameters

b	The unsigned long long.
r	The pseudo-number generator.

Returns: a random bit index, or -1 if b value is zero.

◆ horizontal_mirror()

unsigned long long horizontal_mirror ( unsigned long long b )

Mirror the unsigned long long (exchange the line 1 - 8, 2 - 7, 3 - 6 & 4 - 5).

Parameters

b	An unsigned long long.

Returns: The mirrored unsigned long long.

◆ last_bit()

DLL_API int last_bit ( unsigned long long b )

Search the last bit set (same as log2()).

On CPU with AMD64 or EMT64 instructions, a fast asm code is provided. Alternatively, a fast algorithm based on magic numbers is provided.

Parameters

b	64-bit integer.

Returns: the index of the last bit set.

◆ next_bit()

int next_bit ( unsigned long long * b )

Search the next bit set.

In practice, clear the first bit set and search the next one.

Parameters

b	64-bit integer.

Returns: the index of the next bit set.

◆ transpose()

unsigned long long transpose ( unsigned long long b )

Transpose the unsigned long long (symetry % A1-H8 diagonal).

Parameters

b	An unsigned long long

Returns: The transposed unsigned long long.

◆ vertical_mirror()

unsigned long long vertical_mirror ( unsigned long long b )

Mirror the unsigned long long (exchange the lines A - H, B - G, C - F & D - E.).

Parameters

b	An unsigned long long

Returns: The mirrored unsigned long long.

Variable Documentation

◆ NEIGHBOUR

const unsigned long long NEIGHBOUR[]

Initial value:

= {
        0x0000000000000302ULL, 0x0000000000000705ULL, 0x0000000000000e0aULL, 0x0000000000001c14ULL,
        0x0000000000003828ULL, 0x0000000000007050ULL, 0x000000000000e0a0ULL, 0x000000000000c040ULL,
        0x0000000000030203ULL, 0x0000000000070507ULL, 0x00000000000e0a0eULL, 0x00000000001c141cULL,
        0x0000000000382838ULL, 0x0000000000705070ULL, 0x0000000000e0a0e0ULL, 0x0000000000c040c0ULL,
        0x0000000003020300ULL, 0x0000000007050700ULL, 0x000000000e0a0e00ULL, 0x000000001c141c00ULL,
        0x0000000038283800ULL, 0x0000000070507000ULL, 0x00000000e0a0e000ULL, 0x00000000c040c000ULL,
        0x0000000302030000ULL, 0x0000000705070000ULL, 0x0000000e0a0e0000ULL, 0x0000001c141c0000ULL,
        0x0000003828380000ULL, 0x0000007050700000ULL, 0x000000e0a0e00000ULL, 0x000000c040c00000ULL,
        0x0000030203000000ULL, 0x0000070507000000ULL, 0x00000e0a0e000000ULL, 0x00001c141c000000ULL,
        0x0000382838000000ULL, 0x0000705070000000ULL, 0x0000e0a0e0000000ULL, 0x0000c040c0000000ULL,
        0x0003020300000000ULL, 0x0007050700000000ULL, 0x000e0a0e00000000ULL, 0x001c141c00000000ULL,
        0x0038283800000000ULL, 0x0070507000000000ULL, 0x00e0a0e000000000ULL, 0x00c040c000000000ULL,
        0x0302030000000000ULL, 0x0705070000000000ULL, 0x0e0a0e0000000000ULL, 0x1c141c0000000000ULL,
        0x3828380000000000ULL, 0x7050700000000000ULL, 0xe0a0e00000000000ULL, 0xc040c00000000000ULL,
        0x0203000000000000ULL, 0x0507000000000000ULL, 0x0a0e000000000000ULL, 0x141c000000000000ULL,
        0x2838000000000000ULL, 0x5070000000000000ULL, 0xa0e0000000000000ULL, 0x40c0000000000000ULL,
        0, 0 
}

Conversion array: neighbour bits

◆ X_TO_BIT

const unsigned long long X_TO_BIT[]

Initial value:

= {
        0x0000000000000001ULL, 0x0000000000000002ULL, 0x0000000000000004ULL, 0x0000000000000008ULL,
        0x0000000000000010ULL, 0x0000000000000020ULL, 0x0000000000000040ULL, 0x0000000000000080ULL,
        0x0000000000000100ULL, 0x0000000000000200ULL, 0x0000000000000400ULL, 0x0000000000000800ULL,
        0x0000000000001000ULL, 0x0000000000002000ULL, 0x0000000000004000ULL, 0x0000000000008000ULL,
        0x0000000000010000ULL, 0x0000000000020000ULL, 0x0000000000040000ULL, 0x0000000000080000ULL,
        0x0000000000100000ULL, 0x0000000000200000ULL, 0x0000000000400000ULL, 0x0000000000800000ULL,
        0x0000000001000000ULL, 0x0000000002000000ULL, 0x0000000004000000ULL, 0x0000000008000000ULL,
        0x0000000010000000ULL, 0x0000000020000000ULL, 0x0000000040000000ULL, 0x0000000080000000ULL,
        0x0000000100000000ULL, 0x0000000200000000ULL, 0x0000000400000000ULL, 0x0000000800000000ULL,
        0x0000001000000000ULL, 0x0000002000000000ULL, 0x0000004000000000ULL, 0x0000008000000000ULL,
        0x0000010000000000ULL, 0x0000020000000000ULL, 0x0000040000000000ULL, 0x0000080000000000ULL,
        0x0000100000000000ULL, 0x0000200000000000ULL, 0x0000400000000000ULL, 0x0000800000000000ULL,
        0x0001000000000000ULL, 0x0002000000000000ULL, 0x0004000000000000ULL, 0x0008000000000000ULL,
        0x0010000000000000ULL, 0x0020000000000000ULL, 0x0040000000000000ULL, 0x0080000000000000ULL,
        0x0100000000000000ULL, 0x0200000000000000ULL, 0x0400000000000000ULL, 0x0800000000000000ULL,
        0x1000000000000000ULL, 0x2000000000000000ULL, 0x4000000000000000ULL, 0x8000000000000000ULL,
        0, 0 
}

coordinate to bit table converter

Functions

Variables

Detailed Description

Function Documentation

◆ bit_count()

◆ bit_weighted_count()

◆ bitboard_write()

◆ bswap_int()

◆ bswap_short()

◆ first_bit()

◆ get_rand_bit()

◆ horizontal_mirror()

◆ last_bit()

◆ next_bit()

◆ transpose()

◆ vertical_mirror()

Variable Documentation

◆ NEIGHBOUR

◆ X_TO_BIT