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