1 /*
2  * Copyright 2021 Google LLC
3  *
4  * Licensed under the Apache License, Version 2.0 (the "License");
5  * you may not use this file except in compliance with the License.
6  * You may obtain a copy of the License at
7  *
8  *     http://www.apache.org/licenses/LICENSE-2.0
9  *
10  * Unless required by applicable law or agreed to in writing, software
11  * distributed under the License is distributed on an "AS IS" BASIS,
12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13  * See the License for the specific language governing permissions and
14  * limitations under the License.
15  */
16 #pragma once
17 
18 #include <assert.h>
19 
20 #include <bit>
21 #include <cstdint>
22 #include <limits>
23 
24 class BitsUtil {
25 public:
26     // ⌊log2(n)⌋, resp. numbers of bits needed to represent n in binary encoding
27     // minus one. Input cannot be zero.
28     // Same as util/bits/Bits::Log2FloorNonZero64(..).
29     static uint8_t Log2FloorNonZero64(uint64_t n);
30 
31 private:
32     static uint8_t CountLeadingZeros64(uint64_t x);
33 };
34 
Log2FloorNonZero64(uint64_t n)35 inline uint8_t BitsUtil::Log2FloorNonZero64(uint64_t n) {
36     assert(n != 0);
37     return std::numeric_limits<uint64_t>::digits - CountLeadingZeros64(n) - 1;
38 }
39 
CountLeadingZeros64(uint64_t x)40 inline uint8_t BitsUtil::CountLeadingZeros64(uint64_t x) {
41     uint8_t zeroes = 60;
42     if (x >> 32) {
43         zeroes -= 32;
44         x >>= 32;
45     }
46     if (x >> 16) {
47         zeroes -= 16;
48         x >>= 16;
49     }
50     if (x >> 8) {
51         zeroes -= 8;
52         x >>= 8;
53     }
54     if (x >> 4) {
55         zeroes -= 4;
56         x >>= 4;
57     }
58     return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes;
59 }
60