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