1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
|
/* Sjaak, a program for playing chess variants
* Copyright (C) 2011 Evert Glebbeek
*
* This program is free software: you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation, either version 3 of the License, or
* (at your option) any later version.
*
* This program is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* GNU General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program. If not, see <http://www.gnu.org/licenses/>.
*/
#ifndef BITS64_H
#define BITS64_H
#include <stdint.h>
#include "bool.h"
#if defined _MSC_VER
# include <intrin.h>
# if !defined _M_AMD64 && !defined _M_X64
inline void _BitScanForward64(unsigned long *res, uint64_t b)
{
unsigned __int32 l, h;
l = uint32_t(b & 0xffffffffu);
h = uint32_t(b >> 32);
if (l) {
_BitScanForward(res, l);
} else {
_BitScanForward(res, h);
*res += 32;
}
}
inline void _BitScanReverse64(unsigned long *res, uint64_t b)
{
unsigned __int32 l, h;
l = uint32_t(b & 0xffffffffu);
h = uint32_t(b >> 32);
if (h) {
_BitScanReverse(res, h);
*res += 32;
} else {
_BitScanReverse(res, l);
}
}
#endif
#endif
static inline bool onebit64(uint64_t x)
{
return (x & (x-1)) == 0;
}
static inline int bitscan64(uint64_t x) {
#ifdef __GNUC__
return __builtin_ctzll (x);
#elif defined _MSC_VER
unsigned long res;
_BitScanForward64(&res, x);
return (int)res;
#else
int i = 0;
assert(x);
while (!(x & 1)) {
i++;
x >>= 1;
}
return i;
#endif
}
static inline int lsb64(uint64_t x) {
#ifdef __GNUC__
return __builtin_ctzll (x);
#elif defined _MSC_VER
unsigned long res;
_BitScanForward64(&res, x);
return (int)res;
#else
int n = 0;
assert(x);
while ((x&((uint64_t)1<<n)) == 0) n++;
return n;
#endif
}
static inline int msb64(uint64_t x) {
#ifdef __GNUC__
return 63 - __builtin_clzll (x);
#elif defined _MSC_VER
unsigned long res;
_BitScanReverse64(&res, x);
return (int)res;
#else
int n = 63;
assert(x);
while ((x&((uint64_t)1<<n)) == 0) n--;
return n;
#endif
}
static inline uint64_t sshift64(uint64_t x, int s)
{
signed char left = (signed char) s;
signed char right = -((signed char)(s >> 8) & left);
return (x >> right) << (right + left);
}
static inline int bitscan16(uint16_t x) {
#ifdef __GNUC__
return __builtin_ctz (x);
#elif defined _MSC_VER
unsigned long res;
_BitScanForward(&res, x);
return res;
#else
int i = 0;
assert(x);
while (!(x & 1)) {
i++;
x >>= 1;
}
return i;
#endif
}
/* Return the number of bits set on a bitboard
* From http://chessprogramming.wikispaces.com/Population+Count
*/
static inline int popcount64(uint64_t x)
{
#ifdef __GNUC__
return __builtin_popcountll(x);
#else
const uint64_t k1 = 0x5555555555555555ll;
const uint64_t k2 = 0x3333333333333333ll;
const uint64_t k4 = 0x0f0f0f0f0f0f0f0fll;
const uint64_t kf = 0x0101010101010101ll;
x = x - ((x >> 1) & k1);
x = (x & k2) + ((x >> 2) & k2);
x = (x + (x >> 4)) & k4;
x = (x * kf) >> 56;
return (int) x;
#endif
}
#endif
|
