summaryrefslogtreecommitdiff
path: root/absl/numeric/bits.h
blob: df81b9a929e4e3be80e5c82164fb9453509bad3d (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
// Copyright 2020 The Abseil Authors
//
// Licensed under the Apache License, Version 2.0 (the "License");
// you may not use this file except in compliance with the License.
// You may obtain a copy of the License at
//
//     https://www.apache.org/licenses/LICENSE-2.0
//
// Unless required by applicable law or agreed to in writing, software
// distributed under the License is distributed on an "AS IS" BASIS,
// WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
// See the License for the specific language governing permissions and
// limitations under the License.
//
// -----------------------------------------------------------------------------
// File: bits.h
// -----------------------------------------------------------------------------
//
// This file contains implementations of C++20's bitwise math functions, as
// defined by:
//
// P0553R4:
//  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p0553r4.html
// P0556R3:
//  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2018/p0556r3.html
// P1355R2:
//  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2019/p1355r2.html
// P1956R1:
//  http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2020/p1956r1.pdf
//
// When using a standard library that implements these functions, we use the
// standard library's implementation.

#ifndef ABSL_NUMERIC_BITS_H_
#define ABSL_NUMERIC_BITS_H_

#include <cstdint>
#include <limits>
#include <type_traits>

#if (defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L) || \
    (defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L)
#include <bit>
#endif

#include "absl/base/attributes.h"
#include "absl/base/config.h"
#include "absl/numeric/internal/bits.h"

namespace absl {
ABSL_NAMESPACE_BEGIN

#if !(defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L)
// rotating
template <class T>
ABSL_MUST_USE_RESULT constexpr
    typename std::enable_if<std::is_unsigned<T>::value, T>::type
    rotl(T x, int s) noexcept {
  return numeric_internal::RotateLeft(x, s);
}

template <class T>
ABSL_MUST_USE_RESULT constexpr
    typename std::enable_if<std::is_unsigned<T>::value, T>::type
    rotr(T x, int s) noexcept {
  return numeric_internal::RotateRight(x, s);
}

// Counting functions
//
// While these functions are typically constexpr, on some platforms, they may
// not be marked as constexpr due to constraints of the compiler/available
// intrinsics.
template <class T>
ABSL_INTERNAL_CONSTEXPR_CLZ inline
    typename std::enable_if<std::is_unsigned<T>::value, int>::type
    countl_zero(T x) noexcept {
  return numeric_internal::CountLeadingZeroes(x);
}

template <class T>
ABSL_INTERNAL_CONSTEXPR_CLZ inline
    typename std::enable_if<std::is_unsigned<T>::value, int>::type
    countl_one(T x) noexcept {
  // Avoid integer promotion to a wider type
  return countl_zero(static_cast<T>(~x));
}

template <class T>
ABSL_INTERNAL_CONSTEXPR_CTZ inline
    typename std::enable_if<std::is_unsigned<T>::value, int>::type
    countr_zero(T x) noexcept {
  return numeric_internal::CountTrailingZeroes(x);
}

template <class T>
ABSL_INTERNAL_CONSTEXPR_CTZ inline
    typename std::enable_if<std::is_unsigned<T>::value, int>::type
    countr_one(T x) noexcept {
  // Avoid integer promotion to a wider type
  return countr_zero(static_cast<T>(~x));
}

template <class T>
ABSL_INTERNAL_CONSTEXPR_POPCOUNT inline
    typename std::enable_if<std::is_unsigned<T>::value, int>::type
    popcount(T x) noexcept {
  return numeric_internal::Popcount(x);
}
#else  // defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L

using std::countl_one;
using std::countl_zero;
using std::countr_one;
using std::countr_zero;
using std::popcount;
using std::rotl;
using std::rotr;

#endif

#if !(defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L)
// Returns: true if x is an integral power of two; false otherwise.
template <class T>
constexpr inline typename std::enable_if<std::is_unsigned<T>::value, bool>::type
has_single_bit(T x) noexcept {
  return x != 0 && (x & (x - 1)) == 0;
}

// Returns: If x == 0, 0; otherwise one plus the base-2 logarithm of x, with any
// fractional part discarded.
template <class T>
ABSL_INTERNAL_CONSTEXPR_CLZ inline
    typename std::enable_if<std::is_unsigned<T>::value, int>::type
    bit_width(T x) noexcept {
  return std::numeric_limits<T>::digits - countl_zero(x);
}

// Returns: If x == 0, 0; otherwise the maximal value y such that
// has_single_bit(y) is true and y <= x.
template <class T>
ABSL_INTERNAL_CONSTEXPR_CLZ inline
    typename std::enable_if<std::is_unsigned<T>::value, T>::type
    bit_floor(T x) noexcept {
  return x == 0 ? 0 : T{1} << (bit_width(x) - 1);
}

// Returns: N, where N is the smallest power of 2 greater than or equal to x.
//
// Preconditions: N is representable as a value of type T.
template <class T>
ABSL_INTERNAL_CONSTEXPR_CLZ inline
    typename std::enable_if<std::is_unsigned<T>::value, T>::type
    bit_ceil(T x) {
  // If T is narrower than unsigned, T{1} << bit_width will be promoted.  We
  // want to force it to wraparound so that bit_ceil of an invalid value are not
  // core constant expressions.
  //
  // BitCeilNonPowerOf2 triggers an overflow in constexpr contexts if we would
  // undergo promotion to unsigned but not fit the result into T without
  // truncation.
  return has_single_bit(x) ? T{1} << (bit_width(x) - 1)
                           : numeric_internal::BitCeilNonPowerOf2(x);
}
#else  // defined(__cpp_lib_int_pow2) && __cpp_lib_int_pow2 >= 202002L

using std::bit_ceil;
using std::bit_floor;
using std::bit_width;
using std::has_single_bit;

#endif

ABSL_NAMESPACE_END
}  // namespace absl

#endif  // ABSL_NUMERIC_BITS_H_