SDSL  3.0.0
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 
15 namespace sdsl
16 {
17 
18 #if defined(__GNUC__)
19 
20 typedef unsigned int uint128_t __attribute__((mode(TI)));
21 
22 #else
23 
24 class uint128_t
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 
220 inline 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
uint128_t & operator-=(const uint128_t &x)
Definition: uint128_t.hpp:108
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
uint128_t & operator|=(const uint128_t &x)
Definition: uint128_t.hpp:118
uint128_t & operator=(const uint128_t &x)
Definition: uint128_t.hpp:49
uint128_t & operator+=(const uint64_t &x)
Definition: uint128_t.hpp:88
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 uint64_t &x)
Definition: uint128_t.hpp:161
uint128_t & operator=(uint128_t &&x)
Definition: uint128_t.hpp:56
uint128_t & operator+=(const uint128_t &x)
Definition: uint128_t.hpp:82
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
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
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:1332
static SDSL_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:594
static SDSL_CONSTEXPR uint32_t hi(uint64_t x)
Position of the most significant set bit the 64-bit word x.
Definition: bits.hpp:661
static SDSL_CONSTEXPR uint64_t cnt(uint64_t x)
Counts the number of set bits in x.
Definition: bits.hpp:494