SDSL 3.0.1
Succinct Data Structure Library
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
13#include <sdsl/bits.hpp>
14#include <sdsl/uint128_t.hpp>
15
16namespace sdsl
17{
18
20{
21 public:
22 friend std::ostream & operator<<(std::ostream &, const uint256_t &);
23
24 private:
25 uint64_t m_lo;
26 uint64_t m_mid;
27 uint128_t m_high;
28
29 public:
30 inline uint256_t(uint64_t lo = 0, uint64_t mid = 0, uint128_t high = 0)
31 : m_lo(lo)
32 , m_mid(mid)
33 , m_high(high)
34 {}
35
36 inline uint256_t(const uint256_t & x)
37 : m_lo(x.m_lo)
38 , m_mid(x.m_mid)
39 , m_high(x.m_high)
40 {}
41
42 inline uint256_t(uint256_t && x)
43 : m_lo(std::move(x.m_lo))
44 , m_mid(std::move(x.m_mid))
45 , m_high(std::move(x.m_high))
46 {}
47
49 {
50 m_lo = x.m_lo;
51 m_mid = x.m_mid;
52 m_high = x.m_high;
53 return *this;
54 }
55
57 {
58 m_lo = std::move(x.m_lo);
59 m_mid = std::move(x.m_mid);
60 m_high = std::move(x.m_high);
61 return *this;
62 }
63
64 inline uint16_t popcount()
65 {
66 return ((uint16_t)bits::cnt(m_lo)) + (uint16_t)bits::cnt(m_mid) + (uint16_t)bits::cnt(m_high >> 64) +
67 (uint16_t)bits::cnt(m_high);
68 }
69
70 inline uint16_t hi()
71 {
72 if (m_high == (uint128_t)0ULL)
73 {
74 if (m_mid) { return bits::hi(m_mid) + 64; }
75 else
76 {
77 return bits::hi(m_lo);
78 }
79 }
80 else
81 {
82 uint64_t hh = (m_high >> 64);
83 if (hh) { return bits::hi(hh) + 192; }
84 else
85 {
86 return bits::hi(m_high) + 128;
87 }
88 }
89 }
90
91 inline uint16_t select(uint32_t i)
92 {
93 uint16_t x = 0;
94 if ((x = (uint16_t)bits::cnt(m_lo)) >= i) { return bits::sel(m_lo, i); }
95 i -= x;
96 if ((x = (uint16_t)bits::cnt(m_mid)) >= i) { return bits::sel(m_mid, i) + 64; }
97 i -= x;
98 uint64_t hh = m_high >> 64;
99 uint64_t lh = m_high;
100 if ((x = (uint16_t)bits::cnt(lh)) >= i) { return bits::sel(lh, i) + 128; }
101 i -= x;
102 return bits::sel(hh, i) + 192;
103 }
104
105 inline uint256_t & operator+=(const uint256_t & x)
106 {
107 uint128_t lo = (uint128_t)m_lo + x.m_lo;
108 uint128_t mid = (uint128_t)m_mid + x.m_mid + (lo >> 64);
109 m_lo = lo;
110 m_mid = mid;
111 m_high += x.m_high + (mid >> 64);
112 return *this;
113 // return uint256_t(lo, mid, m_high + x.m_high + (mid >> 64));
114 }
115
116 inline uint256_t operator+(const uint256_t & x)
117 {
118 uint128_t lo = ((uint128_t)m_lo) + x.m_lo;
119 uint128_t mid = (uint128_t)m_mid + x.m_mid + (lo >> 64);
120 return uint256_t(lo, mid, m_high + x.m_high + (mid >> 64));
121 }
122
123 inline uint256_t operator-(const uint256_t & x)
124 {
125 // add two's complement of x
126 uint128_t lo = (uint128_t)m_lo + (~x.m_lo) + (uint128_t)1ULL;
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-=(const uint256_t & 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 m_lo = lo;
137 m_mid = mid;
138 m_high += (~x.m_high) + (mid >> 64);
139 return *this;
140 }
141
142 inline uint256_t operator|(const uint256_t & x)
143 {
144 return uint256_t(m_lo | x.m_lo, m_mid | x.m_mid, m_high | x.m_high);
145 }
146
147 inline uint256_t & operator|=(const uint256_t & x)
148 {
149 m_lo |= x.m_lo;
150 m_mid |= x.m_mid;
151 m_high |= x.m_high;
152 return *this;
153 }
154
155 inline uint256_t operator&(const uint256_t & x)
156 {
157 return uint256_t(m_lo & x.m_lo, m_mid & x.m_mid, m_high & x.m_high);
158 }
159 /* // is not needed since we can convert uint256_t to uint64_t
160 * uint64_t operator&(uint64_t x){
161 * return m_lo & x;
162 * }
163 */
164
165 inline uint256_t operator<<(int x) const
166 {
167 if (x < 128)
168 {
169 uint128_t high = m_high << x;
170 uint128_t low = (((uint128_t)m_mid << 64) | m_lo);
171 high |= (low >> (128 - x));
172 low = low << x;
173 return uint256_t(low, low >> 64, high);
174 }
175 else
176 { // x >= 128
177 uint128_t high = (((uint128_t)m_mid << 64) | m_lo) << (x - 128); // TODO: check x==128
178 return uint256_t(0, 0, high);
179 }
180 }
181
182 inline uint256_t operator>>(int x) const
183 {
184 if (x < 128)
185 {
186 uint128_t low = (((uint128_t)m_mid << 64) | m_lo) >> x;
187 low |= ((m_high << (127 - x)) << 1);
188 return uint256_t(low, low >> 64, m_high >> x);
189 }
190 else
191 { // x >= 128
192 uint128_t low = (m_high >> (x - 128)); // TODO: check x=128
193 return uint256_t(low, low >> 64, 0);
194 }
195 }
196
197 inline uint256_t & operator=(const uint64_t & x)
198 {
199 m_high = 0;
200 m_mid = 0;
201 m_lo = x;
202 return *this;
203 }
204
205 inline bool operator==(const uint256_t & x) const
206 {
207 return (m_lo == x.m_lo) and (m_mid == x.m_mid) and (m_high == x.m_high);
208 }
209
210 inline bool operator!=(const uint256_t & x) const { return !(*this == x); }
211
212 inline bool operator>=(const uint256_t & x) const
213 {
214 if (m_high != x.m_high) { return m_high > x.m_high; }
215 if (m_mid != x.m_mid) { return m_mid > x.m_mid; }
216 else
217 {
218 return m_lo >= x.m_lo;
219 }
220 }
221
222 inline bool operator<=(const uint256_t & x) const
223 {
224 if (m_high != x.m_high) { return m_high < x.m_high; }
225 if (m_mid != x.m_mid) { return m_mid < x.m_mid; }
226 else
227 {
228 return m_lo <= x.m_lo;
229 }
230 }
231
232 inline bool operator>(const uint256_t & x) const
233 {
234 if (m_high != x.m_high) { return m_high > x.m_high; }
235 if (m_mid != x.m_mid) { return m_mid > x.m_mid; }
236 else
237 {
238 return m_lo > x.m_lo;
239 }
240 }
241
242 inline bool operator>(const uint64_t & x) const
243 {
244 if (m_high > (uint128_t)0ULL or m_mid > (uint128_t)0ULL) { return true; }
245 return m_lo > x;
246 }
247
248 inline bool operator<(const uint256_t & x) const
249 {
250 if (m_high != x.m_high) { return m_high < x.m_high; }
251 if (m_mid != x.m_mid) { return m_mid < x.m_mid; }
252 else
253 {
254 return m_lo < x.m_lo;
255 }
256 }
257
258 inline operator uint64_t() { return m_lo; }
259};
260
261inline std::ostream & operator<<(std::ostream & os, const uint256_t & x)
262{
263 uint64_t X[4] = { (uint64_t)(x.m_high >> 64), (uint64_t)x.m_high, x.m_mid, x.m_lo };
264 for (int j = 0; j < 4; ++j)
265 {
266 for (int i = 0; i < 16; ++i)
267 {
268 os << std::hex << ((X[j] >> 60) & 0xFULL) << std::dec;
269 X[j] <<= 4;
270 }
271 }
272 return os;
273}
274
275} // namespace sdsl
276
277#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:30
uint256_t & operator|=(const uint256_t &x)
Definition: uint256_t.hpp:147
uint256_t & operator=(const uint256_t &x)
Definition: uint256_t.hpp:48
uint256_t operator&(const uint256_t &x)
Definition: uint256_t.hpp:155
uint256_t operator>>(int x) const
Definition: uint256_t.hpp:182
bool operator>=(const uint256_t &x) const
Definition: uint256_t.hpp:212
bool operator>(const uint64_t &x) const
Definition: uint256_t.hpp:242
uint256_t & operator-=(const uint256_t &x)
Definition: uint256_t.hpp:131
uint256_t & operator+=(const uint256_t &x)
Definition: uint256_t.hpp:105
friend std::ostream & operator<<(std::ostream &, const uint256_t &)
Definition: uint256_t.hpp:261
uint256_t(const uint256_t &x)
Definition: uint256_t.hpp:36
bool operator<(const uint256_t &x) const
Definition: uint256_t.hpp:248
uint256_t operator<<(int x) const
Definition: uint256_t.hpp:165
bool operator==(const uint256_t &x) const
Definition: uint256_t.hpp:205
bool operator>(const uint256_t &x) const
Definition: uint256_t.hpp:232
uint16_t select(uint32_t i)
Definition: uint256_t.hpp:91
uint256_t operator|(const uint256_t &x)
Definition: uint256_t.hpp:142
bool operator!=(const uint256_t &x) const
Definition: uint256_t.hpp:210
uint256_t operator+(const uint256_t &x)
Definition: uint256_t.hpp:116
uint16_t popcount()
Definition: uint256_t.hpp:64
uint16_t hi()
Definition: uint256_t.hpp:70
bool operator<=(const uint256_t &x) const
Definition: uint256_t.hpp:222
uint256_t operator-(const uint256_t &x)
Definition: uint256_t.hpp:123
uint256_t & operator=(uint256_t &&x)
Definition: uint256_t.hpp:56
uint256_t(uint256_t &&x)
Definition: uint256_t.hpp:42
uint256_t & operator=(const uint64_t &x)
Definition: uint256_t.hpp:197
Namespace for the succinct data structure library.
std::ostream & operator<<(std::ostream &os, const bp_interval< t_int > &interval)
Definition: cst_sct3.hpp:1331
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:584
static constexpr uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:651
static constexpr uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:484
uint128_t.hpp contains contains the definition of a 128-bit unsigned integer type.