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