Google OR-Tools v9.11
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
bitset.cc
Go to the documentation of this file.
1// Copyright 2010-2024 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#include "ortools/util/bitset.h"
15
16#include "ortools/base/commandlineflags.h"
17#include "ortools/base/logging.h"
18
19ABSL_FLAG(int, bitset_small_bitset_count, 8,
20 "threshold to count bits with buckets");
21
22namespace operations_research {
23
24// ---------- Bit Operations ----------
25
26#define BIT_COUNT_RANGE(size, zero) \
27 uint##size##_t BitCountRange##size(const uint##size##_t* const bits, \
28 uint##size##_t start, \
29 uint##size##_t end) { \
30 if (static_cast<int##size##_t>(end - start) > \
31 absl::GetFlag(FLAGS_bitset_small_bitset_count)) { \
32 const int offset_start = BitOffset##size(start); \
33 const int pos_start = BitPos##size(start); \
34 const int offset_end = BitOffset##size(end); \
35 const int pos_end = BitPos##size(end); \
36 if (offset_end == offset_start) { \
37 return BitCount##size(bits[offset_start] & \
38 OneRange##size(pos_start, pos_end)); \
39 } else { \
40 uint##size##_t bit_count = zero; \
41 bit_count += \
42 BitCount##size(bits[offset_start] & IntervalUp##size(pos_start)); \
43 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
44 bit_count += BitCount##size(bits[offset]); \
45 } \
46 bit_count += \
47 BitCount##size(bits[offset_end] & IntervalDown##size(pos_end)); \
48 return bit_count; \
49 } \
50 } else { \
51 uint##size##_t bit_count = zero; \
52 for (uint##size##_t i = start; i <= end; ++i) { \
53 bit_count += IsBitSet##size(bits, i); \
54 } \
55 return bit_count; \
56 } \
57 }
58
59BIT_COUNT_RANGE(64, uint64_t{0})
60BIT_COUNT_RANGE(32, 0U)
61
62#undef BIT_COUNT_RANGE
63
64#define IS_EMPTY_RANGE(size) \
65 bool IsEmptyRange##size(const uint##size##_t* const bits, \
66 uint##size##_t start, uint##size##_t end) { \
67 const int offset_start = BitOffset##size(start); \
68 const int pos_start = BitPos##size(start); \
69 const int offset_end = BitOffset##size(end); \
70 const int pos_end = BitPos##size(end); \
71 if (offset_end == offset_start) { \
72 if (bits[offset_start] & OneRange##size(pos_start, pos_end)) { \
73 return false; \
74 } \
75 } else { \
76 if (bits[offset_start] & IntervalUp##size(pos_start)) { \
77 return false; \
78 } \
79 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
80 if (bits[offset]) { \
81 return false; \
82 } \
83 } \
84 if (bits[offset_end] & IntervalDown##size(pos_end)) { \
85 return false; \
86 } \
87 } \
88 return true; \
89 }
90
91IS_EMPTY_RANGE(64)
92IS_EMPTY_RANGE(32)
93
94#undef IS_EMPTY_RANGE
95
96#define LEAST_SIGNIFCANT_BIT_POSITION(size) \
97 int##size##_t LeastSignificantBitPosition##size( \
98 const uint##size##_t* const bits, uint##size##_t start, \
99 uint##size##_t end) { \
100 DCHECK_LE(start, end); \
101 if (IsBitSet##size(bits, start)) { \
102 return start; \
103 } \
104 const int offset_start = BitOffset##size(start); \
105 const int offset_end = BitOffset##size(end); \
106 const int pos_start = BitPos##size(start); \
107 if (offset_start == offset_end) { \
108 const int pos_end = BitPos##size(end); \
109 const uint##size##_t active_range = \
110 bits[offset_start] & OneRange##size(pos_start, pos_end); \
111 if (active_range) { \
112 return BitShift##size(offset_start) + \
113 LeastSignificantBitPosition##size(active_range); \
114 } \
115 return -1; \
116 } else { \
117 const uint##size##_t start_mask = \
118 bits[offset_start] & IntervalUp##size(pos_start); \
119 if (start_mask) { \
120 return BitShift##size(offset_start) + \
121 LeastSignificantBitPosition##size(start_mask); \
122 } else { \
123 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
124 if (bits[offset]) { \
125 return BitShift##size(offset) + \
126 LeastSignificantBitPosition##size(bits[offset]); \
127 } \
128 } \
129 const int pos_end = BitPos##size(end); \
130 const uint##size##_t active_range = \
131 bits[offset_end] & IntervalDown##size(pos_end); \
132 if (active_range) { \
133 return BitShift##size(offset_end) + \
134 LeastSignificantBitPosition##size(active_range); \
135 } else { \
136 return -1; \
137 } \
138 } \
139 } \
140 }
141
142LEAST_SIGNIFCANT_BIT_POSITION(64)
143LEAST_SIGNIFCANT_BIT_POSITION(32)
144
145#undef LEAST_SIGNIFCANT_BIT_POSITION
146
147#define MOST_SIGNIFICANT_BIT_POSITION(size) \
148 int##size##_t MostSignificantBitPosition##size( \
149 const uint##size##_t* const bits, uint##size##_t start, \
150 uint##size##_t end) { \
151 DCHECK_GE(end, start); \
152 if (IsBitSet##size(bits, end)) { \
153 return end; \
154 } \
155 const int offset_start = BitOffset##size(start); \
156 const int offset_end = BitOffset##size(end); \
157 const int pos_end = BitPos##size(end); \
158 if (offset_start == offset_end) { \
159 const int pos_start = BitPos##size(start); \
160 const uint##size##_t active_range = \
161 bits[offset_start] & OneRange##size(pos_start, pos_end); \
162 if (active_range) { \
163 return BitShift##size(offset_end) + \
164 MostSignificantBitPosition##size(active_range); \
165 } else { \
166 return -1; \
167 } \
168 } else { \
169 const uint##size##_t end_mask = \
170 bits[offset_end] & IntervalDown##size(pos_end); \
171 if (end_mask) { \
172 return BitShift##size(offset_end) + \
173 MostSignificantBitPosition##size(end_mask); \
174 } else { \
175 for (int offset = offset_end - 1; offset > offset_start; --offset) { \
176 if (bits[offset]) { \
177 return BitShift##size(offset) + \
178 MostSignificantBitPosition##size(bits[offset]); \
179 } \
180 } \
181 const int pos_start = BitPos##size(start); \
182 const uint##size##_t active_range = \
183 bits[offset_start] & IntervalUp##size(pos_start); \
184 if (active_range) { \
185 return BitShift##size(offset_start) + \
186 MostSignificantBitPosition##size(active_range); \
187 } else { \
188 return -1; \
189 } \
190 } \
191 } \
192 }
193
194MOST_SIGNIFICANT_BIT_POSITION(64)
195MOST_SIGNIFICANT_BIT_POSITION(32)
196
197#undef MOST_SIGNIFICANT_BIT_POSITION
198
199#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size) \
200 int##size##_t UnsafeLeastSignificantBitPosition##size( \
201 const uint##size##_t* const bits, uint##size##_t start, \
202 uint##size##_t end) { \
203 DCHECK_LE(start, end); \
204 DCHECK(IsBitSet##size(bits, end)); \
205 if (IsBitSet##size(bits, start)) { \
206 return start; \
207 } \
208 const int offset_start = BitOffset##size(start); \
209 const int offset_end = BitOffset##size(end); \
210 const int pos_start = BitPos##size(start); \
211 const uint##size##_t start_mask = \
212 bits[offset_start] & IntervalUp##size(pos_start); \
213 if (start_mask) { \
214 return BitShift##size(offset_start) + \
215 LeastSignificantBitPosition##size(start_mask); \
216 } \
217 for (int offset = offset_start + 1; offset <= offset_end; ++offset) { \
218 if (bits[offset]) { \
219 return BitShift##size(offset) + \
220 LeastSignificantBitPosition##size(bits[offset]); \
221 } \
222 } \
223 return -1; \
224 }
225
226UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(64)
227UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(32)
228
229#undef UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION
230
231#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size) \
232 int##size##_t UnsafeMostSignificantBitPosition##size( \
233 const uint##size##_t* const bits, uint##size##_t start, \
234 uint##size##_t end) { \
235 DCHECK_GE(end, start); \
236 DCHECK(IsBitSet##size(bits, start)); \
237 if (IsBitSet##size(bits, end)) { \
238 return end; \
239 } \
240 const int offset_start = BitOffset##size(start); \
241 const int offset_end = BitOffset##size(end); \
242 const int pos_end = BitPos##size(end); \
243 const uint##size##_t end_mask = \
244 bits[offset_end] & IntervalDown##size(pos_end); \
245 if (end_mask) { \
246 return BitShift##size(offset_end) + \
247 MostSignificantBitPosition##size(end_mask); \
248 } \
249 for (int offset = offset_end - 1; offset >= offset_start; --offset) { \
250 if (bits[offset]) { \
251 return BitShift##size(offset) + \
252 MostSignificantBitPosition##size(bits[offset]); \
253 } \
254 } \
255 return -1; \
256 }
257
258UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(64)
259UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(32)
260
261#undef UNSAFE_MOST_SIGNIFICANT_BIT_POSITION
262
263} // namespace operations_research
LEAST_SIGNIFCANT_BIT_POSITION
#define LEAST_SIGNIFCANT_BIT_POSITION(size)
Definition bitset.cc:96
UNSAFE_MOST_SIGNIFICANT_BIT_POSITION
#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size)
Definition bitset.cc:231
MOST_SIGNIFICANT_BIT_POSITION
#define MOST_SIGNIFICANT_BIT_POSITION(size)
Definition bitset.cc:147
IS_EMPTY_RANGE
#define IS_EMPTY_RANGE(size)
Definition bitset.cc:64
BIT_COUNT_RANGE
#define BIT_COUNT_RANGE(size, zero)
-------— Bit Operations -------—
Definition bitset.cc:26
ABSL_FLAG
ABSL_FLAG(int, bitset_small_bitset_count, 8, "threshold to count bits with buckets")
UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION
#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size)
Definition bitset.cc:199
operations_research
In SWIG mode, we don't want anything besides these top-level includes.
Definition binary_indexed_tree.h:21