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 #include <bit> 20 #include <cstdint> 21 #include <limits> 22 23 class BitsUtil { 24 public: 25 // ⌊log2(n)⌋, resp. numbers of bits needed to represent n in binary encoding 26 // minus one. Input cannot be zero. 27 // Same as util/bits/Bits::Log2FloorNonZero64(..). 28 static uint8_t Log2FloorNonZero64(uint64_t n); 29 30 private: 31 static uint8_t CountLeadingZeros64(uint64_t x); 32 }; 33 Log2FloorNonZero64(uint64_t n)34inline uint8_t BitsUtil::Log2FloorNonZero64(uint64_t n) { 35 assert(n != 0); 36 return std::numeric_limits<uint64_t>::digits - CountLeadingZeros64(n) - 1; 37 } 38 CountLeadingZeros64(uint64_t x)39inline uint8_t BitsUtil::CountLeadingZeros64(uint64_t x) { 40 uint8_t zeroes = 60; 41 if (x >> 32) { 42 zeroes -= 32; 43 x >>= 32; 44 } 45 if (x >> 16) { 46 zeroes -= 16; 47 x >>= 16; 48 } 49 if (x >> 8) { 50 zeroes -= 8; 51 x >>= 8; 52 } 53 if (x >> 4) { 54 zeroes -= 4; 55 x >>= 4; 56 } 57 return "\4\3\2\2\1\1\1\1\0\0\0\0\0\0\0"[x] + zeroes; 58 } 59