-
Notifications
You must be signed in to change notification settings - Fork 34
/
WideInteger.h
197 lines (174 loc) · 6.37 KB
/
WideInteger.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
///
/// ref: https://github.com/abseil/abseil-cpp/blob/master/absl/numeric/int128.h
///
#pragma once
#include <functional>
#include <limits>
#include <iosfwd>
#include <type_traits>
#include <stdint.h>
#include "Types.h"
#include "Util.h"
#ifndef __SIZEOF_INT128__
#error "Current compiler does not support __int128"
#endif
constexpr long long bitCastToSigned(unsigned long long v) {
// Casting an unsigned integer to a signed integer of the same
// width is implementation defined behavior if the source value would not fit
// in the destination type. We step around it with a roundtrip bitwise not
// operation to make sure this function remains constexpr. Clang, GCC, and
// MSVC optimize this to a no-op on x86-64.
return v & (((unsigned long long)1) << 63) ? ~static_cast<long long>(~v) : static_cast<long long>(v);
}
constexpr inline unsigned long long uint128High64(uint128 v) {
return static_cast<unsigned long long>(v >> 64);
}
constexpr inline unsigned long long uint128Low64(uint128 v) {
return static_cast<unsigned long long>(v);
}
constexpr unsigned long long int128Low64(int128 v) {
return static_cast<unsigned long long>(v & ~((unsigned long long)0));
}
constexpr long long int128High64(int128 v) {
// Initially cast to unsigned to prevent a right shift on a negative value.
return bitCastToSigned(static_cast<unsigned long long>(static_cast<uint128>(v) >> 64));
}
std::ostream& operator<<(std::ostream &os, uint128 v);
std::ostream& operator<<(std::ostream &os, int128 v);
/*
-std=c++11 && ((clang < 12) ||(gcc < 10.3))
*/
#if !(!defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_INT128)) && \
( \
(defined(__clang__) && (__clang_major__ < 12)) || \
(!defined(__clang__) && (__GNUC__ < 10 || (__GNUC__ == 10 && __GNUC_MINOR__ < 3))) \
)
// Specialized numeric_limits for uint128 and int128.
namespace std {
template <>
class numeric_limits<uint128> {
public:
static constexpr bool is_specialized = true;
static constexpr bool is_signed = false;
static constexpr bool is_integer = true;
static constexpr bool is_exact = true;
static constexpr bool has_infinity = false;
static constexpr bool has_quiet_NaN = false;
static constexpr bool has_signaling_NaN = false;
static constexpr float_denorm_style has_denorm = denorm_absent;
static constexpr bool has_denorm_loss = false;
static constexpr float_round_style round_style = round_toward_zero;
static constexpr bool is_iec559 = false;
static constexpr bool is_bounded = true;
static constexpr bool is_modulo = true;
static constexpr int digits = 128;
static constexpr int digits10 = 38;
static constexpr int max_digits10 = 0;
static constexpr int radix = 2;
static constexpr int min_exponent = 0;
static constexpr int min_exponent10 = 0;
static constexpr int max_exponent = 0;
static constexpr int max_exponent10 = 0;
static constexpr bool tinyness_before = false;
static constexpr uint128 min() { return 0; }
static constexpr uint128 lowest() { return 0; }
static constexpr uint128 max() { return uint128MaxValue(); }
static constexpr uint128 epsilon() { return 0; }
static constexpr uint128 round_error() { return 0; }
static constexpr uint128 infinity() { return 0; }
static constexpr uint128 quiet_NaN() { return 0; }
static constexpr uint128 signaling_NaN() { return 0; }
static constexpr uint128 denorm_min() { return 0; }
};
template <>
class numeric_limits<int128> {
public:
static constexpr bool is_specialized = true;
static constexpr bool is_signed = true;
static constexpr bool is_integer = true;
static constexpr bool is_exact = true;
static constexpr bool has_infinity = false;
static constexpr bool has_quiet_NaN = false;
static constexpr bool has_signaling_NaN = false;
static constexpr float_denorm_style has_denorm = denorm_absent;
static constexpr bool has_denorm_loss = false;
static constexpr float_round_style round_style = round_toward_zero;
static constexpr bool is_iec559 = false;
static constexpr bool is_bounded = true;
static constexpr bool is_modulo = false;
static constexpr int digits = 127;
static constexpr int digits10 = 38;
static constexpr int max_digits10 = 0;
static constexpr int radix = 2;
static constexpr int min_exponent = 0;
static constexpr int min_exponent10 = 0;
static constexpr int max_exponent = 0;
static constexpr int max_exponent10 = 0;
static constexpr bool tinyness_before = false;
static constexpr int128 min() { return int128MinValue(); }
static constexpr int128 lowest() { return int128MinValue(); }
static constexpr int128 max() { return int128MaxValue(); }
static constexpr int128 epsilon() { return 0; }
static constexpr int128 round_error() { return 0; }
static constexpr int128 infinity() { return 0; }
static constexpr int128 quiet_NaN() { return 0; }
static constexpr int128 signaling_NaN() { return 0; }
static constexpr int128 denorm_min() { return 0; }
};
template <>
struct make_unsigned<int128> {
typedef uint128 type;
};
template <>
struct add_pointer<uint128> {
typedef uint128* type;
};
template <>
struct is_integral<int128> : public true_type {};
template <>
struct is_integral<uint128> : public true_type {};
} // namespace std
#endif
/*
clang && (
(-std=c++11) ||
(-std=gnu++11 && clang < 15)
) ||
gcc && (
(-std=c++11) ||
(gcc < 6)
)
*/
#if (defined(__clang__) && \
( \
(defined(__STRICT_ANSI__)) || \
(!(!defined(__STRICT_ANSI__) && defined(_GLIBCXX_USE_INT128)) && __clang_major__ < 15) \
) \
) || \
(!defined(__clang__) && ( (defined(__STRICT_ANSI__) ) || (__GNUC__ < 6) ) )
namespace std {
// Specialized std::hash for uint128 and int128.
template <>
struct hash<int128> {
size_t operator()(int128 v) const noexcept {
size_t seed = 0;
hashCombine(seed, int128High64(v));
hashCombine(seed, int128Low64(v));
return seed;
}
};
template <>
struct hash<uint128> {
size_t operator()(uint128 v) const noexcept {
size_t seed = 0;
hashCombine(seed, uint128High64(v));
hashCombine(seed, uint128Low64(v));
return seed;
}
};
} // namespace std
#endif
namespace std {
int128 pow(int128 x, size_t y);
int128 trunc(int128 x);
}; // namespace std