Go to the documentation of this file.
47 #pragma intrinsic(_BitScanForward)
48 #pragma intrinsic(__popcnt)
49 #define GECODE_SUPPORT_MSVC_32
52 #if defined(_M_X64) || defined(_M_IA64)
53 #pragma intrinsic(_BitScanForward64)
54 #pragma intrinsic(__popcnt64)
55 #define GECODE_SUPPORT_MSVC_64
60 namespace Gecode {
namespace Support {
68 #if defined(GECODE_SUPPORT_MSVC_32)
69 typedef unsigned long int Base;
72 typedef unsigned long long int Base;
79 static const unsigned int bpb =
80 static_cast<unsigned int>(CHAR_BIT *
sizeof(
Base));
82 void init(
bool setbits=
false);
84 static unsigned int data(
unsigned int s);
88 bool get(
unsigned int i)
const;
90 void set(
unsigned int i);
92 void clear(
unsigned int i);
94 unsigned int next(
unsigned int i=0U)
const;
98 bool all(
unsigned int i)
const;
100 bool none(
void)
const;
102 bool none(
unsigned int i)
const;
104 unsigned int ones(
void)
const;
106 unsigned int zeroes(
void)
const;
108 bool one(
void)
const;
162 void init(A&
a,
unsigned int sz,
bool setbits=
false);
164 void clearall(
unsigned int sz,
bool setbits=
false);
168 bool get(
unsigned int i)
const;
170 void set(
unsigned int i);
172 void clear(
unsigned int i);
174 unsigned int next(
unsigned int i)
const;
178 bool all(
unsigned int sz)
const;
180 bool none(
unsigned int sz)
const;
183 void resize(A&
a,
unsigned int sz,
unsigned int n,
bool setbits=
false);
186 void dispose(A&
a,
unsigned int sz);
204 BitSetBase(A&
a,
unsigned int s,
bool setbits=
false);
210 void init(A&
a,
unsigned int s,
bool setbits=
false);
216 unsigned int size(
void)
const;
218 bool get(
unsigned int i)
const;
220 void set(
unsigned int i);
222 void clear(
unsigned int i);
224 unsigned int next(
unsigned int i)
const;
228 bool all(
void)
const;
230 bool none(
void)
const;
233 void resize(A&
a,
unsigned int n,
bool setbits=
false);
247 bits = setbits ? ~static_cast<Base>(0) :
static_cast<Base>(0);
251 return s == 0 ? 0 : ((s-1) /
bpb + 1);
255 return (
bits >>
i) !=
static_cast<Base>(0U);
259 return (
bits & (
static_cast<Base>(1U) <<
i)) !=
static_cast<Base>(0U);
271 assert(
bits !=
static_cast<Base>(0));
272 #if defined(GECODE_SUPPORT_MSVC_32)
275 _BitScanForward(&
p,
bits >>
i);
276 return static_cast<unsigned int>(
p)+
i;
277 #elif defined(GECODE_SUPPORT_MSVC_64)
280 _BitScanForward64(&
p,
bits >>
i);
281 return static_cast<unsigned int>(
p)+
i;
282 #elif defined(GECODE_HAS_BUILTIN_FFSLL)
284 int p = __builtin_ffsll(
bits >>
i);
286 return static_cast<unsigned int>(
p-1)+
i;
295 return bits == ~static_cast<Base>(0U);
299 const Base mask = (
static_cast<Base>(1U) <<
i) -
static_cast<Base>(1U);
300 return (
bits & mask) == mask;
304 return bits ==
static_cast<Base>(0U);
308 const Base mask = (
static_cast<Base>(1U) <<
i) -
static_cast<Base>(1U);
309 return (
bits & mask) ==
static_cast<Base>(0U);
314 #if defined(GECODE_SUPPORT_MSVC_32)
316 return static_cast<unsigned int>(__popcnt(
bits));
317 #elif defined(GECODE_SUPPORT_MSVC_64)
319 return static_cast<unsigned int>(__popcnt64(
bits));
320 #elif defined(GECODE_HAS_BUILTIN_POPCOUNTLL)
322 return static_cast<unsigned int>(__builtin_popcountll(
bits));
324 const unsigned long long int m1 = 0x5555555555555555;
325 const unsigned long long int m2 = 0x3333333333333333;
326 const unsigned long long int m4 = 0x0f0f0f0f0f0f0f0f;
327 unsigned long long int b =
bits;
329 b = (
b & m2) + ((
b >> 2) & m2);
330 b = (
b + (
b >> 4)) & m4;
331 b +=
b >> 8;
b +=
b >> 16;
b +=
b >> 32;
332 return static_cast<unsigned int>(
b & 0x7f);
342 static_cast<Base>(0U);
351 const Base mask = (
static_cast<Base>(1U) <<
i) -
static_cast<Base>(1U);
352 bits &= (
a.bits & mask);
357 ab.
bits =
a.bits &
b.bits;
367 const Base mask = (
static_cast<Base>(1U) <<
i) -
static_cast<Base>(1U);
368 bits |= (
a.bits & mask);
373 ab.
bits =
a.bits |
b.bits;
385 return bits ==
a.bits;
389 return bits !=
a.bits;
421 for (
unsigned int i=(sz%
bpb);
i<
bpb;
i++)
463 assert(
data == NULL);
470 assert(
data == NULL);
493 unsigned int bit =
i %
bpb;
505 unsigned int pos = sz /
bpb;
506 unsigned int bits = sz %
bpb;
509 for (
unsigned int i=1;
i<
pos;
i++)
514 for (
unsigned int i=1;
i<
pos;
i++)
628 #ifdef GECODE_SUPPORT_MSVC_32
629 #undef GECODE_SUPPORT_MSVC_32
631 #ifdef GECODE_SUPPORT_MSVC_64
632 #undef GECODE_SUPPORT_MSVC_64
static unsigned int data(unsigned int s)
Get number of data elements for s bits.
unsigned int zeroes(void) const
Return the number of bits not set.
void init(A &a, unsigned int s, bool setbits=false)
Initialize for s bits and allocator a (only after default constructor)
void set(unsigned int i)
Set bit i.
void a(BitSetData a)
Perform "and" with a.
Basic bitset support (without stored size information)
RawBitSetBase(void)
Default constructor (yields empty set)
BitSetBase(void)
Default constructor (yields empty set)
BitSetStatus
Status of a bitset.
BitSetStatus status(unsigned int sz) const
Return status of bitset.
void clearall(unsigned int sz, bool setbits=false)
Clear sz bits.
bool operator!=(BitSetData a) const
Check if bits are not the same as for a.
bool all(void) const
Test whether all bits are set.
BitSetData * data
Stored bits.
bool operator==(BitSetData a) const
Check if bits are the same as for a.
void o(BitSetData a)
Perform "or" with a.
unsigned long long int Base
Basetype for bits.
bool one(void) const
Check whether exactly one bit is set.
BitSetStatus status(void) const
Return status of bitset.
unsigned int next(unsigned int i=0U) const
Return next set bit with position greater or equal to i (there must be a bit)
bool all(void) const
Whether all bits are set.
Gecode toplevel namespace
void clear(unsigned int i)
Clear bit i.
static const unsigned int bpb
Bits per base.
bool none(void) const
Whether no bits are set.
void clear(unsigned int i)
Clear bit i.
void clearall(bool setbits=false)
Clear sz bits.
bool get(unsigned int i) const
Access value at bit i.
void copy(const BitSetBase &bs)
Copy sz bits from bs.
void init(A &a, unsigned int sz, bool setbits=false)
Initialize for sz bits and allocator a (only after default constructor)
struct Gecode::@602::NNF::@65::@66 b
For binary nodes (and, or, eqv)
static const unsigned int bpb
Bits per base.
unsigned int size(void) const
Return size of bitset (number of bits)
void set(unsigned int i)
Set bit i.
struct Gecode::@602::NNF::@65::@67 a
For atomic nodes.
bool get(unsigned int i) const
Access value at bit i.
void dispose(A &a, unsigned int sz)
Dispose memory for bit set.
void copy(unsigned int sz, const RawBitSetBase &bs)
Copy sz bits from bs.
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size)
void resize(A &a, unsigned int sz, unsigned int n, bool setbits=false)
Resize bitset from sz to n elememts.
void allocate(A &a, unsigned int sz)
Allocate for sz bits and allocator a (only after default constructor)
void set(unsigned int i)
Set bit i.
void clear(unsigned int i)
Clear bit i.
bool none(void) const
Test whether no bits are set.
void dispose(A &a)
Dispose memory for bit set.
@ BSS_SOME
Some but not all bits set.
int n
Number of negative literals for node type.
void resize(A &a, unsigned int n, bool setbits=false)
Resize bitset to n elememts.
unsigned int next(unsigned int i) const
Return position greater or equal i of next set bit (i is allowed to be equal to size)
bool all(unsigned int sz) const
Test whether all bits are set.
Gecode::IntArgs i({1, 2, 3, 4})
bool pos(const View &x)
Test whether x is postive.
unsigned int sz
Size of bitset (number of bits)
void init(bool setbits=false)
Initialize with all bits set if setbits.
bool get(unsigned int i) const
Access value at bit i.
unsigned int ones(void) const
Return the number of bits set.
int p
Number of positive literals for node type.
bool none(unsigned int sz) const
Test whether no bits are set.
bool operator()(unsigned int i=0U) const
Test wether any bit with position greater or equal to i is set.
BitSetData operator~(void) const
Invert all bits in b.