OR-Tools  8.2
bitset.cc
Go to the documentation of this file.
1// Copyright 2010-2018 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
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 BitCountRange##size(const uint##size* const bits, \
28 uint##size start, uint##size end) { \
29 if (end - start > absl::GetFlag(FLAGS_bitset_small_bitset_count)) { \
30 const int offset_start = BitOffset##size(start); \
31 const int pos_start = BitPos##size(start); \
32 const int offset_end = BitOffset##size(end); \
33 const int pos_end = BitPos##size(end); \
34 if (offset_end == offset_start) { \
35 return BitCount##size(bits[offset_start] & \
36 OneRange##size(pos_start, pos_end)); \
37 } else { \
38 uint##size bit_count = zero; \
39 bit_count += \
40 BitCount##size(bits[offset_start] & IntervalUp##size(pos_start)); \
41 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
42 bit_count += BitCount##size(bits[offset]); \
43 } \
44 bit_count += \
45 BitCount##size(bits[offset_end] & IntervalDown##size(pos_end)); \
46 return bit_count; \
47 } \
48 } else { \
49 uint##size bit_count = zero; \
50 for (uint##size i = start; i <= end; ++i) { \
51 bit_count += IsBitSet##size(bits, i); \
52 } \
53 return bit_count; \
54 } \
55 }
56
57BIT_COUNT_RANGE(64, uint64_t{0})
58BIT_COUNT_RANGE(32, 0U)
59
60#undef BIT_COUNT_RANGE
61
62#define IS_EMPTY_RANGE(size) \
63 bool IsEmptyRange##size(const uint##size* const bits, uint##size start, \
64 uint##size end) { \
65 const int offset_start = BitOffset##size(start); \
66 const int pos_start = BitPos##size(start); \
67 const int offset_end = BitOffset##size(end); \
68 const int pos_end = BitPos##size(end); \
69 if (offset_end == offset_start) { \
70 if (bits[offset_start] & OneRange##size(pos_start, pos_end)) { \
71 return false; \
72 } \
73 } else { \
74 if (bits[offset_start] & IntervalUp##size(pos_start)) { \
75 return false; \
76 } \
77 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
78 if (bits[offset]) { \
79 return false; \
80 } \
81 } \
82 if (bits[offset_end] & IntervalDown##size(pos_end)) { \
83 return false; \
84 } \
85 } \
86 return true; \
87 }
88
91
92#undef IS_EMPTY_RANGE
93
94#define LEAST_SIGNIFCANT_BIT_POSITION(size) \
95 int##size LeastSignificantBitPosition##size( \
96 const uint##size* const bits, uint##size start, uint##size end) { \
97 DCHECK_LE(start, end); \
98 if (IsBitSet##size(bits, start)) { \
99 return start; \
100 } \
101 const int offset_start = BitOffset##size(start); \
102 const int offset_end = BitOffset##size(end); \
103 const int pos_start = BitPos##size(start); \
104 if (offset_start == offset_end) { \
105 const int pos_end = BitPos##size(end); \
106 const uint##size active_range = \
107 bits[offset_start] & OneRange##size(pos_start, pos_end); \
108 if (active_range) { \
109 return BitShift##size(offset_start) + \
110 LeastSignificantBitPosition##size(active_range); \
111 } \
112 return -1; \
113 } else { \
114 const uint##size start_mask = \
115 bits[offset_start] & IntervalUp##size(pos_start); \
116 if (start_mask) { \
117 return BitShift##size(offset_start) + \
118 LeastSignificantBitPosition##size(start_mask); \
119 } else { \
120 for (int offset = offset_start + 1; offset < offset_end; ++offset) { \
121 if (bits[offset]) { \
122 return BitShift##size(offset) + \
123 LeastSignificantBitPosition##size(bits[offset]); \
124 } \
125 } \
126 const int pos_end = BitPos##size(end); \
127 const uint##size active_range = \
128 bits[offset_end] & IntervalDown##size(pos_end); \
129 if (active_range) { \
130 return BitShift##size(offset_end) + \
131 LeastSignificantBitPosition##size(active_range); \
132 } else { \
133 return -1; \
134 } \
135 } \
136 } \
137 }
138
141
142#undef LEAST_SIGNIFCANT_BIT_POSITION
143
144#define MOST_SIGNIFICANT_BIT_POSITION(size) \
145 int##size MostSignificantBitPosition##size( \
146 const uint##size* const bits, uint##size start, uint##size end) { \
147 DCHECK_GE(end, start); \
148 if (IsBitSet##size(bits, end)) { \
149 return end; \
150 } \
151 const int offset_start = BitOffset##size(start); \
152 const int offset_end = BitOffset##size(end); \
153 const int pos_end = BitPos##size(end); \
154 if (offset_start == offset_end) { \
155 const int pos_start = BitPos##size(start); \
156 const uint##size active_range = \
157 bits[offset_start] & OneRange##size(pos_start, pos_end); \
158 if (active_range) { \
159 return BitShift##size(offset_end) + \
160 MostSignificantBitPosition##size(active_range); \
161 } else { \
162 return -1; \
163 } \
164 } else { \
165 const uint##size end_mask = \
166 bits[offset_end] & IntervalDown##size(pos_end); \
167 if (end_mask) { \
168 return BitShift##size(offset_end) + \
169 MostSignificantBitPosition##size(end_mask); \
170 } else { \
171 for (int offset = offset_end - 1; offset > offset_start; --offset) { \
172 if (bits[offset]) { \
173 return BitShift##size(offset) + \
174 MostSignificantBitPosition##size(bits[offset]); \
175 } \
176 } \
177 const int pos_start = BitPos##size(start); \
178 const uint##size active_range = \
179 bits[offset_start] & IntervalUp##size(pos_start); \
180 if (active_range) { \
181 return BitShift##size(offset_start) + \
182 MostSignificantBitPosition##size(active_range); \
183 } else { \
184 return -1; \
185 } \
186 } \
187 } \
188 }
189
192
193#undef MOST_SIGNIFICANT_BIT_POSITION
194
195#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size) \
196 int##size UnsafeLeastSignificantBitPosition##size( \
197 const uint##size* const bits, uint##size start, uint##size end) { \
198 DCHECK_LE(start, end); \
199 DCHECK(IsBitSet##size(bits, end)); \
200 if (IsBitSet##size(bits, start)) { \
201 return start; \
202 } \
203 const int offset_start = BitOffset##size(start); \
204 const int offset_end = BitOffset##size(end); \
205 const int pos_start = BitPos##size(start); \
206 const uint##size start_mask = \
207 bits[offset_start] & IntervalUp##size(pos_start); \
208 if (start_mask) { \
209 return BitShift##size(offset_start) + \
210 LeastSignificantBitPosition##size(start_mask); \
211 } \
212 for (int offset = offset_start + 1; offset <= offset_end; ++offset) { \
213 if (bits[offset]) { \
214 return BitShift##size(offset) + \
215 LeastSignificantBitPosition##size(bits[offset]); \
216 } \
217 } \
218 return -1; \
219 }
220
223
224#undef UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION
225
226#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size) \
227 int##size UnsafeMostSignificantBitPosition##size( \
228 const uint##size* const bits, uint##size start, uint##size end) { \
229 DCHECK_GE(end, start); \
230 DCHECK(IsBitSet##size(bits, start)); \
231 if (IsBitSet##size(bits, end)) { \
232 return end; \
233 } \
234 const int offset_start = BitOffset##size(start); \
235 const int offset_end = BitOffset##size(end); \
236 const int pos_end = BitPos##size(end); \
237 const uint##size end_mask = \
238 bits[offset_end] & IntervalDown##size(pos_end); \
239 if (end_mask) { \
240 return BitShift##size(offset_end) + \
241 MostSignificantBitPosition##size(end_mask); \
242 } \
243 for (int offset = offset_end - 1; offset >= offset_start; --offset) { \
244 if (bits[offset]) { \
245 return BitShift##size(offset) + \
246 MostSignificantBitPosition##size(bits[offset]); \
247 } \
248 } \
249 return -1; \
250 }
251
254
255#undef UNSAFE_MOST_SIGNIFICANT_BIT_POSITION
256
257} // namespace operations_research
#define LEAST_SIGNIFCANT_BIT_POSITION(size)
Definition: bitset.cc:94
#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size)
Definition: bitset.cc:226
#define MOST_SIGNIFICANT_BIT_POSITION(size)
Definition: bitset.cc:144
#define IS_EMPTY_RANGE(size)
Definition: bitset.cc:62
#define BIT_COUNT_RANGE(size, zero)
Definition: bitset.cc:26
ABSL_FLAG(int, bitset_small_bitset_count, 8, "threshold to count bits with buckets")
#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size)
Definition: bitset.cc:195
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...