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
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
|
// Copyright 2024-2025, Amlal El Mahrouss (amlal@nekernel.org)
// Licensed under the Apache License, Version 2.0 (see LICENSE file)
// Official repository: https://github.com/nekernel-org/nekernel
#ifndef UTL_BIT_H
#define UTL_BIT_H
#include <bit>
namespace utl {
/**
* @brief Size of object in terms of bits.
*
* @tparam T Object type
* @return Number of bits
*/
template <class T>
constexpr auto bit_size() {
return sizeof(T) * 8;
}
/**
* @brief Integer with all bits set to 1.
*
* @tparam T Integer type
* @return All set integer
*/
template <class T>
constexpr T bit_full() {
return T(-1);
}
/**
* @brief Wrap around mask for power of two number of bits
* within given integer type. For example:
* [ bit_wrap<uint8_t> = 8 - 1 = 0b111 ]
* [ bit_wrap<uint16_t> = 16 - 1 = 0b1111 ]
* [ bit_wrap<uint32_t> = 32 - 1 = 0b11111 ]
*
* @tparam T Integer type
* @return Wrap around mask for number of bits
*/
template <class T>
constexpr T bit_wrap() {
return bit_size<T>() - 1;
}
/**
* @brief Number of bits to fit bit_wrap<T> result, in other words
* bit width of (sizeof(T) * 8 - 1). For example:
* [ bit_shft<uint8_t> = bit_width(0b111) = 3 ]
* [ bit_shft<uint16_t> = bit_width(0b1111) = 4 ]
* [ bit_shft<uint32_t> = bit_width(0b11111) = 5 ]
*
* @tparam T Integer type
* @return Number of bits to shift to divide by sizeof(T) * 8
*/
template <class T>
constexpr auto bit_shft() {
return std::bit_width(bit_wrap<T>());
}
/**
* @brief Round up division by number of bits within given integer type,
* which sizeof(T) * 8 is power of two.
*
* @tparam T Inetegr type
* @param x Dividend
* @return Quotient
*/
template <class T>
constexpr auto bit_ceil(auto x) {
return (x + bit_wrap<T>()) >> bit_shft<T>();
}
/**
* @brief Count leading zeros.
*
* @param x Unsigned integer argument
* @return Number of leading zeros
*/
constexpr unsigned cntlz(auto x) {
if constexpr (std::is_same_v<decltype(x), int>)
return std::countl_zero(unsigned(x));
else
return std::countl_zero(x);
}
/**
* @brief Count trailing zeros.
*
* @param x Unsigned integer argument
* @return Number of trailing zeros
*/
constexpr unsigned cnttz(auto x) {
if constexpr (std::is_same_v<decltype(x), int>)
return std::countr_zero(unsigned(x));
else
return std::countr_zero(x);
}
/**
* @brief Get number of words (integers) required to store N bits.
*
* @tparam T Word integer type
* @param n Number of bits to store
* @return Number of words
*/
template <class T>
constexpr size_t words_in_bits(size_t n) {
return (n >> bit_shft<T>()) + !!(n & bit_wrap<T>());
}
/**
* @brief Get number of bytes required to store N bits.
*
* @param n Number of bits to store
* @return Number of bytes
*/
constexpr size_t bytes_in_bits(size_t n) {
return words_in_bits<uint8_t>(n);
}
/**
* @brief Make integer with bit at given position.
*
* @tparam T Inetegr type
* @param n Bit position
* @return Integer with set bit
*/
template <class T = unsigned>
constexpr T bit(int n) {
return T(1) << n;
}
/**
* @brief Get n-th bit of an integer.
*
* @tparam T Integer type
* @param x Integer
* @param n Bit position from LSB
* @return true if set
*/
template <class T>
constexpr bool get_bit(T x, int n) {
return (x >> n) & 1;
}
/**
* @brief Set n-th bit of an integer.
*
* @tparam T Integer type
* @param x Integer
* @param n Bit position from LSB
*/
template <class T>
constexpr void set_bit(T& x, int n) {
x |= 1 << n;
}
/**
* @brief Clear n-th bit of an integer.
*
* @tparam T Integer type
* @param x Integer
* @param n Bit position from LSB
*/
template <class T>
constexpr void clr_bit(T& x, int n) {
x &= ~(1 << n);
}
/**
* @brief Get n-th bit in array of words (starting from LSB).
*
* @tparam T Word type
* @param p Array of words
* @param n Index of bit to get
* @return true if set
*/
template <class T>
constexpr bool get_arr_bit(const T* p, unsigned n) {
return get_bit(p[n >> bit_shft<T>()], n & bit_wrap<T>());
}
/**
* @brief Set n-th bit in array of words (starting from LSB).
*
* @tparam T Word type
* @param p Array of words
* @param n Index of bit to set
*/
template <class T>
constexpr void set_arr_bit(T* p, unsigned n) {
set_bit(p[n >> bit_shft<T>()], n & bit_wrap<T>());
}
/**
* @brief Clear n-th bit in array of words (starting from LSB).
*
* @tparam T Word type
* @param p Array of words
* @param n Index of bit to clear
*/
template <class T>
constexpr void clr_arr_bit(T* p, unsigned n) {
clr_bit(p[n >> bit_shft<T>()], n & bit_wrap<T>());
}
/**
* @brief Shift bits left in array of integer elements from least significant bit
* and considering 0-th byte as the right most.
* uint16_t example: 0b10000000'11100001 ==> 0b00000001'11000010.
*
* @tparam T Integer type
* @tparam L Length of array
* @param x Array of integers, nullptr not acceptable!
* @param len Number of elements
*/
template <class T, size_t L>
constexpr void shift_left(T (&x)[L]) {
for (int i = L - 1; i > 0; --i) {
x[i] <<= 1;
x[i] |= x[i - 1] >> bit_wrap<T>();
}
x[0] <<= 1;
}
} // namespace utl
#endif
|
