16#ifndef OR_TOOLS_UTIL_BITSET_H_
17#define OR_TOOLS_UTIL_BITSET_H_
43 const uint64 m1 = uint64_t{0x5555555555555555};
44 const uint64 m2 = uint64_t{0x3333333333333333};
45 const uint64 m4 = uint64_t{0x0F0F0F0F0F0F0F0F};
46 const uint64 h01 = uint64_t{0x0101010101010101};
48 n = (n & m2) + ((n >> 2) & m2);
49 n = (n + (n >> 4)) & m4;
54 n -= (n >> 1) & 0x55555555UL;
55 n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);
56 n = (n + (n >> 4)) & 0x0F0F0F0FUL;
59 return n & 0x0000003FUL;
70#define USE_DEBRUIJN true
71#if defined(__GNUC__) || defined(__llvm__)
72#define USE_FAST_LEAST_SIGNIFICANT_BIT true
75#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
76inline int LeastSignificantBitPosition64Fast(
uint64 n) {
77 return n == 0 ? 0 : __builtin_ctzll(n);
82 static const uint64 kSeq = uint64_t{0x0218a392dd5fb34f};
83 static const int kTab[64] = {
85 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,
86 5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,
87 63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,
88 62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,
90 return kTab[((n & (~n + 1)) * kSeq) >> 58];
96 if (n & 0x00000000FFFFFFFFLL) {
101 if (n & 0x000000000000FFFFLL) {
106 if (n & 0x00000000000000FFLL) {
111 if (n & 0x000000000000000FLL) {
116 if (n & 0x0000000000000003LL) {
121 if (n & 0x0000000000000001LL) {
129#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
130 return LeastSignificantBitPosition64Fast(n);
131#elif defined(USE_DEBRUIJN)
138#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
139inline int LeastSignificantBitPosition32Fast(
uint32 n) {
140 return n == 0 ? 0 : __builtin_ctzl(n);
145 static const uint32 kSeq = 0x077CB531U;
146 static const int kTab[32] = {
147 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
148 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
149 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
150 return kTab[((n & (~n + 1)) * kSeq) >> 27];
154 if (n == 0)
return 0;
156 if (n & 0x0000FFFFL) {
161 if (n & 0x000000FFL) {
166 if (n & 0x0000000FL) {
171 if (n & 0x00000003L) {
176 if (n & 0x00000001L) {
184#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
185 return LeastSignificantBitPosition32Fast(n);
186#elif defined(USE_DEBRUIJN)
194#if USE_FAST_LEAST_SIGNIFICANT_BIT
195inline int MostSignificantBitPosition64Fast(
uint64 n) {
198 const int offset = __builtin_clzll(1);
199 return n == 0 ? 0 : (offset - __builtin_clzll(n));
232#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
233 return MostSignificantBitPosition64Fast(n);
239#if USE_FAST_LEAST_SIGNIFICANT_BIT
240inline int MostSignificantBitPosition32Fast(
uint32 n) {
244 const int offset = __builtin_clzl(1);
245 return n == 0 ? 0 : (offset - __builtin_clzl(n));
274#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
275 return MostSignificantBitPosition32Fast(n);
282#undef USE_FAST_LEAST_SIGNIFICANT_BIT
409template <
typename IndexType =
int64>
412 Bitset64() : size_(), data_(), end_(*this, true) {}
414 : size_(Value(
size) > 0 ?
size : IndexType(0)),
419 IndexType
size()
const {
return size_; }
431 size_ = Value(
size) > 0 ?
size : IndexType(0);
438 size_ = Value(
size) > 0 ?
size : IndexType(0);
443 const size_t bit_length =
static_cast<size_t>(
BitLength64(Value(size_)));
444 const size_t to_clear =
std::min(data_.size(), bit_length);
445 data_.resize(bit_length, 0);
446 memset(data_.data(), 0, to_clear *
sizeof(
int64));
470 data_[
BitOffset64(Value(i))] &= ~TwoBitsFromPos64(Value(i));
509 data_[offset] = other.data_[offset];
515 template <
typename OtherIndexType>
517 const int64 min_size =
std::min(data_.size(), other.data_.size());
518 if (min_size == 0)
return;
519 const uint64 last_common_bucket = data_[min_size - 1];
520 memcpy(data_.data(), other.data_.data(), min_size *
sizeof(
uint64));
521 if (data_.size() >= other.data_.size()) {
524 data_[min_size - 1] &= ~bitmask;
525 data_[min_size - 1] |= (bitmask & last_common_bucket);
530 template <
typename OtherIndexType>
533 memcpy(data_.data(), other.data_.data(), data_.size() *
sizeof(
uint64));
540 const int min_size =
std::min(data_.size(), other.data_.size());
541 for (
int i = 0; i < min_size; ++i) {
542 data_[i] &= other.data_[i];
544 for (
int i = min_size; i < data_.size(); ++i) {
553 const int min_size =
std::min(data_.size(), other.data_.size());
554 for (
int i = 0; i < min_size; ++i) {
555 data_[i] |= other.data_[i];
566 : bitset_(data_), index_(0), base_index_(0), current_(0) {
567 if (bitset_.data_.empty()) {
570 current_ = bitset_.data_[0];
576 bool Ok()
const {
return index_ != -1; }
581 return IndexType(index_);
589 const int size = bitset_.data_.size();
592 }
while (bucket <
size && bitset_.data_[bucket] == 0);
593 if (bucket ==
size) {
597 current_ = bitset_.data_[bucket];
603 current_ &= current_ - 1;
608 : bitset_(data_), index_(0), base_index_(0), current_(0) {
609 if (at_end || bitset_.data_.empty()) {
612 current_ = bitset_.data_[0];
617 return index_ != other.index_;
619 IndexType
operator*()
const {
return IndexType(index_); }
644 DCHECK_EQ(data_.size(), other1.data_.size());
645 DCHECK_EQ(data_.size(), other2.data_.size());
646 DCHECK(use1 == 0 || use1 == 1);
647 DCHECK(use2 == 0 || use2 == 1);
650 data_[bucket] ^= ((1ull << pos) & data_[bucket]) ^
651 ((use1 << pos) & other1.data_[bucket]) ^
652 ((use2 << pos) & other2.data_[bucket]);
658 for (IndexType i(0); i <
size(); ++i) {
659 output +=
IsSet(i) ?
"1" :
"0";
670 std::vector<uint64> data_;
676 template <
class OtherIndexType>
687 : size_(size), top_(-1), data_(
BitLength64(size), 0) {}
713 int bucket_index =
static_cast<int>(
BitOffset64(i));
715 for (--bucket_index; bucket_index >= 0; --bucket_index) {
721 int Top()
const {
return top_; }
726 int bucket_index =
static_cast<int>(
BitOffset64(top_));
729 if (bucket_index == 0) {
733 bucket = data_[--bucket_index];
739 top_ =
static_cast<int>(
BitShift64(bucket_index) +
746 std::vector<uint64> data_;
751template <
typename IntType>
752inline int64 Bitset64<IntType>::Value(IntType
input)
const {
754 return input.value();
764template <
typename IntegerType =
int64>
769 IntegerType
size()
const {
return bitset_.size(); }
771 for (
const IntegerType i : to_clear_) bitset_.ClearBucket(i);
780 const int kSparseThreshold = 300;
781 if (to_clear_.size() * kSparseThreshold < size) {
783 bitset_.Resize(size);
785 bitset_.ClearAndResize(size);
790 if (size < bitset_.size()) {
792 for (IntegerType
index : to_clear_) {
794 to_clear_[new_index] =
index;
798 to_clear_.resize(new_index);
800 bitset_.Resize(size);
804 if (!bitset_[
index]) {
806 to_clear_.push_back(
index);
811 return to_clear_.size();
832 std::vector<IntegerType> to_clear_;
#define DCHECK_LE(val1, val2)
#define DCHECK_NE(val1, val2)
#define CHECK_GE(val1, val2)
#define DCHECK_GE(val1, val2)
#define DCHECK_LT(val1, val2)
#define DCHECK(condition)
#define DCHECK_EQ(val1, val2)
void IncreaseSize(int size)
void ClearAndResize(int size)
Iterator(const Bitset64 &data_)
Iterator(const Bitset64 &data_, bool at_end)
bool operator!=(const Iterator &other) const
IndexType operator*() const
void ClearAndResize(IndexType size)
void ClearBucket(IndexType i)
void Set(IndexType i, bool value)
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
void SetBitFromOtherBitSets(IndexType i, const Bitset64< IndexType > &other1, uint64 use1, const Bitset64< IndexType > &other2, uint64 use2)
void Union(const Bitset64< IndexType > &other)
std::string DebugString() const
void SetContentFromBitset(const Bitset64< OtherIndexType > &other)
void Intersection(const Bitset64< IndexType > &other)
void Resize(IndexType size)
bool IsSet(IndexType i) const
void ClearTwoBits(IndexType i)
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
bool operator[](IndexType i) const
bool AreOneOfTwoBitsSet(IndexType i) const
void PushBack(bool value)
SparseBitset(IntegerType size)
void Set(IntegerType index)
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
int NumberOfSetCallsWithDifferentArguments() const
void Clear(IntegerType index)
void Resize(IntegerType size)
bool operator[](IntegerType index) const
void ClearAndResize(IntegerType size)
#define DISALLOW_COPY_AND_ASSIGN(TypeName)
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
int LeastSignificantBitPosition32DeBruijn(uint32 n)
int LeastSignificantBitPosition32(uint32 n)
int64 UnsafeLeastSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitShift64(uint64 v)
int MostSignificantBitPosition64Default(uint64 n)
bool IsBitSet32(const uint32 *const bitset, uint32 pos)
uint64 LeastSignificantBitWord64(uint64 n)
uint32 OneRange32(uint32 s, uint32 e)
uint64 BitLength64(uint64 size)
void SetBit64(uint64 *const bitset, uint64 pos)
uint64 IntervalUp64(uint64 s)
uint32 BitOffset32(uint32 pos)
bool IsBitSet64(const uint64 *const bitset, uint64 pos)
uint32 BitCount32(uint32 n)
int32 UnsafeLeastSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
int MostSignificantBitPosition64(uint64 n)
int LeastSignificantBitPosition64DeBruijn(uint64 n)
uint32 BitShift32(uint32 v)
static const uint64 kAllBitsButLsb64
void ClearBit64(uint64 *const bitset, uint64 pos)
int MostSignificantBitPosition32Default(uint32 n)
uint32 BitPos64(uint64 pos)
uint64 OneRange64(uint64 s, uint64 e)
uint32 BitCountRange32(const uint32 *const bitset, uint32 start, uint32 end)
static const uint32 kAllBits32
static const uint64 kAllBits64
int32 UnsafeMostSignificantBitPosition32(const uint32 *const bitset, uint32 start, uint32 end)
void ClearBit32(uint32 *const bitset, uint32 pos)
int MostSignificantBitPosition32(uint32 n)
uint32 BitPos32(uint32 pos)
uint64 BitOffset64(uint64 pos)
uint32 BitLength32(uint32 size)
int LeastSignificantBitPosition64(uint64 n)
uint64 TwoBitsFromPos64(uint64 pos)
uint32 IntervalDown32(uint32 s)
uint32 LeastSignificantBitWord32(uint32 n)
int LeastSignificantBitPosition64Default(uint64 n)
uint64 IntervalDown64(uint64 s)
uint64 BitCountRange64(const uint64 *const bitset, uint64 start, uint64 end)
uint64 BitCount64(uint64 n)
bool IsEmptyRange32(const uint32 *const bitset, uint32 start, uint32 end)
int LeastSignificantBitPosition32Default(uint32 n)
int64 UnsafeMostSignificantBitPosition64(const uint64 *const bitset, uint64 start, uint64 end)
void SetBit32(uint32 *const bitset, uint32 pos)
bool IsEmptyRange64(const uint64 *const bitset, uint64 start, uint64 end)
uint32 IntervalUp32(uint32 s)
static int input(yyscan_t yyscanner)