log2.h 1.9 KB

1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071
  1. //===----------------------------------------------------------------------===//
  2. //
  3. // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
  4. // See https://llvm.org/LICENSE.txt for license information.
  5. // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
  6. //
  7. //===----------------------------------------------------------------------===//
  8. #ifndef _LIBCPP___RANDOM_LOG2_H
  9. #define _LIBCPP___RANDOM_LOG2_H
  10. #include <__config>
  11. #include <__type_traits/conditional.h>
  12. #include <cstddef>
  13. #if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)
  14. # pragma GCC system_header
  15. #endif
  16. _LIBCPP_BEGIN_NAMESPACE_STD
  17. template <class _UIntType, _UIntType _Xp, size_t _Rp>
  18. struct __log2_imp;
  19. template <unsigned long long _Xp, size_t _Rp>
  20. struct __log2_imp<unsigned long long, _Xp, _Rp>
  21. {
  22. static const size_t value = _Xp & ((unsigned long long)(1) << _Rp) ? _Rp
  23. : __log2_imp<unsigned long long, _Xp, _Rp - 1>::value;
  24. };
  25. template <unsigned long long _Xp>
  26. struct __log2_imp<unsigned long long, _Xp, 0>
  27. {
  28. static const size_t value = 0;
  29. };
  30. template <size_t _Rp>
  31. struct __log2_imp<unsigned long long, 0, _Rp>
  32. {
  33. static const size_t value = _Rp + 1;
  34. };
  35. #ifndef _LIBCPP_HAS_NO_INT128
  36. template <__uint128_t _Xp, size_t _Rp>
  37. struct __log2_imp<__uint128_t, _Xp, _Rp>
  38. {
  39. static const size_t value = (_Xp >> 64)
  40. ? (64 + __log2_imp<unsigned long long, (_Xp >> 64), 63>::value)
  41. : __log2_imp<unsigned long long, _Xp, 63>::value;
  42. };
  43. #endif // _LIBCPP_HAS_NO_INT128
  44. template <class _UIntType, _UIntType _Xp>
  45. struct __log2
  46. {
  47. static const size_t value = __log2_imp<
  48. #ifndef _LIBCPP_HAS_NO_INT128
  49. __conditional_t<sizeof(_UIntType) <= sizeof(unsigned long long), unsigned long long, __uint128_t>,
  50. #else
  51. unsigned long long,
  52. #endif // _LIBCPP_HAS_NO_INT128
  53. _Xp,
  54. sizeof(_UIntType) * __CHAR_BIT__ - 1>::value;
  55. };
  56. _LIBCPP_END_NAMESPACE_STD
  57. #endif // _LIBCPP___RANDOM_LOG2_H