OR-Tools  9.6
bitset.cc
Go to the documentation of this file.
1 // Copyright 2010-2022 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 
19 ABSL_FLAG(int, bitset_small_bitset_count, 8,
20  "threshold to count bits with buckets");
21 
22 namespace 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 
59 BIT_COUNT_RANGE(64, uint64_t{0})
60 BIT_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 
91 IS_EMPTY_RANGE(64)
92 IS_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 
142 LEAST_SIGNIFCANT_BIT_POSITION(64)
143 LEAST_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 
194 MOST_SIGNIFICANT_BIT_POSITION(64)
195 MOST_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 
226 UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(64)
227 UNSAFE_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 
258 UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(64)
259 UNSAFE_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)
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
Collection of objects used to extend the Constraint Solver library.
Definition: dense_doubly_linked_list.h:21