SDSL  3.0.0
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 
16 namespace sdsl
17 {
18 
19 class uint256_t
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 
261 inline 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: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:147
uint256_t & operator=(uint256_t &&x)
Definition: uint256_t.hpp:56
uint256_t(const uint256_t &x)
Definition: uint256_t.hpp:36
friend std::ostream & operator<<(std::ostream &, const uint256_t &)
Definition: uint256_t.hpp:261
bool operator<(const uint256_t &x) const
Definition: uint256_t.hpp:248
uint256_t operator<<(int x) const
Definition: uint256_t.hpp:165
uint256_t & operator-=(const uint256_t &x)
Definition: uint256_t.hpp:131
uint256_t & operator=(const uint64_t &x)
Definition: uint256_t.hpp:197
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(uint256_t &&x)
Definition: uint256_t.hpp:42
uint256_t & operator+=(const uint256_t &x)
Definition: uint256_t.hpp:105
uint256_t & operator=(const uint256_t &x)
Definition: uint256_t.hpp:48
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
uint128_t.hpp contains contains the definition of a 128-bit unsigned integer type.