SDSL 3.0.3
Succinct Data Structure Library
Loading...
Searching...
No Matches
uint256_t.hpp
Go to the documentation of this file.
1// Copyright (c) 2016, the SDSL Project Authors. All rights reserved.
2// Please see the AUTHORS file for details. Use of this source code is governed
3// by a BSD license that can be found in the LICENSE file.
8#ifndef INCLUDED_SDSL_UINT256
9#define INCLUDED_SDSL_UINT256
10
11#include <iostream>
12#include <stdint.h>
13#include <utility>
14
15#include <sdsl/bits.hpp>
16#include <sdsl/uint128_t.hpp>
17
18namespace sdsl
19{
20
22{
23public:
24 friend std::ostream & operator<<(std::ostream &, uint256_t const &);
25
26private:
27 uint64_t m_lo;
28 uint64_t m_mid;
29 uint128_t m_high;
30
31public:
32 inline uint256_t(uint64_t lo = 0, uint64_t mid = 0, uint128_t high = 0) : m_lo(lo), m_mid(mid), m_high(high)
33 {}
34
35 inline uint256_t(uint256_t const & x) : m_lo(x.m_lo), m_mid(x.m_mid), m_high(x.m_high)
36 {}
37
38 inline uint256_t(uint256_t && x) : m_lo(std::move(x.m_lo)), m_mid(std::move(x.m_mid)), m_high(std::move(x.m_high))
39 {}
40
42 {
43 m_lo = x.m_lo;
44 m_mid = x.m_mid;
45 m_high = x.m_high;
46 return *this;
47 }
48
50 {
51 m_lo = std::move(x.m_lo);
52 m_mid = std::move(x.m_mid);
53 m_high = std::move(x.m_high);
54 return *this;
55 }
56
57 inline uint16_t popcount()
58 {
59 return ((uint16_t)bits::cnt(m_lo)) + (uint16_t)bits::cnt(m_mid) + (uint16_t)bits::cnt(m_high >> 64)
60 + (uint16_t)bits::cnt(m_high);
61 }
62
63 inline uint16_t hi()
64 {
65 if (m_high == (uint128_t)0ULL)
66 {
67 if (m_mid)
68 {
69 return bits::hi(m_mid) + 64;
70 }
71 else
72 {
73 return bits::hi(m_lo);
74 }
75 }
76 else
77 {
78 uint64_t hh = (m_high >> 64);
79 if (hh)
80 {
81 return bits::hi(hh) + 192;
82 }
83 else
84 {
85 return bits::hi(m_high) + 128;
86 }
87 }
88 }
89
90 inline uint16_t select(uint32_t i)
91 {
92 uint16_t x = 0;
93 if ((x = (uint16_t)bits::cnt(m_lo)) >= i)
94 {
95 return bits::sel(m_lo, i);
96 }
97 i -= x;
98 if ((x = (uint16_t)bits::cnt(m_mid)) >= i)
99 {
100 return bits::sel(m_mid, i) + 64;
101 }
102 i -= x;
103 uint64_t hh = m_high >> 64;
104 uint64_t lh = m_high;
105 if ((x = (uint16_t)bits::cnt(lh)) >= i)
106 {
107 return bits::sel(lh, i) + 128;
108 }
109 i -= x;
110 return bits::sel(hh, i) + 192;
111 }
112
113 inline uint256_t & operator+=(uint256_t const & x)
114 {
115 uint128_t lo = (uint128_t)m_lo + x.m_lo;
116 uint128_t mid = (uint128_t)m_mid + x.m_mid + (lo >> 64);
117 m_lo = lo;
118 m_mid = mid;
119 m_high += x.m_high + (mid >> 64);
120 return *this;
121 // return uint256_t(lo, mid, m_high + x.m_high + (mid >> 64));
122 }
123
124 inline uint256_t operator+(uint256_t const & x)
125 {
126 uint128_t lo = ((uint128_t)m_lo) + x.m_lo;
127 uint128_t mid = (uint128_t)m_mid + x.m_mid + (lo >> 64);
128 return uint256_t(lo, mid, m_high + x.m_high + (mid >> 64));
129 }
130
131 inline uint256_t operator-(uint256_t const & x)
132 {
133 // add two's complement of x
134 uint128_t lo = (uint128_t)m_lo + (~x.m_lo) + (uint128_t)1ULL;
135 uint128_t mid = (uint128_t)m_mid + (~x.m_mid) + (lo >> 64);
136 return uint256_t(lo, mid, m_high + (~x.m_high) + (mid >> 64));
137 }
138
139 inline uint256_t & operator-=(uint256_t const & x)
140 {
141 // add two's complement of x
142 uint128_t lo = (uint128_t)m_lo + (~x.m_lo) + (uint128_t)1ULL;
143 uint128_t mid = (uint128_t)m_mid + (~x.m_mid) + (lo >> 64);
144 m_lo = lo;
145 m_mid = mid;
146 m_high += (~x.m_high) + (mid >> 64);
147 return *this;
148 }
149
150 inline uint256_t operator|(uint256_t const & x)
151 {
152 return uint256_t(m_lo | x.m_lo, m_mid | x.m_mid, m_high | x.m_high);
153 }
154
155 inline uint256_t & operator|=(uint256_t const & x)
156 {
157 m_lo |= x.m_lo;
158 m_mid |= x.m_mid;
159 m_high |= x.m_high;
160 return *this;
161 }
162
163 inline uint256_t operator&(uint256_t const & x)
164 {
165 return uint256_t(m_lo & x.m_lo, m_mid & x.m_mid, m_high & x.m_high);
166 }
167 /* // is not needed since we can convert uint256_t to uint64_t
168 * uint64_t operator&(uint64_t x){
169 * return m_lo & x;
170 * }
171 */
172
173 inline uint256_t operator<<(int x) const
174 {
175 if (x < 128)
176 {
177 uint128_t high = m_high << x;
178 uint128_t low = (((uint128_t)m_mid << 64) | m_lo);
179 high |= (low >> (128 - x));
180 low = low << x;
181 return uint256_t(low, low >> 64, high);
182 }
183 else
184 { // x >= 128
185 uint128_t high = (((uint128_t)m_mid << 64) | m_lo) << (x - 128); // TODO: check x==128
186 return uint256_t(0, 0, high);
187 }
188 }
189
190 inline uint256_t operator>>(int x) const
191 {
192 if (x < 128)
193 {
194 uint128_t low = (((uint128_t)m_mid << 64) | m_lo) >> x;
195 low |= ((m_high << (127 - x)) << 1);
196 return uint256_t(low, low >> 64, m_high >> x);
197 }
198 else
199 { // x >= 128
200 uint128_t low = (m_high >> (x - 128)); // TODO: check x=128
201 return uint256_t(low, low >> 64, 0);
202 }
203 }
204
205 inline uint256_t & operator=(uint64_t const & x)
206 {
207 m_high = 0;
208 m_mid = 0;
209 m_lo = x;
210 return *this;
211 }
212
213 inline bool operator==(uint256_t const & x) const
214 {
215 return (m_lo == x.m_lo) and (m_mid == x.m_mid) and (m_high == x.m_high);
216 }
217
218 inline bool operator!=(uint256_t const & x) const
219 {
220 return !(*this == x);
221 }
222
223 inline bool operator>=(uint256_t const & x) const
224 {
225 if (m_high != x.m_high)
226 {
227 return m_high > x.m_high;
228 }
229 if (m_mid != x.m_mid)
230 {
231 return m_mid > x.m_mid;
232 }
233 else
234 {
235 return m_lo >= x.m_lo;
236 }
237 }
238
239 inline bool operator<=(uint256_t const & x) const
240 {
241 if (m_high != x.m_high)
242 {
243 return m_high < x.m_high;
244 }
245 if (m_mid != x.m_mid)
246 {
247 return m_mid < x.m_mid;
248 }
249 else
250 {
251 return m_lo <= x.m_lo;
252 }
253 }
254
255 inline bool operator>(uint256_t const & x) const
256 {
257 if (m_high != x.m_high)
258 {
259 return m_high > x.m_high;
260 }
261 if (m_mid != x.m_mid)
262 {
263 return m_mid > x.m_mid;
264 }
265 else
266 {
267 return m_lo > x.m_lo;
268 }
269 }
270
271 inline bool operator>(uint64_t const & x) const
272 {
273 if (m_high > (uint128_t)0ULL or m_mid > (uint128_t)0ULL)
274 {
275 return true;
276 }
277 return m_lo > x;
278 }
279
280 inline bool operator<(uint256_t const & x) const
281 {
282 if (m_high != x.m_high)
283 {
284 return m_high < x.m_high;
285 }
286 if (m_mid != x.m_mid)
287 {
288 return m_mid < x.m_mid;
289 }
290 else
291 {
292 return m_lo < x.m_lo;
293 }
294 }
295
296 inline operator uint64_t()
297 {
298 return m_lo;
299 }
300};
301
302inline std::ostream & operator<<(std::ostream & os, uint256_t const & x)
303{
304 uint64_t X[4] = {(uint64_t)(x.m_high >> 64), (uint64_t)x.m_high, x.m_mid, x.m_lo};
305 for (int j = 0; j < 4; ++j)
306 {
307 for (int i = 0; i < 16; ++i)
308 {
309 os << std::hex << ((X[j] >> 60) & 0xFULL) << std::dec;
310 X[j] <<= 4;
311 }
312 }
313 return os;
314}
315
316} // namespace sdsl
317
318#endif
bits.hpp contains the sdsl::bits class.
uint256_t(uint64_t lo=0, uint64_t mid=0, uint128_t high=0)
Definition uint256_t.hpp:32
bool operator!=(uint256_t const &x) const
uint256_t operator>>(int x) const
uint256_t operator&(uint256_t const &x)
uint256_t & operator=(uint256_t const &x)
Definition uint256_t.hpp:41
bool operator<=(uint256_t const &x) const
friend std::ostream & operator<<(std::ostream &, uint256_t const &)
uint256_t & operator-=(uint256_t const &x)
bool operator>(uint256_t const &x) const
uint256_t operator<<(int x) const
bool operator<(uint256_t const &x) const
uint256_t & operator|=(uint256_t const &x)
bool operator>=(uint256_t const &x) const
bool operator==(uint256_t const &x) const
uint256_t & operator=(uint64_t const &x)
uint256_t operator|(uint256_t const &x)
uint16_t select(uint32_t i)
Definition uint256_t.hpp:90
uint256_t operator-(uint256_t const &x)
uint16_t popcount()
Definition uint256_t.hpp:57
uint16_t hi()
Definition uint256_t.hpp:63
bool operator>(uint64_t const &x) const
uint256_t & operator=(uint256_t &&x)
Definition uint256_t.hpp:49
uint256_t(uint256_t &&x)
Definition uint256_t.hpp:38
uint256_t & operator+=(uint256_t const &x)
uint256_t operator+(uint256_t const &x)
uint256_t(uint256_t const &x)
Definition uint256_t.hpp:35
Namespace for the succinct data structure library.
std::ostream & operator<<(std::ostream &os, bp_interval< t_int > const &interval)
static constexpr uint32_t sel(uint64_t x, uint32_t i)
Calculate the position of the i-th rightmost 1 bit in the 64bit integer x.
Definition bits.hpp:586
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition bits.hpp:653
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition bits.hpp:486
uint128_t.hpp contains contains the definition of a 128-bit unsigned integer type.