1 // Copyright 2020 The Abseil Authors
2 //
3 // Licensed under the Apache License, Version 2.0 (the "License");
4 // you may not use this file except in compliance with the License.
5 // You may obtain a copy of the License at
6 //
7 // https://www.apache.org/licenses/LICENSE-2.0
8 //
9 // Unless required by applicable law or agreed to in writing, software
10 // distributed under the License is distributed on an "AS IS" BASIS,
11 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 // See the License for the specific language governing permissions and
13 // limitations under the License.
14
15 #include "absl/numeric/bits.h"
16
17 #include <limits>
18 #include <type_traits>
19
20 #include "gmock/gmock.h"
21 #include "gtest/gtest.h"
22 #include "absl/random/random.h"
23
24 namespace absl {
25 ABSL_NAMESPACE_BEGIN
26 namespace {
27
28 template <typename IntT>
29 class IntegerTypesTest : public ::testing::Test {};
30
31 using OneByteIntegerTypes = ::testing::Types<
32 unsigned char,
33 uint8_t
34 >;
35
36 TYPED_TEST_SUITE(IntegerTypesTest, OneByteIntegerTypes);
37
TYPED_TEST(IntegerTypesTest,HandlesTypes)38 TYPED_TEST(IntegerTypesTest, HandlesTypes) {
39 using UIntType = TypeParam;
40
41 EXPECT_EQ(rotl(UIntType{0x12}, 0), uint8_t{0x12});
42 EXPECT_EQ(rotr(UIntType{0x12}, -4), uint8_t{0x21});
43 static_assert(rotl(UIntType{0x12}, 0) == uint8_t{0x12}, "");
44
45 static_assert(rotr(UIntType{0x12}, 0) == uint8_t{0x12}, "");
46 EXPECT_EQ(rotr(UIntType{0x12}, 0), uint8_t{0x12});
47
48 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
49 static_assert(countl_zero(UIntType{}) == 8, "");
50 static_assert(countl_zero(static_cast<UIntType>(-1)) == 0, "");
51
52 static_assert(countl_one(UIntType{}) == 0, "");
53 static_assert(countl_one(static_cast<UIntType>(-1)) == 8, "");
54
55 static_assert(countr_zero(UIntType{}) == 8, "");
56 static_assert(countr_zero(static_cast<UIntType>(-1)) == 0, "");
57
58 static_assert(countr_one(UIntType{}) == 0, "");
59 static_assert(countr_one(static_cast<UIntType>(-1)) == 8, "");
60
61 static_assert(popcount(UIntType{}) == 0, "");
62 static_assert(popcount(UIntType{1}) == 1, "");
63 static_assert(popcount(static_cast<UIntType>(-1)) == 8, "");
64
65 static_assert(bit_width(UIntType{}) == 0, "");
66 static_assert(bit_width(UIntType{1}) == 1, "");
67 static_assert(bit_width(UIntType{3}) == 2, "");
68 static_assert(bit_width(static_cast<UIntType>(-1)) == 8, "");
69 #endif
70
71 EXPECT_EQ(countl_zero(UIntType{}), 8);
72 EXPECT_EQ(countl_zero(static_cast<UIntType>(-1)), 0);
73
74 EXPECT_EQ(countl_one(UIntType{}), 0);
75 EXPECT_EQ(countl_one(static_cast<UIntType>(-1)), 8);
76
77 EXPECT_EQ(countr_zero(UIntType{}), 8);
78 EXPECT_EQ(countr_zero(static_cast<UIntType>(-1)), 0);
79
80 EXPECT_EQ(countr_one(UIntType{}), 0);
81 EXPECT_EQ(countr_one(static_cast<UIntType>(-1)), 8);
82
83 EXPECT_EQ(popcount(UIntType{}), 0);
84 EXPECT_EQ(popcount(UIntType{1}), 1);
85
86 EXPECT_FALSE(has_single_bit(UIntType{}));
87 EXPECT_FALSE(has_single_bit(static_cast<UIntType>(-1)));
88
89 EXPECT_EQ(bit_width(UIntType{}), 0);
90 EXPECT_EQ(bit_width(UIntType{1}), 1);
91 EXPECT_EQ(bit_width(UIntType{3}), 2);
92 EXPECT_EQ(bit_width(static_cast<UIntType>(-1)), 8);
93 }
94
TEST(Rotate,Left)95 TEST(Rotate, Left) {
96 static_assert(rotl(uint8_t{0x12}, 0) == uint8_t{0x12}, "");
97 static_assert(rotl(uint16_t{0x1234}, 0) == uint16_t{0x1234}, "");
98 static_assert(rotl(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, "");
99 static_assert(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0) ==
100 uint64_t{0x12345678ABCDEF01ULL},
101 "");
102
103 EXPECT_EQ(rotl(uint8_t{0x12}, 0), uint8_t{0x12});
104 EXPECT_EQ(rotl(uint16_t{0x1234}, 0), uint16_t{0x1234});
105 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL});
106 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 0),
107 uint64_t{0x12345678ABCDEF01ULL});
108
109 EXPECT_EQ(rotl(uint8_t{0x12}, 8), uint8_t{0x12});
110 EXPECT_EQ(rotl(uint16_t{0x1234}, 16), uint16_t{0x1234});
111 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL});
112 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 64),
113 uint64_t{0x12345678ABCDEF01ULL});
114
115 EXPECT_EQ(rotl(uint8_t{0x12}, -8), uint8_t{0x12});
116 EXPECT_EQ(rotl(uint16_t{0x1234}, -16), uint16_t{0x1234});
117 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL});
118 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -64),
119 uint64_t{0x12345678ABCDEF01ULL});
120
121 EXPECT_EQ(rotl(uint8_t{0x12}, 4), uint8_t{0x21});
122 EXPECT_EQ(rotl(uint16_t{0x1234}, 4), uint16_t{0x2341});
123 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, 4), uint32_t{0x23456781UL});
124 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, 4),
125 uint64_t{0x2345678ABCDEF011ULL});
126
127 EXPECT_EQ(rotl(uint8_t{0x12}, -4), uint8_t{0x21});
128 EXPECT_EQ(rotl(uint16_t{0x1234}, -4), uint16_t{0x4123});
129 EXPECT_EQ(rotl(uint32_t{0x12345678UL}, -4), uint32_t{0x81234567UL});
130 EXPECT_EQ(rotl(uint64_t{0x12345678ABCDEF01ULL}, -4),
131 uint64_t{0x112345678ABCDEF0ULL});
132 }
133
TEST(Rotate,Right)134 TEST(Rotate, Right) {
135 static_assert(rotr(uint8_t{0x12}, 0) == uint8_t{0x12}, "");
136 static_assert(rotr(uint16_t{0x1234}, 0) == uint16_t{0x1234}, "");
137 static_assert(rotr(uint32_t{0x12345678UL}, 0) == uint32_t{0x12345678UL}, "");
138 static_assert(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0) ==
139 uint64_t{0x12345678ABCDEF01ULL},
140 "");
141
142 EXPECT_EQ(rotr(uint8_t{0x12}, 0), uint8_t{0x12});
143 EXPECT_EQ(rotr(uint16_t{0x1234}, 0), uint16_t{0x1234});
144 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 0), uint32_t{0x12345678UL});
145 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 0),
146 uint64_t{0x12345678ABCDEF01ULL});
147
148 EXPECT_EQ(rotr(uint8_t{0x12}, 8), uint8_t{0x12});
149 EXPECT_EQ(rotr(uint16_t{0x1234}, 16), uint16_t{0x1234});
150 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 32), uint32_t{0x12345678UL});
151 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 64),
152 uint64_t{0x12345678ABCDEF01ULL});
153
154 EXPECT_EQ(rotr(uint8_t{0x12}, -8), uint8_t{0x12});
155 EXPECT_EQ(rotr(uint16_t{0x1234}, -16), uint16_t{0x1234});
156 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -32), uint32_t{0x12345678UL});
157 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -64),
158 uint64_t{0x12345678ABCDEF01ULL});
159
160 EXPECT_EQ(rotr(uint8_t{0x12}, 4), uint8_t{0x21});
161 EXPECT_EQ(rotr(uint16_t{0x1234}, 4), uint16_t{0x4123});
162 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, 4), uint32_t{0x81234567UL});
163 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, 4),
164 uint64_t{0x112345678ABCDEF0ULL});
165
166 EXPECT_EQ(rotr(uint8_t{0x12}, -4), uint8_t{0x21});
167 EXPECT_EQ(rotr(uint16_t{0x1234}, -4), uint16_t{0x2341});
168 EXPECT_EQ(rotr(uint32_t{0x12345678UL}, -4), uint32_t{0x23456781UL});
169 EXPECT_EQ(rotr(uint64_t{0x12345678ABCDEF01ULL}, -4),
170 uint64_t{0x2345678ABCDEF011ULL});
171 }
172
TEST(Rotate,Symmetry)173 TEST(Rotate, Symmetry) {
174 // rotr(x, s) is equivalent to rotl(x, -s)
175 absl::BitGen rng;
176 constexpr int kTrials = 100;
177
178 for (int i = 0; i < kTrials; ++i) {
179 uint8_t value = absl::Uniform(rng, std::numeric_limits<uint8_t>::min(),
180 std::numeric_limits<uint8_t>::max());
181 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint8_t>::digits,
182 2 * std::numeric_limits<uint8_t>::digits);
183
184 EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
185 }
186
187 for (int i = 0; i < kTrials; ++i) {
188 uint16_t value = absl::Uniform(rng, std::numeric_limits<uint16_t>::min(),
189 std::numeric_limits<uint16_t>::max());
190 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint16_t>::digits,
191 2 * std::numeric_limits<uint16_t>::digits);
192
193 EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
194 }
195
196 for (int i = 0; i < kTrials; ++i) {
197 uint32_t value = absl::Uniform(rng, std::numeric_limits<uint32_t>::min(),
198 std::numeric_limits<uint32_t>::max());
199 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint32_t>::digits,
200 2 * std::numeric_limits<uint32_t>::digits);
201
202 EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
203 }
204
205 for (int i = 0; i < kTrials; ++i) {
206 uint64_t value = absl::Uniform(rng, std::numeric_limits<uint64_t>::min(),
207 std::numeric_limits<uint64_t>::max());
208 int shift = absl::Uniform(rng, -2 * std::numeric_limits<uint64_t>::digits,
209 2 * std::numeric_limits<uint64_t>::digits);
210
211 EXPECT_EQ(rotl(value, shift), rotr(value, -shift));
212 }
213 }
214
TEST(Counting,LeadingZeroes)215 TEST(Counting, LeadingZeroes) {
216 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
217 static_assert(countl_zero(uint8_t{}) == 8, "");
218 static_assert(countl_zero(static_cast<uint8_t>(-1)) == 0, "");
219 static_assert(countl_zero(uint16_t{}) == 16, "");
220 static_assert(countl_zero(static_cast<uint16_t>(-1)) == 0, "");
221 static_assert(countl_zero(uint32_t{}) == 32, "");
222 static_assert(countl_zero(~uint32_t{}) == 0, "");
223 static_assert(countl_zero(uint64_t{}) == 64, "");
224 static_assert(countl_zero(~uint64_t{}) == 0, "");
225 #endif
226
227 EXPECT_EQ(countl_zero(uint8_t{}), 8);
228 EXPECT_EQ(countl_zero(static_cast<uint8_t>(-1)), 0);
229 EXPECT_EQ(countl_zero(uint16_t{}), 16);
230 EXPECT_EQ(countl_zero(static_cast<uint16_t>(-1)), 0);
231 EXPECT_EQ(countl_zero(uint32_t{}), 32);
232 EXPECT_EQ(countl_zero(~uint32_t{}), 0);
233 EXPECT_EQ(countl_zero(uint64_t{}), 64);
234 EXPECT_EQ(countl_zero(~uint64_t{}), 0);
235
236 for (int i = 0; i < 8; i++) {
237 EXPECT_EQ(countl_zero(static_cast<uint8_t>(1u << i)), 7 - i);
238 }
239
240 for (int i = 0; i < 16; i++) {
241 EXPECT_EQ(countl_zero(static_cast<uint16_t>(1u << i)), 15 - i);
242 }
243
244 for (int i = 0; i < 32; i++) {
245 EXPECT_EQ(countl_zero(uint32_t{1} << i), 31 - i);
246 }
247
248 for (int i = 0; i < 64; i++) {
249 EXPECT_EQ(countl_zero(uint64_t{1} << i), 63 - i);
250 }
251 }
252
TEST(Counting,LeadingOnes)253 TEST(Counting, LeadingOnes) {
254 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
255 static_assert(countl_one(uint8_t{}) == 0, "");
256 static_assert(countl_one(static_cast<uint8_t>(-1)) == 8, "");
257 static_assert(countl_one(uint16_t{}) == 0, "");
258 static_assert(countl_one(static_cast<uint16_t>(-1)) == 16, "");
259 static_assert(countl_one(uint32_t{}) == 0, "");
260 static_assert(countl_one(~uint32_t{}) == 32, "");
261 static_assert(countl_one(uint64_t{}) == 0, "");
262 static_assert(countl_one(~uint64_t{}) == 64, "");
263 #endif
264
265 EXPECT_EQ(countl_one(uint8_t{}), 0);
266 EXPECT_EQ(countl_one(static_cast<uint8_t>(-1)), 8);
267 EXPECT_EQ(countl_one(uint16_t{}), 0);
268 EXPECT_EQ(countl_one(static_cast<uint16_t>(-1)), 16);
269 EXPECT_EQ(countl_one(uint32_t{}), 0);
270 EXPECT_EQ(countl_one(~uint32_t{}), 32);
271 EXPECT_EQ(countl_one(uint64_t{}), 0);
272 EXPECT_EQ(countl_one(~uint64_t{}), 64);
273 }
274
TEST(Counting,TrailingZeroes)275 TEST(Counting, TrailingZeroes) {
276 #if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ
277 static_assert(countr_zero(uint8_t{}) == 8, "");
278 static_assert(countr_zero(static_cast<uint8_t>(-1)) == 0, "");
279 static_assert(countr_zero(uint16_t{}) == 16, "");
280 static_assert(countr_zero(static_cast<uint16_t>(-1)) == 0, "");
281 static_assert(countr_zero(uint32_t{}) == 32, "");
282 static_assert(countr_zero(~uint32_t{}) == 0, "");
283 static_assert(countr_zero(uint64_t{}) == 64, "");
284 static_assert(countr_zero(~uint64_t{}) == 0, "");
285 #endif
286
287 EXPECT_EQ(countr_zero(uint8_t{}), 8);
288 EXPECT_EQ(countr_zero(static_cast<uint8_t>(-1)), 0);
289 EXPECT_EQ(countr_zero(uint16_t{}), 16);
290 EXPECT_EQ(countr_zero(static_cast<uint16_t>(-1)), 0);
291 EXPECT_EQ(countr_zero(uint32_t{}), 32);
292 EXPECT_EQ(countr_zero(~uint32_t{}), 0);
293 EXPECT_EQ(countr_zero(uint64_t{}), 64);
294 EXPECT_EQ(countr_zero(~uint64_t{}), 0);
295 }
296
TEST(Counting,TrailingOnes)297 TEST(Counting, TrailingOnes) {
298 #if ABSL_INTERNAL_HAS_CONSTEXPR_CTZ
299 static_assert(countr_one(uint8_t{}) == 0, "");
300 static_assert(countr_one(static_cast<uint8_t>(-1)) == 8, "");
301 static_assert(countr_one(uint16_t{}) == 0, "");
302 static_assert(countr_one(static_cast<uint16_t>(-1)) == 16, "");
303 static_assert(countr_one(uint32_t{}) == 0, "");
304 static_assert(countr_one(~uint32_t{}) == 32, "");
305 static_assert(countr_one(uint64_t{}) == 0, "");
306 static_assert(countr_one(~uint64_t{}) == 64, "");
307 #endif
308
309 EXPECT_EQ(countr_one(uint8_t{}), 0);
310 EXPECT_EQ(countr_one(static_cast<uint8_t>(-1)), 8);
311 EXPECT_EQ(countr_one(uint16_t{}), 0);
312 EXPECT_EQ(countr_one(static_cast<uint16_t>(-1)), 16);
313 EXPECT_EQ(countr_one(uint32_t{}), 0);
314 EXPECT_EQ(countr_one(~uint32_t{}), 32);
315 EXPECT_EQ(countr_one(uint64_t{}), 0);
316 EXPECT_EQ(countr_one(~uint64_t{}), 64);
317 }
318
TEST(Counting,Popcount)319 TEST(Counting, Popcount) {
320 #if ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT
321 static_assert(popcount(uint8_t{}) == 0, "");
322 static_assert(popcount(uint8_t{1}) == 1, "");
323 static_assert(popcount(static_cast<uint8_t>(-1)) == 8, "");
324 static_assert(popcount(uint16_t{}) == 0, "");
325 static_assert(popcount(uint16_t{1}) == 1, "");
326 static_assert(popcount(static_cast<uint16_t>(-1)) == 16, "");
327 static_assert(popcount(uint32_t{}) == 0, "");
328 static_assert(popcount(uint32_t{1}) == 1, "");
329 static_assert(popcount(~uint32_t{}) == 32, "");
330 static_assert(popcount(uint64_t{}) == 0, "");
331 static_assert(popcount(uint64_t{1}) == 1, "");
332 static_assert(popcount(~uint64_t{}) == 64, "");
333 #endif // ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT
334
335 EXPECT_EQ(popcount(uint8_t{}), 0);
336 EXPECT_EQ(popcount(uint8_t{1}), 1);
337 EXPECT_EQ(popcount(static_cast<uint8_t>(-1)), 8);
338 EXPECT_EQ(popcount(uint16_t{}), 0);
339 EXPECT_EQ(popcount(uint16_t{1}), 1);
340 EXPECT_EQ(popcount(static_cast<uint16_t>(-1)), 16);
341 EXPECT_EQ(popcount(uint32_t{}), 0);
342 EXPECT_EQ(popcount(uint32_t{1}), 1);
343 EXPECT_EQ(popcount(~uint32_t{}), 32);
344 EXPECT_EQ(popcount(uint64_t{}), 0);
345 EXPECT_EQ(popcount(uint64_t{1}), 1);
346 EXPECT_EQ(popcount(~uint64_t{}), 64);
347
348 for (int i = 0; i < 8; i++) {
349 EXPECT_EQ(popcount(static_cast<uint8_t>(uint8_t{1} << i)), 1);
350 EXPECT_EQ(popcount(static_cast<uint8_t>(static_cast<uint8_t>(-1) ^
351 (uint8_t{1} << i))),
352 7);
353 }
354
355 for (int i = 0; i < 16; i++) {
356 EXPECT_EQ(popcount(static_cast<uint16_t>(uint16_t{1} << i)), 1);
357 EXPECT_EQ(popcount(static_cast<uint16_t>(static_cast<uint16_t>(-1) ^
358 (uint16_t{1} << i))),
359 15);
360 }
361
362 for (int i = 0; i < 32; i++) {
363 EXPECT_EQ(popcount(uint32_t{1} << i), 1);
364 EXPECT_EQ(popcount(static_cast<uint32_t>(-1) ^ (uint32_t{1} << i)), 31);
365 }
366
367 for (int i = 0; i < 64; i++) {
368 EXPECT_EQ(popcount(uint64_t{1} << i), 1);
369 EXPECT_EQ(popcount(static_cast<uint64_t>(-1) ^ (uint64_t{1} << i)), 63);
370 }
371 }
372
373 template <typename T>
374 struct PopcountInput {
375 T value = 0;
376 int expected = 0;
377 };
378
379 template <typename T>
GeneratePopcountInput(absl::BitGen & gen)380 PopcountInput<T> GeneratePopcountInput(absl::BitGen& gen) {
381 PopcountInput<T> ret;
382 for (int i = 0; i < std::numeric_limits<T>::digits; i++) {
383 bool coin = absl::Bernoulli(gen, 0.2);
384 if (coin) {
385 ret.value |= T{1} << i;
386 ret.expected++;
387 }
388 }
389 return ret;
390 }
391
TEST(Counting,PopcountFuzz)392 TEST(Counting, PopcountFuzz) {
393 absl::BitGen rng;
394 constexpr int kTrials = 100;
395
396 for (int i = 0; i < kTrials; ++i) {
397 auto input = GeneratePopcountInput<uint8_t>(rng);
398 EXPECT_EQ(popcount(input.value), input.expected);
399 }
400
401 for (int i = 0; i < kTrials; ++i) {
402 auto input = GeneratePopcountInput<uint16_t>(rng);
403 EXPECT_EQ(popcount(input.value), input.expected);
404 }
405
406 for (int i = 0; i < kTrials; ++i) {
407 auto input = GeneratePopcountInput<uint32_t>(rng);
408 EXPECT_EQ(popcount(input.value), input.expected);
409 }
410
411 for (int i = 0; i < kTrials; ++i) {
412 auto input = GeneratePopcountInput<uint64_t>(rng);
413 EXPECT_EQ(popcount(input.value), input.expected);
414 }
415 }
416
TEST(IntegralPowersOfTwo,SingleBit)417 TEST(IntegralPowersOfTwo, SingleBit) {
418 EXPECT_FALSE(has_single_bit(uint8_t{}));
419 EXPECT_FALSE(has_single_bit(static_cast<uint8_t>(-1)));
420 EXPECT_FALSE(has_single_bit(uint16_t{}));
421 EXPECT_FALSE(has_single_bit(static_cast<uint16_t>(-1)));
422 EXPECT_FALSE(has_single_bit(uint32_t{}));
423 EXPECT_FALSE(has_single_bit(~uint32_t{}));
424 EXPECT_FALSE(has_single_bit(uint64_t{}));
425 EXPECT_FALSE(has_single_bit(~uint64_t{}));
426
427 static_assert(!has_single_bit(0u), "");
428 static_assert(has_single_bit(1u), "");
429 static_assert(has_single_bit(2u), "");
430 static_assert(!has_single_bit(3u), "");
431 static_assert(has_single_bit(4u), "");
432 static_assert(!has_single_bit(1337u), "");
433 static_assert(has_single_bit(65536u), "");
434 static_assert(has_single_bit(uint32_t{1} << 30), "");
435 static_assert(has_single_bit(uint64_t{1} << 42), "");
436
437 EXPECT_FALSE(has_single_bit(0u));
438 EXPECT_TRUE(has_single_bit(1u));
439 EXPECT_TRUE(has_single_bit(2u));
440 EXPECT_FALSE(has_single_bit(3u));
441 EXPECT_TRUE(has_single_bit(4u));
442 EXPECT_FALSE(has_single_bit(1337u));
443 EXPECT_TRUE(has_single_bit(65536u));
444 EXPECT_TRUE(has_single_bit(uint32_t{1} << 30));
445 EXPECT_TRUE(has_single_bit(uint64_t{1} << 42));
446
447 EXPECT_TRUE(has_single_bit(
448 static_cast<uint8_t>(std::numeric_limits<uint8_t>::max() / 2 + 1)));
449 EXPECT_TRUE(has_single_bit(
450 static_cast<uint16_t>(std::numeric_limits<uint16_t>::max() / 2 + 1)));
451 EXPECT_TRUE(has_single_bit(
452 static_cast<uint32_t>(std::numeric_limits<uint32_t>::max() / 2 + 1)));
453 EXPECT_TRUE(has_single_bit(
454 static_cast<uint64_t>(std::numeric_limits<uint64_t>::max() / 2 + 1)));
455 }
456
457 template <typename T, T arg, T = bit_ceil(arg)>
IsBitCeilConstantExpression(int)458 bool IsBitCeilConstantExpression(int) {
459 return true;
460 }
461 template <typename T, T arg>
IsBitCeilConstantExpression(char)462 bool IsBitCeilConstantExpression(char) {
463 return false;
464 }
465
TEST(IntegralPowersOfTwo,Ceiling)466 TEST(IntegralPowersOfTwo, Ceiling) {
467 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
468 static_assert(bit_ceil(0u) == 1, "");
469 static_assert(bit_ceil(1u) == 1, "");
470 static_assert(bit_ceil(2u) == 2, "");
471 static_assert(bit_ceil(3u) == 4, "");
472 static_assert(bit_ceil(4u) == 4, "");
473 static_assert(bit_ceil(1337u) == 2048, "");
474 static_assert(bit_ceil(65536u) == 65536, "");
475 static_assert(bit_ceil(65536u - 1337u) == 65536, "");
476 static_assert(bit_ceil(uint32_t{0x80000000}) == uint32_t{0x80000000}, "");
477 static_assert(bit_ceil(uint64_t{0x40000000000}) == uint64_t{0x40000000000},
478 "");
479 static_assert(
480 bit_ceil(uint64_t{0x8000000000000000}) == uint64_t{0x8000000000000000},
481 "");
482
483 EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x0}>(0)));
484 EXPECT_TRUE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x80}>(0)));
485 EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0x81}>(0)));
486 EXPECT_FALSE((IsBitCeilConstantExpression<uint8_t, uint8_t{0xff}>(0)));
487
488 EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x0}>(0)));
489 EXPECT_TRUE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8000}>(0)));
490 EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0x8001}>(0)));
491 EXPECT_FALSE((IsBitCeilConstantExpression<uint16_t, uint16_t{0xffff}>(0)));
492
493 EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x0}>(0)));
494 EXPECT_TRUE((IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000000}>(0)));
495 EXPECT_FALSE(
496 (IsBitCeilConstantExpression<uint32_t, uint32_t{0x80000001}>(0)));
497 EXPECT_FALSE(
498 (IsBitCeilConstantExpression<uint32_t, uint32_t{0xffffffff}>(0)));
499
500 EXPECT_TRUE((IsBitCeilConstantExpression<uint64_t, uint64_t{0x0}>(0)));
501 EXPECT_TRUE(
502 (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000000}>(0)));
503 EXPECT_FALSE(
504 (IsBitCeilConstantExpression<uint64_t, uint64_t{0x8000000000000001}>(0)));
505 EXPECT_FALSE(
506 (IsBitCeilConstantExpression<uint64_t, uint64_t{0xffffffffffffffff}>(0)));
507 #endif
508
509 EXPECT_EQ(bit_ceil(0u), 1);
510 EXPECT_EQ(bit_ceil(1u), 1);
511 EXPECT_EQ(bit_ceil(2u), 2);
512 EXPECT_EQ(bit_ceil(3u), 4);
513 EXPECT_EQ(bit_ceil(4u), 4);
514 EXPECT_EQ(bit_ceil(1337u), 2048);
515 EXPECT_EQ(bit_ceil(65536u), 65536);
516 EXPECT_EQ(bit_ceil(65536u - 1337u), 65536);
517 EXPECT_EQ(bit_ceil(uint64_t{0x40000000000}), uint64_t{0x40000000000});
518 }
519
TEST(IntegralPowersOfTwo,Floor)520 TEST(IntegralPowersOfTwo, Floor) {
521 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
522 static_assert(bit_floor(0u) == 0, "");
523 static_assert(bit_floor(1u) == 1, "");
524 static_assert(bit_floor(2u) == 2, "");
525 static_assert(bit_floor(3u) == 2, "");
526 static_assert(bit_floor(4u) == 4, "");
527 static_assert(bit_floor(1337u) == 1024, "");
528 static_assert(bit_floor(65536u) == 65536, "");
529 static_assert(bit_floor(65536u - 1337u) == 32768, "");
530 static_assert(bit_floor(uint64_t{0x40000000000}) == uint64_t{0x40000000000},
531 "");
532 #endif
533
534 EXPECT_EQ(bit_floor(0u), 0);
535 EXPECT_EQ(bit_floor(1u), 1);
536 EXPECT_EQ(bit_floor(2u), 2);
537 EXPECT_EQ(bit_floor(3u), 2);
538 EXPECT_EQ(bit_floor(4u), 4);
539 EXPECT_EQ(bit_floor(1337u), 1024);
540 EXPECT_EQ(bit_floor(65536u), 65536);
541 EXPECT_EQ(bit_floor(65536u - 1337u), 32768);
542 EXPECT_EQ(bit_floor(uint64_t{0x40000000000}), uint64_t{0x40000000000});
543
544 for (int i = 0; i < 8; i++) {
545 uint8_t input = uint8_t{1} << i;
546 EXPECT_EQ(bit_floor(input), input);
547 if (i > 0) {
548 EXPECT_EQ(bit_floor(static_cast<uint8_t>(input + 1)), input);
549 }
550 }
551
552 for (int i = 0; i < 16; i++) {
553 uint16_t input = uint16_t{1} << i;
554 EXPECT_EQ(bit_floor(input), input);
555 if (i > 0) {
556 EXPECT_EQ(bit_floor(static_cast<uint16_t>(input + 1)), input);
557 }
558 }
559
560 for (int i = 0; i < 32; i++) {
561 uint32_t input = uint32_t{1} << i;
562 EXPECT_EQ(bit_floor(input), input);
563 if (i > 0) {
564 EXPECT_EQ(bit_floor(input + 1), input);
565 }
566 }
567
568 for (int i = 0; i < 64; i++) {
569 uint64_t input = uint64_t{1} << i;
570 EXPECT_EQ(bit_floor(input), input);
571 if (i > 0) {
572 EXPECT_EQ(bit_floor(input + 1), input);
573 }
574 }
575 }
576
TEST(IntegralPowersOfTwo,Width)577 TEST(IntegralPowersOfTwo, Width) {
578 #if ABSL_INTERNAL_HAS_CONSTEXPR_CLZ
579 static_assert(bit_width(uint8_t{}) == 0, "");
580 static_assert(bit_width(uint8_t{1}) == 1, "");
581 static_assert(bit_width(uint8_t{3}) == 2, "");
582 static_assert(bit_width(static_cast<uint8_t>(-1)) == 8, "");
583 static_assert(bit_width(uint16_t{}) == 0, "");
584 static_assert(bit_width(uint16_t{1}) == 1, "");
585 static_assert(bit_width(uint16_t{3}) == 2, "");
586 static_assert(bit_width(static_cast<uint16_t>(-1)) == 16, "");
587 static_assert(bit_width(uint32_t{}) == 0, "");
588 static_assert(bit_width(uint32_t{1}) == 1, "");
589 static_assert(bit_width(uint32_t{3}) == 2, "");
590 static_assert(bit_width(~uint32_t{}) == 32, "");
591 static_assert(bit_width(uint64_t{}) == 0, "");
592 static_assert(bit_width(uint64_t{1}) == 1, "");
593 static_assert(bit_width(uint64_t{3}) == 2, "");
594 static_assert(bit_width(~uint64_t{}) == 64, "");
595 #endif
596
597 EXPECT_EQ(bit_width(uint8_t{}), 0);
598 EXPECT_EQ(bit_width(uint8_t{1}), 1);
599 EXPECT_EQ(bit_width(uint8_t{3}), 2);
600 EXPECT_EQ(bit_width(static_cast<uint8_t>(-1)), 8);
601 EXPECT_EQ(bit_width(uint16_t{}), 0);
602 EXPECT_EQ(bit_width(uint16_t{1}), 1);
603 EXPECT_EQ(bit_width(uint16_t{3}), 2);
604 EXPECT_EQ(bit_width(static_cast<uint16_t>(-1)), 16);
605 EXPECT_EQ(bit_width(uint32_t{}), 0);
606 EXPECT_EQ(bit_width(uint32_t{1}), 1);
607 EXPECT_EQ(bit_width(uint32_t{3}), 2);
608 EXPECT_EQ(bit_width(~uint32_t{}), 32);
609 EXPECT_EQ(bit_width(uint64_t{}), 0);
610 EXPECT_EQ(bit_width(uint64_t{1}), 1);
611 EXPECT_EQ(bit_width(uint64_t{3}), 2);
612 EXPECT_EQ(bit_width(~uint64_t{}), 64);
613
614 for (int i = 0; i < 8; i++) {
615 EXPECT_EQ(bit_width(static_cast<uint8_t>(uint8_t{1} << i)), i + 1);
616 }
617
618 for (int i = 0; i < 16; i++) {
619 EXPECT_EQ(bit_width(static_cast<uint16_t>(uint16_t{1} << i)), i + 1);
620 }
621
622 for (int i = 0; i < 32; i++) {
623 EXPECT_EQ(bit_width(uint32_t{1} << i), i + 1);
624 }
625
626 for (int i = 0; i < 64; i++) {
627 EXPECT_EQ(bit_width(uint64_t{1} << i), i + 1);
628 }
629 }
630
631 // On GCC and Clang, anticiapte that implementations will be constexpr
632 #if defined(__GNUC__)
633 static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_POPCOUNT,
634 "popcount should be constexpr");
635 static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_CLZ, "clz should be constexpr");
636 static_assert(ABSL_INTERNAL_HAS_CONSTEXPR_CTZ, "ctz should be constexpr");
637 #endif
638
639 } // namespace
640 ABSL_NAMESPACE_END
641 } // namespace absl
642