OR-Tools  8.1
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 
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 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 
57 BIT_COUNT_RANGE(64, GG_ULONGLONG(0))
58 BIT_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 
89 IS_EMPTY_RANGE(64)
90 IS_EMPTY_RANGE(32)
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 
139 LEAST_SIGNIFCANT_BIT_POSITION(64)
140 LEAST_SIGNIFCANT_BIT_POSITION(32)
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 
190 MOST_SIGNIFICANT_BIT_POSITION(64)
191 MOST_SIGNIFICANT_BIT_POSITION(32)
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 
221 UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(64)
222 UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(32)
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 
252 UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(64)
253 UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(32)
254 
255 #undef UNSAFE_MOST_SIGNIFICANT_BIT_POSITION
256 
257 } // namespace operations_research
GG_ULONGLONG
#define GG_ULONGLONG(x)
Definition: integral_types.h:47
logging.h
UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION
#define UNSAFE_LEAST_SIGNIFICANT_BIT_POSITION(size)
Definition: bitset.cc:195
ABSL_FLAG
ABSL_FLAG(int, bitset_small_bitset_count, 8, "threshold to count bits with buckets")
operations_research
The vehicle routing library lets one model and solve generic vehicle routing problems ranging from th...
Definition: dense_doubly_linked_list.h:21
MOST_SIGNIFICANT_BIT_POSITION
#define MOST_SIGNIFICANT_BIT_POSITION(size)
Definition: bitset.cc:144
IS_EMPTY_RANGE
#define IS_EMPTY_RANGE(size)
Definition: bitset.cc:62
BIT_COUNT_RANGE
#define BIT_COUNT_RANGE(size, zero)
Definition: bitset.cc:26
LEAST_SIGNIFCANT_BIT_POSITION
#define LEAST_SIGNIFCANT_BIT_POSITION(size)
Definition: bitset.cc:94
commandlineflags.h
bitset.h
UNSAFE_MOST_SIGNIFICANT_BIT_POSITION
#define UNSAFE_MOST_SIGNIFICANT_BIT_POSITION(size)
Definition: bitset.cc:226