34 constexpr uint128_t() noexcept :
low{0},
high{0} {}
37 :
low{
static_cast<std::uint64_t
>(value)},
38 high{value < 0 ? UINT64_MAX : 0} {}
41 :
low{
static_cast<std::uint64_t
>(value)},
high{0} {}
46 :
low{
static_cast<std::uint64_t
>(value)},
47 high{value < 0 ? UINT64_MAX : 0} {}
49 constexpr uint128_t(std::uint64_t high_part, std::uint64_t low_part) noexcept
50 :
low{low_part},
high{high_part} {}
52 constexpr explicit operator std::uint64_t() const noexcept {
55 constexpr explicit operator std::int64_t() const noexcept {
56 return static_cast<std::int64_t
>(this->
low);
59 constexpr explicit operator bool() const noexcept {
60 return this->
low != 0 || this->
high != 0;
63 constexpr auto operator+=(
const uint128_t &other)
noexcept -> uint128_t & {
64 auto old_low = this->
low;
65 this->
low += other.low;
66 this->
high += other.high + (this->
low < old_low ? 1 : 0);
70 constexpr auto operator-=(
const uint128_t &other)
noexcept -> uint128_t & {
71 const auto old_low = this->
low;
72 this->
low -= other.low;
73 this->
high -= other.high + (old_low < other.low ? 1 : 0);
77 constexpr auto operator*=(
const uint128_t &other)
noexcept -> uint128_t & {
78 *
this = *
this * other;
82 constexpr auto operator%=(
const uint128_t &other)
noexcept -> uint128_t & {
83 *
this = *
this % other;
87 friend constexpr auto operator+(uint128_t left,
88 const uint128_t &right)
noexcept
94 friend constexpr auto operator-(uint128_t left,
95 const uint128_t &right)
noexcept
101 friend constexpr auto operator*(
const uint128_t &left,
102 const uint128_t &right)
noexcept
104 std::uint64_t result_high;
105 std::uint64_t result_low;
110 result_low = _umul128(left.low, right.low, &result_high);
114 const std::uint64_t left_low{left.low & 0xFFFFFFFF};
115 const std::uint64_t left_high{left.low >> 32};
116 const std::uint64_t right_low{right.low & 0xFFFFFFFF};
117 const std::uint64_t right_high{right.low >> 32};
118 const std::uint64_t cross_1{left_high * right_low};
119 const std::uint64_t cross_2{left_low * right_high};
120 const std::uint64_t mid{cross_1 + (left_low * right_low >> 32)};
121 const std::uint64_t mid_2{(mid & 0xFFFFFFFF) + cross_2};
122 result_high = left_high * right_high + (mid >> 32) + (mid_2 >> 32);
123 result_low = (mid_2 << 32) | ((left_low * right_low) & 0xFFFFFFFF);
125 result_high += left.low * right.high + left.high * right.low;
126 return {result_high, result_low};
129 friend constexpr auto operator/(
const uint128_t ÷nd,
130 std::uint64_t divisor)
noexcept -> uint128_t {
131 if (dividend.high == 0) {
132 return {0, dividend.low / divisor};
135 auto quotient_high = dividend.high / divisor;
136 auto remainder_high = dividend.high % divisor;
137 std::uint64_t quotient_low;
141 assert(remainder_high < divisor);
146 std::uint64_t remainder;
148 _udiv128(remainder_high, dividend.low, divisor, &remainder);
153 auto current_remainder = remainder_high;
154 for (
int bit = 63; bit >= 0; --bit) {
155 const auto carry = current_remainder >> 63;
157 (current_remainder << 1) | ((dividend.low >> bit) & 1);
158 if (carry || current_remainder >= divisor) {
159 current_remainder -= divisor;
160 quotient_low |=
static_cast<std::uint64_t
>(1) << bit;
164 return {quotient_high, quotient_low};
167 friend constexpr auto operator/(
const uint128_t ÷nd,
168 const uint128_t &divisor)
noexcept
170 assert(divisor.high == 0);
171 return dividend / divisor.low;
174 friend constexpr auto operator%(
const uint128_t ÷nd,
175 std::uint64_t divisor)
noexcept -> uint128_t {
176 if (dividend.high == 0) {
177 return {0, dividend.low % divisor};
180 auto remainder_high = dividend.high % divisor;
181 std::uint64_t remainder;
185 assert(remainder_high < divisor);
190 _udiv128(remainder_high, dividend.low, divisor, &remainder);
194 remainder = remainder_high;
195 for (
int bit = 63; bit >= 0; --bit) {
196 const auto carry = remainder >> 63;
197 remainder = (remainder << 1) | ((dividend.low >> bit) & 1);
198 if (carry || remainder >= divisor) {
199 remainder -= divisor;
203 return {0, remainder};
206 friend constexpr auto operator%(
const uint128_t ÷nd,
207 const uint128_t &divisor)
noexcept
209 assert(divisor.high == 0);
210 return dividend % divisor.low;
213 friend constexpr auto operator<(
const uint128_t &left,
214 const uint128_t &right)
noexcept ->
bool {
215 return left.high < right.high ||
216 (left.high == right.high && left.low < right.low);
219 friend constexpr auto operator>(
const uint128_t &left,
220 const uint128_t &right)
noexcept ->
bool {
224 friend constexpr auto operator<=(
const uint128_t &left,
225 const uint128_t &right)
noexcept ->
bool {
226 return !(right < left);
229 friend constexpr auto operator>=(
const uint128_t &left,
230 const uint128_t &right)
noexcept ->
bool {
231 return !(left < right);
234 friend constexpr auto operator==(
const uint128_t &left,
235 const uint128_t &right)
noexcept ->
bool {
236 return left.high == right.high && left.low == right.low;
239 friend constexpr auto operator!=(
const uint128_t &left,
240 const uint128_t &right)
noexcept ->
bool {
241 return !(left == right);
244 friend constexpr auto operator<<(
const uint128_t &value,
int shift)
noexcept
248 }
else if (shift >= 128) {
250 }
else if (shift >= 64) {
251 return {value.low << (shift - 64), 0};
253 return {(value.high << shift) | (value.low >> (64 - shift)),
258 friend constexpr auto operator>>(
const uint128_t &value,
int shift)
noexcept
262 }
else if (shift >= 128) {
264 }
else if (shift >= 64) {
265 return {0, value.high >> (shift - 64)};
267 return {value.high >> shift,
268 (value.low >> shift) | (value.high << (64 - shift))};
272 friend constexpr auto operator|(
const uint128_t &left,
273 const uint128_t &right)
noexcept
275 return {left.high | right.high, left.low | right.low};
278 constexpr auto operator|=(
const uint128_t &other)
noexcept -> uint128_t & {
279 this->
high |= other.high;
280 this->
low |= other.low;
284 friend constexpr auto operator&(
const uint128_t &left,
285 const uint128_t &right)
noexcept
287 return {left.high & right.high, left.low & right.low};