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