Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
bitset.h
Go to the documentation of this file.
1// Copyright 2010-2025 Google LLC
2// Licensed under the Apache License, Version 2.0 (the "License");
3// you may not use this file except in compliance with the License.
4// You may obtain a copy of the License at
5//
6// http://www.apache.org/licenses/LICENSE-2.0
7//
8// Unless required by applicable law or agreed to in writing, software
9// distributed under the License is distributed on an "AS IS" BASIS,
10// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
11// See the License for the specific language governing permissions and
12// limitations under the License.
13
14// Various utility functions on bitsets.
15
16#ifndef OR_TOOLS_UTIL_BITSET_H_
17#define OR_TOOLS_UTIL_BITSET_H_
18
19#include <string.h>
20
21#include <algorithm>
22#include <cstddef>
23#include <cstdint>
24#include <iterator>
25#include <string>
26#include <tuple>
27#include <vector>
28
29#include "absl/log/check.h"
30
31namespace operations_research {
32
33// Basic bit operations
34
35// Useful constants: word and double word will all bits set.
36static const uint64_t kAllBits64 = uint64_t{0xFFFFFFFFFFFFFFFF};
37static const uint64_t kAllBitsButLsb64 = uint64_t{0xFFFFFFFFFFFFFFFE};
38static const uint32_t kAllBits32 = 0xFFFFFFFFU;
39
40// Returns a word with only bit pos set.
41inline uint64_t OneBit64(int pos) { return uint64_t{1} << pos; }
42inline uint32_t OneBit32(int pos) { return 1U << pos; }
43
44// Returns the number of bits set in n.
45inline uint64_t BitCount64(uint64_t n) {
46 const uint64_t m1 = uint64_t{0x5555555555555555};
47 const uint64_t m2 = uint64_t{0x3333333333333333};
48 const uint64_t m4 = uint64_t{0x0F0F0F0F0F0F0F0F};
49 const uint64_t h01 = uint64_t{0x0101010101010101};
50 n -= (n >> 1) & m1;
51 n = (n & m2) + ((n >> 2) & m2);
52 n = (n + (n >> 4)) & m4;
53 n = (n * h01) >> 56;
54 return n;
55}
56inline uint32_t BitCount32(uint32_t n) {
57 n -= (n >> 1) & 0x55555555UL;
58 n = (n & 0x33333333) + ((n >> 2) & 0x33333333UL);
59 n = (n + (n >> 4)) & 0x0F0F0F0FUL;
60 n = n + (n >> 8);
61 n = n + (n >> 16);
62 return n & 0x0000003FUL;
63}
64
65// Returns a word with only the least significant bit of n set.
66inline uint64_t LeastSignificantBitWord64(uint64_t n) { return n & ~(n - 1); }
67inline uint32_t LeastSignificantBitWord32(uint32_t n) { return n & ~(n - 1); }
68
69// Returns the least significant bit position in n.
70// Discussion around lsb computation:
71// De Bruijn is almost as fast as the bsr/bsf-instruction-based intrinsics.
72// Both are always much faster than the Default algorithm.
73#define USE_DEBRUIJN true // if true, use de Bruijn bit forward scanner.
74#if defined(__GNUC__) || defined(__llvm__)
75#define USE_FAST_LEAST_SIGNIFICANT_BIT true // if true, use fast lsb.
76#endif
77
78#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
79inline int LeastSignificantBitPosition64Fast(uint64_t n) {
80 return __builtin_ctzll(n);
81}
82#endif
83
85 static const uint64_t kSeq = uint64_t{0x0218a392dd5fb34f};
86 static const int kTab[64] = {
87 // initialized by 'kTab[(kSeq << i) >> 58] = i
88 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 52, 20, 58,
89 5, 17, 26, 56, 15, 38, 29, 40, 10, 49, 53, 31, 21, 34, 59, 42,
90 63, 6, 12, 18, 24, 27, 51, 57, 16, 55, 37, 39, 48, 30, 33, 41,
91 62, 11, 23, 50, 54, 36, 47, 32, 61, 22, 35, 46, 60, 45, 44, 43,
92 };
93 return kTab[((n & (~n + 1)) * kSeq) >> 58];
94}
95
97 DCHECK_NE(n, 0);
98 int pos = 63;
99 if (n & 0x00000000FFFFFFFFLL) {
100 pos -= 32;
101 } else {
102 n >>= 32;
103 }
104 if (n & 0x000000000000FFFFLL) {
105 pos -= 16;
106 } else {
107 n >>= 16;
108 }
109 if (n & 0x00000000000000FFLL) {
110 pos -= 8;
111 } else {
112 n >>= 8;
113 }
114 if (n & 0x000000000000000FLL) {
115 pos -= 4;
116 } else {
117 n >>= 4;
118 }
119 if (n & 0x0000000000000003LL) {
120 pos -= 2;
121 } else {
122 n >>= 2;
123 }
124 if (n & 0x0000000000000001LL) {
125 pos -= 1;
126 }
127 return pos;
128}
129
130inline int LeastSignificantBitPosition64(uint64_t n) {
131 DCHECK_NE(n, 0);
132#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
133 return LeastSignificantBitPosition64Fast(n);
134#elif defined(USE_DEBRUIJN)
136#else
138#endif
139}
140
141#if defined(USE_FAST_LEAST_SIGNIFICANT_BIT)
142inline int LeastSignificantBitPosition32Fast(uint32_t n) {
143 return __builtin_ctzl(n);
144}
145#endif
146
148 static const uint32_t kSeq = 0x077CB531U; // de Bruijn sequence
149 static const int kTab[32] = {// initialized by 'kTab[(kSeq << i) >> 27] = i
150 0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20,
151 15, 25, 17, 4, 8, 31, 27, 13, 23, 21, 19,
152 16, 7, 26, 12, 18, 6, 11, 5, 10, 9};
153 return kTab[((n & (~n + 1)) * kSeq) >> 27];
154}
155
157 DCHECK_NE(n, 0);
158 int pos = 31;
159 if (n & 0x0000FFFFL) {
160 pos -= 16;
161 } else {
162 n >>= 16;
163 }
164 if (n & 0x000000FFL) {
165 pos -= 8;
166 } else {
167 n >>= 8;
168 }
169 if (n & 0x0000000FL) {
170 pos -= 4;
171 } else {
172 n >>= 4;
173 }
174 if (n & 0x00000003L) {
175 pos -= 2;
176 } else {
177 n >>= 2;
178 }
179 if (n & 0x00000001L) {
180 pos -= 1;
181 }
182 return pos;
183}
184
185inline int LeastSignificantBitPosition32(uint32_t n) {
186 DCHECK_NE(n, 0);
187#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
188 return LeastSignificantBitPosition32Fast(n);
189#elif defined(USE_DEBRUIJN)
191#else
193#endif
194}
195
196// Returns the most significant bit position in n.
197#if USE_FAST_LEAST_SIGNIFICANT_BIT
198inline int MostSignificantBitPosition64Fast(uint64_t n) {
199 // __builtin_clzll(1) should always return 63. There is no penalty in
200 // using offset, and the code looks more like its uint32_t counterpart.
201 const int offset = __builtin_clzll(1);
202 return n == 0 ? 0 : (offset - __builtin_clzll(n));
203}
204#endif
205
207 int b = 0;
208 if (0 != (n & (kAllBits64 << (1 << 5)))) {
209 b |= (1 << 5);
210 n >>= (1 << 5);
211 }
212 if (0 != (n & (kAllBits64 << (1 << 4)))) {
213 b |= (1 << 4);
214 n >>= (1 << 4);
215 }
216 if (0 != (n & (kAllBits64 << (1 << 3)))) {
217 b |= (1 << 3);
218 n >>= (1 << 3);
219 }
220 if (0 != (n & (kAllBits64 << (1 << 2)))) {
221 b |= (1 << 2);
222 n >>= (1 << 2);
223 }
224 if (0 != (n & (kAllBits64 << (1 << 1)))) {
225 b |= (1 << 1);
226 n >>= (1 << 1);
227 }
228 if (0 != (n & (kAllBits64 << (1 << 0)))) {
229 b |= (1 << 0);
230 }
231 return b;
232}
233
234inline int MostSignificantBitPosition64(uint64_t n) {
235#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
236 return MostSignificantBitPosition64Fast(n);
237#else
239#endif
240}
241
242#if USE_FAST_LEAST_SIGNIFICANT_BIT
243inline int MostSignificantBitPosition32Fast(uint32_t n) {
244 // The constant here depends on whether we are on a 32-bit or 64-bit machine.
245 // __builtin_clzl(1) returns 63 on a 64-bit machine and 31 on a 32-bit
246 // machine.
247 const int offset = __builtin_clzl(1);
248 return n == 0 ? 0 : (offset - __builtin_clzl(n));
249}
250#endif
251
253 int b = 0;
254 if (0 != (n & (kAllBits32 << (1 << 4)))) {
255 b |= (1 << 4);
256 n >>= (1 << 4);
257 }
258 if (0 != (n & (kAllBits32 << (1 << 3)))) {
259 b |= (1 << 3);
260 n >>= (1 << 3);
261 }
262 if (0 != (n & (kAllBits32 << (1 << 2)))) {
263 b |= (1 << 2);
264 n >>= (1 << 2);
265 }
266 if (0 != (n & (kAllBits32 << (1 << 1)))) {
267 b |= (1 << 1);
268 n >>= (1 << 1);
269 }
270 if (0 != (n & (kAllBits32 << (1 << 0)))) {
271 b |= (1 << 0);
272 }
273 return b;
274}
275
276inline int MostSignificantBitPosition32(uint32_t n) {
277#ifdef USE_FAST_LEAST_SIGNIFICANT_BIT
278 return MostSignificantBitPosition32Fast(n);
279#else
281#endif
282}
283
284#undef USE_DEBRUIJN
285#undef USE_FAST_LEAST_SIGNIFICANT_BIT
286
287// Returns a word with bits from s to e set.
288inline uint64_t OneRange64(uint64_t s, uint64_t e) {
289 DCHECK_LE(s, 63);
290 DCHECK_LE(e, 63);
291 DCHECK_LE(s, e);
292 return (kAllBits64 << s) ^ ((kAllBits64 - 1) << e);
293}
294
295inline uint32_t OneRange32(uint32_t s, uint32_t e) {
296 DCHECK_LE(s, 31);
297 DCHECK_LE(e, 31);
298 DCHECK_LE(s, e);
299 return (kAllBits32 << s) ^ ((kAllBits32 - 1) << e);
300}
301
302// Returns a word with s least significant bits unset.
303inline uint64_t IntervalUp64(uint64_t s) {
304 DCHECK_LE(s, 63);
305 return kAllBits64 << s;
306}
307
308inline uint32_t IntervalUp32(uint32_t s) {
309 DCHECK_LE(s, 31);
310 return kAllBits32 << s;
311}
312
313// Returns a word with the s most significant bits unset.
314inline uint64_t IntervalDown64(uint64_t s) {
315 DCHECK_LE(s, 63);
316 return kAllBits64 >> (63 - s);
317}
318
319inline uint32_t IntervalDown32(uint32_t s) {
320 DCHECK_LE(s, 31);
321 return kAllBits32 >> (31 - s);
322}
323
324// ----- Bitset operators -----
325// Bitset: array of uint32_t/uint64_t words
326
327// Bit operators used to manipulates bitsets.
328
329// Returns the bit number in the word computed by BitOffsetXX,
330// corresponding to the bit at position pos in the bitset.
331// Note: '& 63' is faster than '% 64'
332// TODO(user): rename BitPos and BitOffset to something more understandable.
333inline uint32_t BitPos64(uint64_t pos) { return (pos & 63); }
334inline uint32_t BitPos32(uint32_t pos) { return (pos & 31); }
335
336// Returns the word number corresponding to bit number pos.
337inline uint64_t BitOffset64(uint64_t pos) { return (pos >> 6); }
338inline uint32_t BitOffset32(uint32_t pos) { return (pos >> 5); }
339
340// Returns the number of words needed to store size bits.
341inline uint64_t BitLength64(uint64_t size) { return ((size + 63) >> 6); }
342inline uint32_t BitLength32(uint32_t size) { return ((size + 31) >> 5); }
343
344// Returns the bit number in the bitset of the first bit of word number v.
345inline uint64_t BitShift64(uint64_t v) { return v << 6; }
346inline uint32_t BitShift32(uint32_t v) { return v << 5; }
347
348// Returns true if the bit pos is set in bitset.
349inline bool IsBitSet64(const uint64_t* const bitset, uint64_t pos) {
350 return (bitset[BitOffset64(pos)] & OneBit64(BitPos64(pos)));
351}
352inline bool IsBitSet32(const uint32_t* const bitset, uint32_t pos) {
353 return (bitset[BitOffset32(pos)] & OneBit32(BitPos32(pos)));
354}
355
356// Sets the bit pos to true in bitset.
357inline void SetBit64(uint64_t* const bitset, uint64_t pos) {
358 bitset[BitOffset64(pos)] |= OneBit64(BitPos64(pos));
359}
360inline void SetBit32(uint32_t* const bitset, uint32_t pos) {
361 bitset[BitOffset32(pos)] |= OneBit32(BitPos32(pos));
362}
363
364// Sets the bit pos to false in bitset.
365inline void ClearBit64(uint64_t* const bitset, uint64_t pos) {
366 bitset[BitOffset64(pos)] &= ~OneBit64(BitPos64(pos));
367}
368inline void ClearBit32(uint32_t* const bitset, uint32_t pos) {
369 bitset[BitOffset32(pos)] &= ~OneBit32(BitPos32(pos));
370}
371
372// Returns the number of bits set in bitset between positions start and end.
373uint64_t BitCountRange64(const uint64_t* bitset, uint64_t start, uint64_t end);
374uint32_t BitCountRange32(const uint32_t* bitset, uint32_t start, uint32_t end);
375
376// Returns true if no bits are set in bitset between start and end.
377bool IsEmptyRange64(const uint64_t* bitset, uint64_t start, uint64_t end);
378bool IsEmptyRange32(const uint32_t* bitset, uint32_t start, uint32_t end);
379
380// Returns the first bit set in bitset between start and max_bit.
381int64_t LeastSignificantBitPosition64(const uint64_t* bitset, uint64_t start,
382 uint64_t end);
383int LeastSignificantBitPosition32(const uint32_t* bitset, uint32_t start,
384 uint32_t end);
385
386// Returns the last bit set in bitset between min_bit and start.
387int64_t MostSignificantBitPosition64(const uint64_t* bitset, uint64_t start,
388 uint64_t end);
389int MostSignificantBitPosition32(const uint32_t* bitset, uint32_t start,
390 uint32_t end);
391
392// Unsafe versions of the functions above where respectively end and start
393// are supposed to be set.
394int64_t UnsafeLeastSignificantBitPosition64(const uint64_t* bitset,
395 uint64_t start, uint64_t end);
396int32_t UnsafeLeastSignificantBitPosition32(const uint32_t* bitset,
397 uint32_t start, uint32_t end);
398
399int64_t UnsafeMostSignificantBitPosition64(const uint64_t* bitset,
400 uint64_t start, uint64_t end);
401int32_t UnsafeMostSignificantBitPosition32(const uint32_t* bitset,
402 uint32_t start, uint32_t end);
403
404// Returns a mask with the bits pos % 64 and (pos ^ 1) % 64 sets.
405inline uint64_t TwoBitsFromPos64(uint64_t pos) {
406 return uint64_t{3} << (pos & 62);
407}
408
409// This class is like an ITIVector<IndexType, bool> except that it provides a
410// more efficient way to iterate over the positions set to true. It achieves
411// this by caching the current uint64_t bucket in the Iterator and using
412// LeastSignificantBitPosition64() to iterate over the positions at 1 in this
413// bucket.
414template <typename IndexType = int64_t>
415class Bitset64 {
416 public:
417 using value_type = IndexType;
418
419 // When speed matter, caching the base pointer helps.
420 class ConstView {
421 public:
422 explicit ConstView(const Bitset64* bitset) : data_(bitset->data_.data()) {}
423
424 bool operator[](IndexType i) const {
425 return data_[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
426 }
427
428 const uint64_t* data() const { return data_; }
429
430 private:
431 const uint64_t* const data_;
432 };
433
434 class View {
435 public:
436 explicit View(Bitset64* bitset) : data_(bitset->data_.data()) {}
437
438 bool operator[](IndexType i) const {
439 return data_[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
440 }
441
442 void Clear(IndexType i) {
443 data_[BitOffset64(Value(i))] &= ~OneBit64(BitPos64(Value(i)));
444 }
445
446 void Set(IndexType i) {
447 data_[BitOffset64(Value(i))] |= OneBit64(BitPos64(Value(i)));
448 }
449
450 private:
451 uint64_t* const data_;
452 };
453
454 Bitset64() : size_(), data_() {}
455 explicit Bitset64(IndexType size)
456 : size_(Value(size) > 0 ? size : IndexType(0)),
457 data_(BitLength64(Value(size_))) {}
458
459 ConstView const_view() const { return ConstView(this); }
460 View view() { return View(this); }
461
462 // Returns how many bits this Bitset64 can hold.
463 IndexType size() const { return size_; }
464
465 // Appends value at the end of the bitset.
466 void PushBack(bool value) {
467 ++size_;
468 data_.resize(BitLength64(Value(size_)), 0);
469 Set(size_ - 1, value);
470 }
471
472 // Resizes the Bitset64 to the given number of bits. New bits are sets to 0.
473 void resize(int size) { Resize(IndexType(size)); }
474 void Resize(IndexType size) {
475 DCHECK_GE(Value(size), 0);
476 IndexType new_size = Value(size) > 0 ? size : IndexType(0);
477 if (new_size < size_ && Value(new_size) > 0) {
478 const int64_t new_data_size = BitLength64(Value(new_size));
479 const uint64_t bitmask = kAllBitsButLsb64
480 << BitPos64(Value(new_size) - 1);
481 data_[new_data_size - 1] &= ~bitmask;
482 }
483 size_ = new_size;
484 data_.resize(BitLength64(Value(size_)), 0);
485 }
486
487 // Changes the number of bits the Bitset64 can hold and set all of them to 0.
488 void ClearAndResize(IndexType size) {
489 DCHECK_GE(Value(size), 0);
490 size_ = Value(size) > 0 ? size : IndexType(0);
491
492 // Memset is 4x faster than data_.assign() as of 19/03/2014.
493 // TODO(user): Ideally if a realloc happens, we don't need to copy the old
494 // data...
495 const size_t bit_length = static_cast<size_t>(BitLength64(Value(size_)));
496 const size_t to_clear = std::min(data_.size(), bit_length);
497 data_.resize(bit_length, 0);
498 memset(data_.data(), 0, to_clear * sizeof(int64_t));
499 }
500
501 // Sets all bits to 0.
502 void ClearAll() { memset(data_.data(), 0, data_.size() * sizeof(int64_t)); }
503
504 // Sets the bit at position i to 0.
505 void Clear(IndexType i) {
506 DCHECK_GE(Value(i), 0);
507 DCHECK_LT(Value(i), Value(size_));
508 data_.data()[BitOffset64(Value(i))] &= ~OneBit64(BitPos64(Value(i)));
509 }
510
511 // Sets bucket containing bit i to 0.
512 void ClearBucket(IndexType i) {
513 DCHECK_GE(Value(i), 0);
514 DCHECK_LT(Value(i), Value(size_));
515 data_.data()[BitOffset64(Value(i))] = 0;
516 }
517
518 // Clears the bits at position i and i ^ 1.
519 void ClearTwoBits(IndexType i) {
520 DCHECK_GE(Value(i), 0);
521 DCHECK_LT(Value(i), Value(size_));
522 data_[BitOffset64(Value(i))] &= ~TwoBitsFromPos64(Value(i));
523 }
524
525 // Returns true if the bit at position i or the one at position i ^ 1 is set.
526 bool AreOneOfTwoBitsSet(IndexType i) const {
527 DCHECK_GE(Value(i), 0);
528 DCHECK_LT(Value(i), Value(size_));
529 return data_.data()[BitOffset64(Value(i))] & TwoBitsFromPos64(Value(i));
530 }
531
532 // Returns true if the bit at position i is set.
533 bool IsSet(IndexType i) const {
534 DCHECK_GE(Value(i), 0);
535 DCHECK_LT(Value(i), Value(size_));
536 return data_.data()[BitOffset64(Value(i))] & OneBit64(BitPos64(Value(i)));
537 }
538
539 // Same as IsSet().
540 bool operator[](IndexType i) const { return IsSet(i); }
541
542 // Sets the bit at position i to 1.
543 void Set(IndexType i) {
544 DCHECK_GE(Value(i), 0);
545 DCHECK_LT(Value(i), size_);
546 // The c++ hardening is costly here, so we disable it.
547 data_.data()[BitOffset64(Value(i))] |= OneBit64(BitPos64(Value(i)));
548 }
549
550 // If value is true, sets the bit at position i to 1, sets it to 0 otherwise.
551 void Set(IndexType i, bool value) {
552 if (value) {
553 Set(i);
554 } else {
555 Clear(i);
556 }
557 }
558
559 // Copies bucket containing bit i from "other" to "this".
560 void CopyBucket(const Bitset64<IndexType>& other, IndexType i) {
561 const uint64_t offset = BitOffset64(Value(i));
562 data_[offset] = other.data_[offset];
563 }
564
565 // Copies "other" to "this". The bitsets do not have to be of the same size.
566 // If "other" is smaller, high order bits are not changed. If "other" is
567 // larger, its high order bits are ignored. In any case "this" is not resized.
568 template <typename OtherIndexType>
570 const int64_t min_size = std::min(data_.size(), other.data_.size());
571 if (min_size == 0) return;
572 const uint64_t last_common_bucket = data_[min_size - 1];
573 memcpy(data_.data(), other.data_.data(), min_size * sizeof(uint64_t));
574 if (data_.size() >= other.data_.size()) {
575 const uint64_t bitmask = kAllBitsButLsb64
576 << BitPos64(other.Value(other.size() - 1));
577 data_[min_size - 1] &= ~bitmask;
578 data_[min_size - 1] |= (bitmask & last_common_bucket);
579 }
580 }
581
582 // Same as SetContentFromBitset where "this" and "other" have the same size.
583 template <typename OtherIndexType>
585 DCHECK_EQ(Value(size()), other.Value(other.size()));
586 memcpy(data_.data(), other.data_.data(), data_.size() * sizeof(uint64_t));
587 }
588
589 // Sets "this" to be the intersection of "this" and "other". The
590 // bitsets do not have to be the same size. If other is smaller, all
591 // the higher order bits are assumed to be 0.
593 const int min_size = std::min(data_.size(), other.data_.size());
594 uint64_t* const d = data_.data();
595 const uint64_t* const o = other.data_.data();
596 for (int i = 0; i < min_size; ++i) {
597 d[i] &= o[i];
598 }
599 for (int i = min_size; i < data_.size(); ++i) {
600 d[i] = 0;
601 }
602 }
603
604 // This one assume both given bitset to be of the same size.
606 const Bitset64<IndexType>& b) {
607 DCHECK_EQ(a.size(), b.size());
608 Resize(a.size());
609
610 // Copy buckets.
611 const int num_buckets = a.data_.size();
612 for (int i = 0; i < num_buckets; ++i) {
613 data_[i] = a.data_[i] & b.data_[i];
614 }
615 }
616
617 // Sets "this" to be the union of "this" and "other". The
618 // bitsets do not have to be the same size. If other is smaller, all
619 // the higher order bits are assumed to be 0.
620 void Union(const Bitset64<IndexType>& other) {
621 const int min_size = std::min(data_.size(), other.data_.size());
622 for (int i = 0; i < min_size; ++i) {
623 data_[i] |= other.data_[i];
624 }
625 }
626
627 // Class to iterate over the bit positions at 1 of a Bitset64.
628 //
629 // IMPORTANT: Because the iterator "caches" the current uint64_t bucket, this
630 // will probably not do what you want if Bitset64 is modified while iterating.
631 class Iterator {
632 public:
633 // Make this iterator a std::forward_iterator, so it works with std::sample,
634 // std::max_element, etc.
635 Iterator() : data_(nullptr), size_(0) {}
636 Iterator(Iterator&& other) = default;
637 Iterator(const Iterator& other) = default;
638 Iterator& operator=(const Iterator& other) = default;
639 using difference_type = std::ptrdiff_t;
640 using iterator_category = std::forward_iterator_tag;
641 using value_type = IndexType;
642 using size_type = std::size_t;
645
646 explicit Iterator(const Bitset64& bitset)
647 : data_(bitset.data_.data()), size_(bitset.data_.size()) {
648 if (!bitset.data_.empty()) {
649 current_ = data_[0];
650 this->operator++();
651 }
652 }
653
654 static Iterator EndIterator(const Bitset64& bitset) {
655 return Iterator(bitset.data_.data());
656 }
657
658 bool operator==(const Iterator& other) const { return !(*this != other); }
659 bool operator!=(const Iterator& other) const {
660 if (other.size_ == 0) {
661 return size_ != 0;
662 }
663 return std::tie(index_, current_) !=
664 std::tie(other.index_, other.current_);
665 }
666
667 IndexType operator*() const { return IndexType(index_); }
668
670 Iterator other = *this;
671 ++(*this);
672 return other;
673 }
674
676 int bucket = BitOffset64(index_);
677 while (current_ == 0) {
678 bucket++;
679 if (bucket == size_) {
680 size_ = 0;
681 return *this;
682 }
683 current_ = data_[bucket];
684 }
685
686 // Computes the index and clear the least significant bit of current_.
687 index_ = BitShift64(bucket) | LeastSignificantBitPosition64(current_);
688 current_ &= current_ - 1;
689 return *this;
690 }
691
692 private:
693 explicit Iterator(const uint64_t* data) : data_(data), size_(0) {}
694
695 const uint64_t* data_;
696 int size_;
697 int index_ = 0;
698 uint64_t current_ = 0;
699 };
700
701 // Allows range-based "for" loop on the non-zero positions:
702 // for (const IndexType index : bitset) {}
703 Iterator begin() const { return Iterator(*this); }
704 Iterator end() const { return Iterator::EndIterator(*this); }
705
706 // Cryptic function! This is just an optimized version of a given piece of
707 // code and has probably little general use.
708 static uint64_t ConditionalXorOfTwoBits(IndexType i, uint64_t use1,
710 uint64_t use2,
712 DCHECK(use1 == 0 || use1 == 1);
713 DCHECK(use2 == 0 || use2 == 1);
714 const int bucket = BitOffset64(Value(i));
715 const int pos = BitPos64(Value(i));
716 return ((use1 << pos) & set1.data()[bucket]) ^
717 ((use2 << pos) & set2.data()[bucket]);
718 }
719
720 // Returns a 0/1 string representing the bitset.
721 std::string DebugString() const {
722 std::string output;
723 for (IndexType i(0); i < size(); ++i) {
724 output += IsSet(i) ? "1" : "0";
725 }
726 return output;
727 }
728
729 bool IsAllFalse() const {
730 return std::all_of(data_.begin(), data_.end(),
731 [](uint64_t v) { return v == 0; });
732 }
733
734 private:
735 // Returns the value of the index type.
736 // This function is specialized below to work with IntType and int64_t.
737 static int Value(IndexType input);
738
739 IndexType size_;
740 std::vector<uint64_t> data_;
741
742 template <class OtherIndexType>
743 friend class Bitset64;
744};
745
746// Specialized version of Bitset64 that allows to query the last bit set more
747// efficiently.
749 public:
750 BitQueue64() : size_(), top_(-1), data_() {}
751 explicit BitQueue64(int size)
752 : size_(size), top_(-1), data_(BitLength64(size), 0) {}
753
754 // This type is neither copyable nor movable.
755 BitQueue64(const BitQueue64&) = delete;
756 BitQueue64& operator=(const BitQueue64&) = delete;
757
758 void IncreaseSize(int size) {
759 CHECK_GE(size, size_);
760 size_ = size;
761 data_.resize(BitLength64(size), 0);
762 }
763
764 void ClearAndResize(int size) {
765 top_ = -1;
766 size_ = size;
767 data_.assign(BitLength64(size), 0);
768 }
769
770 void Set(int i) {
771 DCHECK_GE(i, 0);
772 DCHECK_LT(i, size_);
773 top_ = std::max(top_, i);
774 data_[BitOffset64(i)] |= OneBit64(BitPos64(i));
775 }
776
777 // Sets all the bits from 0 up to i-1 to 1.
778 void SetAllBefore(int i) {
779 DCHECK_GE(i, 0);
780 DCHECK_LT(i, size_);
781 top_ = std::max(top_, i - 1);
782 int bucket_index = static_cast<int>(BitOffset64(i));
783 data_[bucket_index] |= OneBit64(BitPos64(i)) - 1;
784 for (--bucket_index; bucket_index >= 0; --bucket_index) {
785 data_[bucket_index] = kAllBits64;
786 }
787 }
788
789 // Returns the position of the highest bit set in O(1) or -1 if no bit is set.
790 int Top() const { return top_; }
791
792 // Clears the Top() bit and recomputes the position of the next Top().
793 void ClearTop() {
794 DCHECK_NE(top_, -1);
795 int bucket_index = static_cast<int>(BitOffset64(top_));
796 uint64_t bucket = data_[bucket_index] &= ~OneBit64(BitPos64(top_));
797 while (!bucket) {
798 if (bucket_index == 0) {
799 top_ = -1;
800 return;
801 }
802 bucket = data_[--bucket_index];
803 }
804
805 // Note(user): I experimented with reversing the bit order in a bucket to
806 // use LeastSignificantBitPosition64() and it is only slightly faster at the
807 // cost of a lower Set() speed. So I preferred this version.
808 top_ = static_cast<int>(BitShift64(bucket_index) +
810 }
811
812 private:
813 int size_;
814 int top_;
815 std::vector<uint64_t> data_;
816};
817
818// The specialization of Value() for IntType and int64_t.
819template <typename IntType>
820inline int Bitset64<IntType>::Value(IntType input) {
821 DCHECK_GE(input.value(), 0);
822 return input.value();
823}
824template <>
825inline int Bitset64<int>::Value(int input) {
826 DCHECK_GE(input, 0);
827 return input;
828}
829template <>
830inline int Bitset64<int64_t>::Value(int64_t input) {
831 DCHECK_GE(input, 0);
832 return input;
833}
834template <>
835inline int Bitset64<size_t>::Value(size_t input) {
836 return input;
837}
838
839// A simple utility class to set/unset integer in a range [0, size).
840// This is optimized for sparsity.
841template <typename IntegerType = int64_t>
843 public:
845 explicit SparseBitset(IntegerType size) : bitset_(size) {}
846
847 // This type is neither copyable nor movable.
848 SparseBitset(const SparseBitset&) = delete;
850 IntegerType size() const { return bitset_.size(); }
852 void ClearAndResize(IntegerType size) {
853 // As of 19/03/2014, experiments show that this is a reasonable threshold.
854 const int kSparseThreshold = 300;
855 if (to_clear_.size() * kSparseThreshold < size) {
856 for (const IntegerType i : to_clear_) bitset_.ClearBucket(i);
857 to_clear_.clear();
858 bitset_.Resize(size);
859 } else {
860 bitset_.ClearAndResize(size);
861 to_clear_.clear();
862 }
863 }
864 void Resize(IntegerType size) {
865 if (size < bitset_.size()) {
866 int new_index = 0;
867 for (IntegerType index : to_clear_) {
868 if (index < size) {
869 to_clear_[new_index] = index;
870 ++new_index;
871 }
872 }
873 to_clear_.resize(new_index);
874 }
875 bitset_.Resize(size);
876 }
877 bool operator[](IntegerType index) const { return bitset_[index]; }
878 void Set(IntegerType index) {
879 if (!bitset_[index]) {
880 bitset_.Set(index);
881 to_clear_.push_back(index);
882 }
883 }
884
885 // A bit hacky for really hot loop.
886 typename Bitset64<IntegerType>::View BitsetView() { return bitset_.view(); }
888 return bitset_.const_view();
889 }
890 void SetUnsafe(typename Bitset64<IntegerType>::View view, IntegerType index) {
891 view.Set(index);
892 to_clear_.push_back(index);
893 }
894
895 void Clear(IntegerType index) { bitset_.Clear(index); }
897 return to_clear_.size();
898 }
899 const std::vector<IntegerType>& PositionsSetAtLeastOnce() const {
900 return to_clear_;
901 }
902
903 // Tells the class that all its bits are cleared, so it can reset to_clear_
904 // to the empty vector. Note that this call is "unsafe" since the fact that
905 // the class is actually all cleared is only checked in debug mode.
906 //
907 // This is useful to iterate on the "set" positions while clearing them for
908 // instance. This way, after the loop, a client can call this for efficiency.
910#if !defined(NDEBUG)
911 for (IntegerType index : to_clear_) CHECK(!bitset_[index]);
912#endif
913 to_clear_.clear();
914 }
915
917 return bitset_.const_view();
918 }
919
920 private:
921 Bitset64<IntegerType> bitset_;
922 std::vector<IntegerType> to_clear_;
923};
924
925} // namespace operations_research
926
927#endif // OR_TOOLS_UTIL_BITSET_H_
int Top() const
Returns the position of the highest bit set in O(1) or -1 if no bit is set.
Definition bitset.h:790
void ClearAndResize(int size)
Definition bitset.h:764
void ClearTop()
Clears the Top() bit and recomputes the position of the next Top().
Definition bitset.h:793
BitQueue64(const BitQueue64 &)=delete
This type is neither copyable nor movable.
void IncreaseSize(int size)
Definition bitset.h:758
BitQueue64 & operator=(const BitQueue64 &)=delete
void SetAllBefore(int i)
Sets all the bits from 0 up to i-1 to 1.
Definition bitset.h:778
When speed matter, caching the base pointer helps.
Definition bitset.h:420
const uint64_t * data() const
Definition bitset.h:428
bool operator[](IndexType i) const
Definition bitset.h:424
ConstView(const Bitset64 *bitset)
Definition bitset.h:422
Iterator(const Iterator &other)=default
bool operator==(const Iterator &other) const
Definition bitset.h:658
bool operator!=(const Iterator &other) const
Definition bitset.h:659
std::forward_iterator_tag iterator_category
Definition bitset.h:640
Iterator(Iterator &&other)=default
Iterator & operator=(const Iterator &other)=default
static Iterator EndIterator(const Bitset64 &bitset)
Definition bitset.h:654
Iterator(const Bitset64 &bitset)
Definition bitset.h:646
bool operator[](IndexType i) const
Definition bitset.h:438
void CopyBucket(const Bitset64< IndexType > &other, IndexType i)
Copies bucket containing bit i from "other" to "this".
Definition bitset.h:560
void ClearAll()
Sets all bits to 0.
Definition bitset.h:502
void ClearBucket(IndexType i)
Sets bucket containing bit i to 0.
Definition bitset.h:512
void SetContentFromBitset(const Bitset64< OtherIndexType > &other)
Definition bitset.h:569
bool IsSet(IndexType i) const
Returns true if the bit at position i is set.
Definition bitset.h:533
void Clear(IndexType i)
Sets the bit at position i to 0.
Definition bitset.h:505
void Set(IndexType i, bool value)
If value is true, sets the bit at position i to 1, sets it to 0 otherwise.
Definition bitset.h:551
void Union(const Bitset64< IndexType > &other)
Definition bitset.h:620
void Intersection(const Bitset64< IndexType > &other)
Definition bitset.h:592
Iterator end() const
Definition bitset.h:704
Iterator begin() const
Definition bitset.h:703
void resize(int size)
Resizes the Bitset64 to the given number of bits. New bits are sets to 0.
Definition bitset.h:473
std::string DebugString() const
Returns a 0/1 string representing the bitset.
Definition bitset.h:721
static uint64_t ConditionalXorOfTwoBits(IndexType i, uint64_t use1, Bitset64< IndexType >::ConstView set1, uint64_t use2, Bitset64< IndexType >::ConstView set2)
Definition bitset.h:708
void ClearTwoBits(IndexType i)
Clears the bits at position i and i ^ 1.
Definition bitset.h:519
Bitset64(IndexType size)
Definition bitset.h:455
void Resize(IndexType size)
Definition bitset.h:474
bool AreOneOfTwoBitsSet(IndexType i) const
Returns true if the bit at position i or the one at position i ^ 1 is set.
Definition bitset.h:526
void SetToIntersectionOf(const Bitset64< IndexType > &a, const Bitset64< IndexType > &b)
This one assume both given bitset to be of the same size.
Definition bitset.h:605
void ClearAndResize(IndexType size)
Changes the number of bits the Bitset64 can hold and set all of them to 0.
Definition bitset.h:488
void PushBack(bool value)
Appends value at the end of the bitset.
Definition bitset.h:466
bool operator[](IndexType i) const
Same as IsSet().
Definition bitset.h:540
void SetContentFromBitsetOfSameSize(const Bitset64< OtherIndexType > &other)
Same as SetContentFromBitset where "this" and "other" have the same size.
Definition bitset.h:584
ConstView const_view() const
Definition bitset.h:459
void Set(IndexType i)
Sets the bit at position i to 1.
Definition bitset.h:543
Bitset64< IntegerType >::ConstView BitsetConstView()
Definition bitset.h:887
void ClearAndResize(IntegerType size)
Definition bitset.h:852
const std::vector< IntegerType > & PositionsSetAtLeastOnce() const
Definition bitset.h:899
void Clear(IntegerType index)
Definition bitset.h:895
bool operator[](IntegerType index) const
Definition bitset.h:877
SparseBitset & operator=(const SparseBitset &)=delete
Bitset64< IntegerType >::ConstView const_view() const
Definition bitset.h:916
SparseBitset(IntegerType size)
Definition bitset.h:845
void Set(IntegerType index)
Definition bitset.h:878
Bitset64< IntegerType >::View BitsetView()
A bit hacky for really hot loop.
Definition bitset.h:886
int NumberOfSetCallsWithDifferentArguments() const
Definition bitset.h:896
SparseBitset(const SparseBitset &)=delete
This type is neither copyable nor movable.
IntegerType size() const
Definition bitset.h:850
void Resize(IntegerType size)
Definition bitset.h:864
void SetUnsafe(typename Bitset64< IntegerType >::View view, IntegerType index)
Definition bitset.h:890
In SWIG mode, we don't want anything besides these top-level includes.
uint32_t IntervalDown32(uint32_t s)
Definition bitset.h:319
int64_t UnsafeMostSignificantBitPosition64(const uint64_t *bitset, uint64_t start, uint64_t end)
uint32_t BitCountRange32(const uint32_t *bitset, uint32_t start, uint32_t end)
int LeastSignificantBitPosition32Default(uint32_t n)
Definition bitset.h:156
void SetBit32(uint32_t *const bitset, uint32_t pos)
Definition bitset.h:360
int64_t UnsafeLeastSignificantBitPosition64(const uint64_t *bitset, uint64_t start, uint64_t end)
uint32_t BitLength32(uint32_t size)
Definition bitset.h:342
static const uint32_t kAllBits32
Definition bitset.h:38
bool IsEmptyRange32(const uint32_t *bitset, uint32_t start, uint32_t end)
uint32_t BitCount32(uint32_t n)
Definition bitset.h:56
int32_t UnsafeLeastSignificantBitPosition32(const uint32_t *bitset, uint32_t start, uint32_t end)
int LeastSignificantBitPosition64DeBruijn(uint64_t n)
Definition bitset.h:84
int MostSignificantBitPosition32Default(uint32_t n)
Definition bitset.h:252
int LeastSignificantBitPosition64Default(uint64_t n)
Definition bitset.h:96
bool IsBitSet32(const uint32_t *const bitset, uint32_t pos)
Definition bitset.h:352
uint32_t BitPos32(uint32_t pos)
Definition bitset.h:334
ClosedInterval::Iterator end(ClosedInterval interval)
uint64_t BitShift64(uint64_t v)
Returns the bit number in the bitset of the first bit of word number v.
Definition bitset.h:345
uint32_t BitOffset32(uint32_t pos)
Definition bitset.h:338
uint32_t LeastSignificantBitWord32(uint32_t n)
Definition bitset.h:67
uint64_t IntervalDown64(uint64_t s)
Returns a word with the s most significant bits unset.
Definition bitset.h:314
uint32_t IntervalUp32(uint32_t s)
Definition bitset.h:308
void ClearBit32(uint32_t *const bitset, uint32_t pos)
Definition bitset.h:368
static const uint64_t kAllBits64
Basic bit operations.
Definition bitset.h:36
int LeastSignificantBitPosition32DeBruijn(uint32_t n)
Definition bitset.h:147
void ClearBit64(uint64_t *const bitset, uint64_t pos)
Sets the bit pos to false in bitset.
Definition bitset.h:365
uint32_t OneBit32(int pos)
Definition bitset.h:42
uint64_t OneRange64(uint64_t s, uint64_t e)
Returns a word with bits from s to e set.
Definition bitset.h:288
static const uint64_t kAllBitsButLsb64
Definition bitset.h:37
uint32_t BitShift32(uint32_t v)
Definition bitset.h:346
uint32_t BitPos64(uint64_t pos)
Bit operators used to manipulates bitsets.
Definition bitset.h:333
uint64_t BitCountRange64(const uint64_t *bitset, uint64_t start, uint64_t end)
Returns the number of bits set in bitset between positions start and end.
uint64_t BitCount64(uint64_t n)
Returns the number of bits set in n.
Definition bitset.h:45
int MostSignificantBitPosition32(uint32_t n)
Definition bitset.h:276
bool IsBitSet64(const uint64_t *const bitset, uint64_t pos)
Returns true if the bit pos is set in bitset.
Definition bitset.h:349
uint64_t OneBit64(int pos)
Returns a word with only bit pos set.
Definition bitset.h:41
uint32_t OneRange32(uint32_t s, uint32_t e)
Definition bitset.h:295
uint64_t BitOffset64(uint64_t pos)
Returns the word number corresponding to bit number pos.
Definition bitset.h:337
bool IsEmptyRange64(const uint64_t *bitset, uint64_t start, uint64_t end)
Returns true if no bits are set in bitset between start and end.
uint64_t BitLength64(uint64_t size)
Returns the number of words needed to store size bits.
Definition bitset.h:341
int LeastSignificantBitPosition64(uint64_t n)
Definition bitset.h:130
int32_t UnsafeMostSignificantBitPosition32(const uint32_t *bitset, uint32_t start, uint32_t end)
int MostSignificantBitPosition64Default(uint64_t n)
Returns the most significant bit position in n.
Definition bitset.h:206
int LeastSignificantBitPosition32(uint32_t n)
Definition bitset.h:185
void SetBit64(uint64_t *const bitset, uint64_t pos)
Sets the bit pos to true in bitset.
Definition bitset.h:357
uint64_t LeastSignificantBitWord64(uint64_t n)
Returns a word with only the least significant bit of n set.
Definition bitset.h:66
uint64_t TwoBitsFromPos64(uint64_t pos)
Returns a mask with the bits pos % 64 and (pos ^ 1) % 64 sets.
Definition bitset.h:405
int MostSignificantBitPosition64(uint64_t n)
Definition bitset.h:234
uint64_t IntervalUp64(uint64_t s)
Returns a word with s least significant bits unset.
Definition bitset.h:303
static int input(yyscan_t yyscanner)