NicheLibrary
This documentation is automatically generated by NotLeonian/competitive-verifier (forked from competitive-verifier/competitive-verifier)
verify/standalone-int128.test.cpp
- View this file on GitHub
- Last update: 2026-07-11 16:54:42+09:00
Depends on
Code
// competitive-verifier: STANDALONE
#include <cassert>
#include <cstdint>
#include <limits>
#include <sstream>
#include "../internal/int128.hpp"
namespace {
using NicheLibrary::Int128;
using NicheLibrary::UInt128;
struct UInt128DivModResult {
UInt128 quotient;
UInt128 remainder;
};
constexpr UInt128 to_unsigned(Int128 value) {
return UInt128::from_words(value.high(), value.low());
}
constexpr UInt128 abs_unsigned(Int128 value) {
if (!value.is_negative()) {
return to_unsigned(value);
}
return -to_unsigned(value);
}
constexpr bool get_bit(UInt128 value, int index) {
if (index < 64) {
return ((value.low() >> index) & 1) != 0;
}
return ((value.high() >> (index - 64)) & 1) != 0;
}
constexpr UInt128 bit_value(int index) {
if (index < 64) {
return UInt128::from_words(0, std::uint64_t{1} << index);
}
return UInt128::from_words(std::uint64_t{1} << (index - 64), 0);
}
constexpr UInt128 shift_left_one(UInt128 value) {
return UInt128::from_words((value.high() * 2) + (value.low() >> 63),
value.low() * 2);
}
constexpr UInt128DivModResult reference_div_mod(UInt128 lhs, UInt128 rhs) {
assert(rhs != UInt128{});
UInt128 quotient;
UInt128 remainder;
for (int bit = 127; bit >= 0; bit -= 1) {
remainder = shift_left_one(remainder);
if (get_bit(lhs, bit)) {
remainder += UInt128(1);
}
if (remainder >= rhs) {
remainder -= rhs;
quotient += bit_value(bit);
}
}
return {quotient, remainder};
}
void test_unsigned_division(UInt128 lhs, UInt128 rhs) {
if (rhs == UInt128{}) {
return;
}
const UInt128DivModResult expected = reference_div_mod(lhs, rhs);
UInt128 quotient;
UInt128 remainder;
UInt128::div_mod(lhs, rhs, quotient, remainder);
assert(quotient == expected.quotient);
assert(remainder == expected.remainder);
assert(lhs / rhs == expected.quotient);
assert(lhs % rhs == expected.remainder);
assert(quotient * rhs + remainder == lhs);
assert(remainder < rhs);
UInt128 quotient_alias = lhs;
UInt128 remainder_alias;
UInt128::div_mod(quotient_alias, rhs, quotient_alias, remainder_alias);
assert(quotient_alias == expected.quotient);
assert(remainder_alias == expected.remainder);
UInt128 rhs_alias = rhs;
UInt128::div_mod(lhs, rhs_alias, rhs_alias, remainder_alias);
assert(rhs_alias == expected.quotient);
assert(remainder_alias == expected.remainder);
UInt128 lhs_alias = lhs;
UInt128::div_mod(lhs_alias, rhs, quotient_alias, lhs_alias);
assert(quotient_alias == expected.quotient);
assert(lhs_alias == expected.remainder);
}
void test_signed_division(Int128 lhs, Int128 rhs) {
if (rhs == Int128{}) {
return;
}
if (lhs == std::numeric_limits<Int128>::min() && rhs == Int128(-1)) {
return;
}
Int128 quotient;
Int128 remainder;
Int128::div_mod(lhs, rhs, quotient, remainder);
assert(lhs / rhs == quotient);
assert(lhs % rhs == remainder);
assert(quotient * rhs + remainder == lhs);
assert(abs_unsigned(remainder) < abs_unsigned(rhs));
if (remainder != Int128{}) {
assert(remainder.is_negative() == lhs.is_negative());
}
}
constexpr bool test_uint128_div_mod_fast_paths() {
UInt128 quotient;
UInt128 remainder;
UInt128::div_mod(UInt128::from_words(0, ~std::uint64_t{}),
UInt128::from_words(0, (std::uint64_t{1} << 63) + 1),
quotient, remainder);
if (quotient != UInt128(1) ||
remainder != UInt128::from_words(0, (std::uint64_t{1} << 63) - 2)) {
return false;
}
const UInt128 wide =
UInt128::from_words(0x123456789abcdef0ULL, 0xfedcba9876543210ULL);
UInt128::div_mod(wide, UInt128(1), quotient, remainder);
if (quotient != wide || remainder != UInt128{}) {
return false;
}
UInt128::div_mod(UInt128::from_words(1, 0), UInt128(2), quotient,
remainder);
if (quotient != UInt128::from_words(0, std::uint64_t{1} << 63) ||
remainder != UInt128{}) {
return false;
}
const UInt128 smaller = UInt128::from_words(1, ~std::uint64_t{});
const UInt128 larger = UInt128::from_words(2, 0);
UInt128::div_mod(smaller, larger, quotient, remainder);
return quotient == UInt128{} && remainder == smaller;
}
} // namespace
int main() {
using NicheLibrary::Int128;
using NicheLibrary::UInt128;
static_assert(test_uint128_div_mod_fast_paths(),
"UInt128 division fast paths must be constexpr-correct.");
static_assert(std::numeric_limits<UInt128>::is_integer,
"UInt128 must be integer.");
static_assert(!std::numeric_limits<UInt128>::is_signed,
"UInt128 must be unsigned.");
static_assert(std::numeric_limits<UInt128>::digits == 128,
"UInt128 must have 128 value bits.");
static_assert(std::numeric_limits<Int128>::is_integer,
"Int128 must be integer.");
static_assert(std::numeric_limits<Int128>::is_signed,
"Int128 must be signed.");
static_assert(std::numeric_limits<Int128>::digits == 127,
"Int128 must have 127 value bits.");
static_assert(static_cast<long double>(UInt128(123)) == 123.0L,
"UInt128 must convert to long double.");
static_assert(static_cast<long double>(Int128(-123)) == -123.0L,
"Int128 must convert to long double.");
static_assert(static_cast<long double>(UInt128::from_words(1, 0)) ==
0x1p64L,
"wide UInt128 must convert to long double.");
static_assert(static_cast<long double>(
Int128::from_words(~std::uint64_t{}, 0)) == -0x1p64L,
"wide negative Int128 must convert to long double.");
const UInt128 unsigned_values[] = {
UInt128(0),
UInt128(1),
UInt128(2),
UInt128(3),
UInt128::from_words(0, (std::uint64_t{1} << 32) - 1),
UInt128::from_words(0, std::uint64_t{1} << 32),
UInt128::from_words(0, (std::uint64_t{1} << 32) + 1),
UInt128::from_words(0, (std::uint64_t{1} << 63) - 1),
UInt128::from_words(0, std::uint64_t{1} << 63),
UInt128::from_words(0, ~std::uint64_t{}),
UInt128::from_words(1, 0),
UInt128::from_words(1, 1),
UInt128::from_words((std::uint64_t{1} << 32) - 1, ~std::uint64_t{}),
UInt128::from_words(std::uint64_t{1} << 32, 0),
UInt128::from_words(std::uint64_t{1} << 63, 0),
UInt128::from_words((std::uint64_t{1} << 63) + 123, 456),
UInt128::from_words(0x123456789abcdef0ULL, 0xfedcba9876543210ULL),
UInt128::from_words(0xfedcba9876543210ULL, 0x123456789abcdef0ULL),
UInt128::from_words(~std::uint64_t{}, ~std::uint64_t{}),
};
for (const UInt128 lhs : unsigned_values) {
for (const UInt128 rhs : unsigned_values) {
test_unsigned_division(lhs, rhs);
}
}
const Int128 signed_values[] = {
Int128(0),
Int128(1),
Int128(-1),
Int128(2),
Int128(-2),
Int128(3),
Int128(-3),
Int128::from_words(0, std::uint64_t{1} << 63),
Int128::from_words(~std::uint64_t{}, std::uint64_t{1} << 63),
Int128::from_words(0x123456789abcdef0ULL, 0xfedcba9876543210ULL),
Int128::from_words(0xfedcba9876543210ULL, 0x123456789abcdef0ULL),
std::numeric_limits<Int128>::max(),
std::numeric_limits<Int128>::min(),
};
for (const Int128 lhs : signed_values) {
for (const Int128 rhs : signed_values) {
test_signed_division(lhs, rhs);
}
}
{
std::stringstream stream;
stream << UInt128::from_words(~std::uint64_t{}, ~std::uint64_t{});
assert(stream.str() == "340282366920938463463374607431768211455");
}
{
std::stringstream stream;
stream << Int128::from_words(std::uint64_t{1} << 63, 0);
assert(stream.str() == "-170141183460469231731687303715884105728");
}
{
std::stringstream stream("170141183460469231731687303715884105727");
Int128 value;
stream >> value;
assert(value == std::numeric_limits<Int128>::max());
}
{
std::stringstream stream("340282366920938463463374607431768211455");
UInt128 value;
stream >> value;
assert(value == std::numeric_limits<UInt128>::max());
}
return 0;
}
#line 1 "verify/standalone-int128.test.cpp"
// competitive-verifier: STANDALONE
#include <cassert>
#include <cstdint>
#include <limits>
#include <sstream>
#line 1 "internal/int128.hpp"
// 128 bit 符号なし整数型 UInt128 と 128 bit 符号付き整数型 Int128 を提供する。
// GCC 拡張には依存しない。
#include <bit>
#line 10 "internal/int128.hpp"
#include <istream>
#line 12 "internal/int128.hpp"
#include <ostream>
#include <string>
#include <type_traits>
namespace NicheLibrary {
class UInt128 {
public:
constexpr UInt128() = default;
template <
class T,
std::enable_if_t<std::is_integral_v<T> && std::is_signed_v<T>, int> = 0>
constexpr UInt128(T value)
: high_(value < 0 ? ~std::uint64_t{} : std::uint64_t{}),
low_(static_cast<std::uint64_t>(value)) {}
template <class T,
std::enable_if_t<std::is_integral_v<T> && !std::is_signed_v<T>,
int> = 0>
constexpr UInt128(T value)
: high_(0), low_(static_cast<std::uint64_t>(value)) {}
static constexpr UInt128 from_words(std::uint64_t high, std::uint64_t low) {
UInt128 value;
value.high_ = high;
value.low_ = low;
return value;
}
constexpr std::uint64_t high() const { return high_; }
constexpr std::uint64_t low() const { return low_; }
template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
explicit constexpr operator T() const {
return static_cast<T>(low_);
}
explicit constexpr operator bool() const { return high_ != 0 || low_ != 0; }
explicit constexpr operator long double() const {
if (high_ == 0) {
return static_cast<long double>(low_);
}
return static_cast<long double>(high_) * 0x1p64L +
static_cast<long double>(low_);
}
friend constexpr bool operator==(UInt128 lhs, UInt128 rhs) {
return lhs.high_ == rhs.high_ && lhs.low_ == rhs.low_;
}
friend constexpr bool operator!=(UInt128 lhs, UInt128 rhs) {
return !(lhs == rhs);
}
friend constexpr bool operator<(UInt128 lhs, UInt128 rhs) {
if (lhs.high_ != rhs.high_) {
return lhs.high_ < rhs.high_;
}
return lhs.low_ < rhs.low_;
}
friend constexpr bool operator>(UInt128 lhs, UInt128 rhs) {
return rhs < lhs;
}
friend constexpr bool operator<=(UInt128 lhs, UInt128 rhs) {
return !(rhs < lhs);
}
friend constexpr bool operator>=(UInt128 lhs, UInt128 rhs) {
return !(lhs < rhs);
}
constexpr UInt128 operator+() const { return *this; }
constexpr UInt128 operator-() const { return UInt128{} - *this; }
constexpr UInt128 &operator+=(UInt128 rhs) {
const std::uint64_t old_low = low_;
low_ += rhs.low_;
high_ += rhs.high_ + (low_ < old_low ? 1 : 0);
return *this;
}
constexpr UInt128 &operator-=(UInt128 rhs) {
const std::uint64_t old_low = low_;
low_ -= rhs.low_;
high_ -= rhs.high_ + (old_low < rhs.low_ ? 1 : 0);
return *this;
}
constexpr UInt128 &operator*=(UInt128 rhs) {
*this = *this * rhs;
return *this;
}
constexpr UInt128 &operator/=(UInt128 rhs) {
*this = *this / rhs;
return *this;
}
constexpr UInt128 &operator%=(UInt128 rhs) {
*this = *this % rhs;
return *this;
}
friend constexpr UInt128 operator+(UInt128 lhs, UInt128 rhs) {
lhs += rhs;
return lhs;
}
friend constexpr UInt128 operator-(UInt128 lhs, UInt128 rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr UInt128 operator*(UInt128 lhs, UInt128 rhs) {
const UInt128 p00 = multiply_u64(lhs.low_, rhs.low_);
return from_words(
p00.high_ + lhs.low_ * rhs.high_ + lhs.high_ * rhs.low_, p00.low_);
}
static constexpr void div_mod(UInt128 lhs, UInt128 rhs, UInt128 "ient,
UInt128 &remainder) {
assert(rhs != UInt128{});
div_mod_unchecked(lhs, rhs, quotient, remainder);
}
friend constexpr UInt128 operator/(UInt128 lhs, UInt128 rhs) {
UInt128 quotient;
UInt128 remainder;
div_mod(lhs, rhs, quotient, remainder);
return quotient;
}
friend constexpr UInt128 operator%(UInt128 lhs, UInt128 rhs) {
UInt128 quotient;
UInt128 remainder;
div_mod(lhs, rhs, quotient, remainder);
return remainder;
}
private:
friend class Int128;
static constexpr std::uint64_t word_base() {
return std::uint64_t{1} << 32;
}
static constexpr std::uint64_t word_mask() { return word_base() - 1; }
static constexpr void to_words(UInt128 value, std::uint32_t words[4]) {
words[0] = static_cast<std::uint32_t>(value.low_ & word_mask());
words[1] = static_cast<std::uint32_t>(value.low_ >> 32);
words[2] = static_cast<std::uint32_t>(value.high_ & word_mask());
words[3] = static_cast<std::uint32_t>(value.high_ >> 32);
}
static constexpr UInt128 from_32bit_words(const std::uint32_t words[4]) {
return UInt128::from_words(
(static_cast<std::uint64_t>(words[3]) << 32) | words[2],
(static_cast<std::uint64_t>(words[1]) << 32) | words[0]);
}
static constexpr int word_length(const std::uint32_t words[4]) {
int length = 4;
while (length > 0 && words[length - 1] == 0) {
--length;
}
return length;
}
// divisor ≠ 0 が呼び出し元で保証されていることを仮定する。
static constexpr UInt128 div_mod_uint32(UInt128 value,
std::uint32_t divisor,
std::uint32_t &remainder) {
const std::uint32_t words[4] = {
static_cast<std::uint32_t>(value.low_ & word_mask()),
static_cast<std::uint32_t>(value.low_ >> 32),
static_cast<std::uint32_t>(value.high_ & word_mask()),
static_cast<std::uint32_t>(value.high_ >> 32),
};
std::uint32_t quotient_words[4] = {};
std::uint64_t rem = 0;
for (int i = 3; i >= 0; --i) {
const std::uint64_t current = (rem << 32) | words[i];
quotient_words[i] = static_cast<std::uint32_t>(current / divisor);
rem = current % divisor;
}
remainder = static_cast<std::uint32_t>(rem);
return from_32bit_words(quotient_words);
}
static constexpr void shift_left_words(const std::uint32_t source[4],
int source_length, int shift,
std::uint32_t result[5]) {
std::uint64_t carry = 0;
for (int i = 0; i < source_length; ++i) {
const std::uint64_t current =
(static_cast<std::uint64_t>(source[i]) << shift) | carry;
result[i] = static_cast<std::uint32_t>(current & word_mask());
carry = current >> 32;
}
result[source_length] = static_cast<std::uint32_t>(carry);
}
static constexpr void shift_right_words(const std::uint32_t source[5],
int source_length, int shift,
std::uint32_t result[4]) {
if (shift == 0) {
for (int i = 0; i < source_length; ++i) {
result[i] = source[i];
}
return;
}
for (int i = 0; i < source_length; ++i) {
const std::uint32_t next = i + 1 < 5 ? source[i + 1] : 0;
result[i] = static_cast<std::uint32_t>(
(source[i] >> shift) |
(static_cast<std::uint64_t>(next) << (32 - shift)));
}
}
static constexpr bool subtract_product(std::uint32_t words[5], int offset,
const std::uint32_t divisor[5],
int divisor_length,
std::uint32_t multiplier) {
std::uint64_t borrow = 0;
std::uint64_t carry = 0;
for (int i = 0; i < divisor_length; ++i) {
const std::uint64_t product =
static_cast<std::uint64_t>(multiplier) * divisor[i] + carry;
carry = product >> 32;
const std::uint64_t subtrahend = (product & word_mask()) + borrow;
if (static_cast<std::uint64_t>(words[offset + i]) >= subtrahend) {
words[offset + i] = static_cast<std::uint32_t>(
static_cast<std::uint64_t>(words[offset + i]) - subtrahend);
borrow = 0;
} else {
words[offset + i] = static_cast<std::uint32_t>(
word_base() + words[offset + i] - subtrahend);
borrow = 1;
}
}
const std::uint64_t subtrahend = carry + borrow;
if (static_cast<std::uint64_t>(words[offset + divisor_length]) >=
subtrahend) {
words[offset + divisor_length] = static_cast<std::uint32_t>(
static_cast<std::uint64_t>(words[offset + divisor_length]) -
subtrahend);
return false;
}
words[offset + divisor_length] = static_cast<std::uint32_t>(
word_base() + words[offset + divisor_length] - subtrahend);
return true;
}
static constexpr void add_back(std::uint32_t words[5], int offset,
const std::uint32_t divisor[5],
int divisor_length) {
std::uint64_t carry = 0;
for (int i = 0; i < divisor_length; ++i) {
const std::uint64_t sum =
static_cast<std::uint64_t>(words[offset + i]) + divisor[i] +
carry;
words[offset + i] = static_cast<std::uint32_t>(sum & word_mask());
carry = sum >> 32;
}
words[offset + divisor_length] = static_cast<std::uint32_t>(
static_cast<std::uint64_t>(words[offset + divisor_length]) + carry);
}
static constexpr void div_mod_knuth(const std::uint32_t lhs_words[4],
int lhs_length,
const std::uint32_t rhs_words[4],
int rhs_length,
std::uint32_t quotient_words[4],
std::uint32_t remainder_words[4]) {
const int shift = std::countl_zero(rhs_words[rhs_length - 1]);
std::uint32_t normalized_lhs[5] = {};
std::uint32_t normalized_rhs[5] = {};
shift_left_words(lhs_words, lhs_length, shift, normalized_lhs);
shift_left_words(rhs_words, rhs_length, shift, normalized_rhs);
const int quotient_length = lhs_length - rhs_length + 1;
for (int j = quotient_length - 1; j >= 0; --j) {
const std::uint64_t numerator =
(static_cast<std::uint64_t>(normalized_lhs[j + rhs_length])
<< 32) |
normalized_lhs[j + rhs_length - 1];
std::uint64_t estimate = numerator / normalized_rhs[rhs_length - 1];
std::uint64_t estimate_remainder =
numerator % normalized_rhs[rhs_length - 1];
while (estimate == word_base() ||
estimate * normalized_rhs[rhs_length - 2] >
word_base() * estimate_remainder +
normalized_lhs[j + rhs_length - 2]) {
--estimate;
estimate_remainder += normalized_rhs[rhs_length - 1];
if (estimate_remainder >= word_base()) {
break;
}
}
quotient_words[j] = static_cast<std::uint32_t>(estimate);
if (subtract_product(normalized_lhs, j, normalized_rhs, rhs_length,
quotient_words[j])) {
--quotient_words[j];
add_back(normalized_lhs, j, normalized_rhs, rhs_length);
}
}
std::uint32_t shifted_remainder[4] = {};
shift_right_words(normalized_lhs, rhs_length, shift, shifted_remainder);
for (int i = 0; i < rhs_length; ++i) {
remainder_words[i] = shifted_remainder[i];
}
}
// 呼び出し元で lhs >= rhs > 0 が保証されていることを仮定する。
static constexpr void div_mod_32bit_words(UInt128 lhs, UInt128 rhs,
UInt128 "ient,
UInt128 &remainder) {
std::uint32_t lhs_words[4] = {};
std::uint32_t rhs_words[4] = {};
to_words(lhs, lhs_words);
to_words(rhs, rhs_words);
const int lhs_length = word_length(lhs_words);
const int rhs_length = word_length(rhs_words);
if (rhs_length == 1) {
std::uint32_t rem = 0;
quotient = div_mod_uint32(lhs, rhs_words[0], rem);
remainder = UInt128(rem);
return;
}
std::uint32_t quotient_words[4] = {};
std::uint32_t remainder_words[4] = {};
div_mod_knuth(lhs_words, lhs_length, rhs_words, rhs_length,
quotient_words, remainder_words);
quotient = from_32bit_words(quotient_words);
remainder = from_32bit_words(remainder_words);
}
// rhs ≠ 0 が呼び出し元で保証されていることを仮定する。
static constexpr void div_mod_unchecked(UInt128 lhs, UInt128 rhs,
UInt128 "ient,
UInt128 &remainder) {
UInt128 q, r;
if (rhs.high_ == 0) {
if (lhs.high_ == 0) {
q = UInt128(lhs.low_ / rhs.low_);
r = UInt128(lhs.low_ % rhs.low_);
} else if (rhs.low_ == 1) {
q = lhs;
r = UInt128{};
} else if (rhs.low_ <= std::numeric_limits<std::uint32_t>::max()) {
std::uint32_t rem = 0;
q = div_mod_uint32(lhs, static_cast<std::uint32_t>(rhs.low_),
rem);
r = UInt128(rem);
} else {
div_mod_32bit_words(lhs, rhs, q, r);
}
} else if (lhs < rhs) {
q = UInt128{};
r = lhs;
} else {
div_mod_32bit_words(lhs, rhs, q, r);
}
quotient = q;
remainder = r;
}
static constexpr UInt128 multiply_u64(std::uint64_t lhs,
std::uint64_t rhs) {
constexpr std::uint64_t mask = (std::uint64_t{1} << 32) - 1;
const std::uint64_t lhs_low = lhs & mask;
const std::uint64_t lhs_high = lhs >> 32;
const std::uint64_t rhs_low = rhs & mask;
const std::uint64_t rhs_high = rhs >> 32;
const std::uint64_t p00 = lhs_low * rhs_low;
const std::uint64_t p01 = lhs_low * rhs_high;
const std::uint64_t p10 = lhs_high * rhs_low;
const std::uint64_t p11 = lhs_high * rhs_high;
const std::uint64_t middle = (p00 >> 32) + (p01 & mask) + (p10 & mask);
return from_words(p11 + (p01 >> 32) + (p10 >> 32) + (middle >> 32),
(middle << 32) | (p00 & mask));
}
std::uint64_t high_ = 0;
std::uint64_t low_ = 0;
};
class Int128 {
public:
constexpr Int128() = default;
template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
constexpr Int128(T value) : value_(value) {}
static constexpr Int128 from_words(std::uint64_t high, std::uint64_t low) {
Int128 value;
value.value_ = UInt128::from_words(high, low);
return value;
}
constexpr std::uint64_t high() const { return value_.high(); }
constexpr std::uint64_t low() const { return value_.low(); }
template <class T, std::enable_if_t<std::is_integral_v<T>, int> = 0>
explicit constexpr operator T() const {
return static_cast<T>(value_.low());
}
explicit constexpr operator bool() const { return value_ != UInt128{}; }
constexpr bool is_negative() const { return (value_.high() >> 63) != 0; }
explicit constexpr operator long double() const {
const bool negative = is_negative();
const long double magnitude =
static_cast<long double>(negative ? -value_ : value_);
return negative ? -magnitude : magnitude;
}
friend constexpr bool operator==(Int128 lhs, Int128 rhs) {
return lhs.value_ == rhs.value_;
}
friend constexpr bool operator!=(Int128 lhs, Int128 rhs) {
return !(lhs == rhs);
}
friend constexpr bool operator<(Int128 lhs, Int128 rhs) {
const bool lhs_negative = lhs.is_negative();
const bool rhs_negative = rhs.is_negative();
if (lhs_negative != rhs_negative) {
return lhs_negative;
}
return lhs.value_ < rhs.value_;
}
friend constexpr bool operator>(Int128 lhs, Int128 rhs) {
return rhs < lhs;
}
friend constexpr bool operator<=(Int128 lhs, Int128 rhs) {
return !(rhs < lhs);
}
friend constexpr bool operator>=(Int128 lhs, Int128 rhs) {
return !(lhs < rhs);
}
constexpr Int128 operator+() const { return *this; }
constexpr Int128 operator-() const {
Int128 value;
value.value_ = -value_;
return value;
}
constexpr Int128 &operator+=(Int128 rhs) {
value_ += rhs.value_;
return *this;
}
constexpr Int128 &operator-=(Int128 rhs) {
value_ -= rhs.value_;
return *this;
}
constexpr Int128 &operator*=(Int128 rhs) {
value_ *= rhs.value_;
return *this;
}
constexpr Int128 &operator/=(Int128 rhs) {
*this = *this / rhs;
return *this;
}
constexpr Int128 &operator%=(Int128 rhs) {
*this = *this % rhs;
return *this;
}
friend constexpr Int128 operator+(Int128 lhs, Int128 rhs) {
lhs += rhs;
return lhs;
}
friend constexpr Int128 operator-(Int128 lhs, Int128 rhs) {
lhs -= rhs;
return lhs;
}
friend constexpr Int128 operator*(Int128 lhs, Int128 rhs) {
lhs *= rhs;
return lhs;
}
static constexpr void div_mod(Int128 lhs, Int128 rhs, Int128 "ient,
Int128 &remainder) {
assert(rhs != Int128{});
assert(!(lhs == min_value() && rhs == Int128(-1)));
const bool lhs_negative = lhs.is_negative();
const bool rhs_negative = rhs.is_negative();
const bool quotient_negative = lhs_negative != rhs_negative;
UInt128 quotient_abs;
UInt128 remainder_abs;
UInt128::div_mod_unchecked(abs_unsigned(lhs), abs_unsigned(rhs),
quotient_abs, remainder_abs);
const Int128 q =
from_unsigned_unchecked(quotient_abs, quotient_negative);
const Int128 r = from_unsigned_unchecked(remainder_abs, lhs_negative);
quotient = q;
remainder = r;
}
friend constexpr Int128 operator/(Int128 lhs, Int128 rhs) {
Int128 quotient;
Int128 remainder;
div_mod(lhs, rhs, quotient, remainder);
return quotient;
}
friend constexpr Int128 operator%(Int128 lhs, Int128 rhs) {
Int128 quotient;
Int128 remainder;
div_mod(lhs, rhs, quotient, remainder);
return remainder;
}
private:
static constexpr Int128 from_twos_complement(UInt128 value) {
Int128 result;
result.value_ = value;
return result;
}
static constexpr Int128 min_value() {
return from_words(std::uint64_t{1} << 63, 0);
}
static constexpr UInt128 abs_unsigned(Int128 value) {
if (!value.is_negative()) {
return value.value_;
}
return -value.value_;
}
static constexpr Int128 from_unsigned(UInt128 value, bool negative) {
if (!negative) {
assert((value.high() >> 63) == 0);
} else {
assert(value <= UInt128::from_words(std::uint64_t{1} << 63, 0));
}
return from_unsigned_unchecked(value, negative);
}
// 引数 negative で指定した通りに符号を付けた value が
// Int128 の範囲に収まることを仮定する。
static constexpr Int128 from_unsigned_unchecked(UInt128 value,
bool negative) {
return from_twos_complement(negative ? -value : value);
}
friend std::istream &operator>>(std::istream &input, Int128 &value);
friend std::ostream &operator<<(std::ostream &output, Int128 value);
UInt128 value_;
};
namespace int128_internal {
// first < text.size() が呼び出し元で保証されていることを仮定する。
inline UInt128 read_uint128_decimal(const std::string &text,
std::size_t first) {
UInt128 value = 0;
std::size_t i = first;
const std::size_t first_len = (text.size() - first) % 9;
if (first_len != 0) {
std::uint32_t chunk = 0;
for (std::size_t j = 0; j < first_len; ++j) {
assert('0' <= text[i] && text[i] <= '9');
chunk = chunk * 10 + static_cast<std::uint32_t>(text[i] - '0');
++i;
}
value = UInt128(chunk);
}
while (i < text.size()) {
std::uint32_t chunk = 0;
for (int j = 0; j < 9; ++j) {
assert('0' <= text[i] && text[i] <= '9');
chunk = chunk * 10 + static_cast<std::uint32_t>(text[i] - '0');
++i;
}
value *= UInt128(1000000000);
value += UInt128(chunk);
}
return value;
}
inline void write_padded_9(std::ostream &output, std::uint32_t value) {
char buffer[9];
for (int i = 8; i >= 0; --i) {
buffer[i] = static_cast<char>('0' + value % 10);
value /= 10;
}
output.write(buffer, 9);
}
inline void write_uint128_decimal(std::ostream &output, UInt128 value) {
if (value == UInt128(0)) {
output << '0';
return;
}
constexpr std::uint32_t base = 1000000000;
std::uint32_t parts[5] = {};
int size = 0;
while (value != UInt128(0)) {
UInt128 quotient;
UInt128 remainder;
UInt128::div_mod(value, UInt128(base), quotient, remainder);
parts[size] = static_cast<std::uint32_t>(remainder);
value = quotient;
++size;
}
output << parts[size - 1];
for (int i = size - 2; i >= 0; --i) {
write_padded_9(output, parts[i]);
}
}
} // namespace int128_internal
inline std::istream &operator>>(std::istream &input, UInt128 &value) {
std::string text;
input >> text;
if (!input) {
return input;
}
std::size_t first = 0;
if (text[first] == '+') {
++first;
}
assert(first < text.size());
assert(text[first] != '-');
value = int128_internal::read_uint128_decimal(text, first);
return input;
}
inline std::ostream &operator<<(std::ostream &output, UInt128 value) {
int128_internal::write_uint128_decimal(output, value);
return output;
}
inline std::istream &operator>>(std::istream &input, Int128 &value) {
std::string text;
input >> text;
if (!input) {
return input;
}
std::size_t first = 0;
bool negative = false;
if (text[first] == '+' || text[first] == '-') {
negative = text[first] == '-';
++first;
}
assert(first < text.size());
const UInt128 magnitude =
int128_internal::read_uint128_decimal(text, first);
value = Int128::from_unsigned(magnitude, negative);
return input;
}
inline std::ostream &operator<<(std::ostream &output, Int128 value) {
if (value.is_negative()) {
output << '-';
int128_internal::write_uint128_decimal(output,
Int128::abs_unsigned(value));
} else {
int128_internal::write_uint128_decimal(
output, UInt128::from_words(value.high(), value.low()));
}
return output;
}
} // namespace NicheLibrary
namespace std {
template <> class numeric_limits<NicheLibrary::UInt128> {
public:
static constexpr bool is_specialized = true;
static constexpr NicheLibrary::UInt128 min() noexcept { return 0; }
static constexpr NicheLibrary::UInt128 max() noexcept {
return NicheLibrary::UInt128::from_words(~std::uint64_t{},
~std::uint64_t{});
}
static constexpr NicheLibrary::UInt128 lowest() noexcept { return 0; }
static constexpr int digits = 128;
static constexpr int digits10 = 38;
static constexpr int max_digits10 = 0;
static constexpr bool is_signed = false;
static constexpr bool is_integer = true;
static constexpr bool is_exact = true;
static constexpr int radix = 2;
static constexpr NicheLibrary::UInt128 epsilon() noexcept { return 0; }
static constexpr NicheLibrary::UInt128 round_error() noexcept { return 0; }
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 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 NicheLibrary::UInt128 infinity() noexcept { return 0; }
static constexpr NicheLibrary::UInt128 quiet_NaN() noexcept { return 0; }
static constexpr NicheLibrary::UInt128 signaling_NaN() noexcept {
return 0;
}
static constexpr NicheLibrary::UInt128 denorm_min() noexcept { return 0; }
static constexpr bool is_iec559 = false;
static constexpr bool is_bounded = true;
static constexpr bool is_modulo = true;
static constexpr bool traps = false;
static constexpr bool tinyness_before = false;
static constexpr float_round_style round_style = round_toward_zero;
};
template <> class numeric_limits<NicheLibrary::Int128> {
public:
static constexpr bool is_specialized = true;
static constexpr NicheLibrary::Int128 min() noexcept {
return NicheLibrary::Int128::from_words(std::uint64_t{1} << 63, 0);
}
static constexpr NicheLibrary::Int128 max() noexcept {
return NicheLibrary::Int128::from_words((std::uint64_t{1} << 63) - 1,
~std::uint64_t{});
}
static constexpr NicheLibrary::Int128 lowest() noexcept { return min(); }
static constexpr int digits = 127;
static constexpr int digits10 = 38;
static constexpr int max_digits10 = 0;
static constexpr bool is_signed = true;
static constexpr bool is_integer = true;
static constexpr bool is_exact = true;
static constexpr int radix = 2;
static constexpr NicheLibrary::Int128 epsilon() noexcept { return 0; }
static constexpr NicheLibrary::Int128 round_error() noexcept { return 0; }
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 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 NicheLibrary::Int128 infinity() noexcept { return 0; }
static constexpr NicheLibrary::Int128 quiet_NaN() noexcept { return 0; }
static constexpr NicheLibrary::Int128 signaling_NaN() noexcept { return 0; }
static constexpr NicheLibrary::Int128 denorm_min() noexcept { return 0; }
static constexpr bool is_iec559 = false;
static constexpr bool is_bounded = true;
static constexpr bool is_modulo = false;
static constexpr bool traps = false;
static constexpr bool tinyness_before = false;
static constexpr float_round_style round_style = round_toward_zero;
};
} // namespace std
#line 9 "verify/standalone-int128.test.cpp"
namespace {
using NicheLibrary::Int128;
using NicheLibrary::UInt128;
struct UInt128DivModResult {
UInt128 quotient;
UInt128 remainder;
};
constexpr UInt128 to_unsigned(Int128 value) {
return UInt128::from_words(value.high(), value.low());
}
constexpr UInt128 abs_unsigned(Int128 value) {
if (!value.is_negative()) {
return to_unsigned(value);
}
return -to_unsigned(value);
}
constexpr bool get_bit(UInt128 value, int index) {
if (index < 64) {
return ((value.low() >> index) & 1) != 0;
}
return ((value.high() >> (index - 64)) & 1) != 0;
}
constexpr UInt128 bit_value(int index) {
if (index < 64) {
return UInt128::from_words(0, std::uint64_t{1} << index);
}
return UInt128::from_words(std::uint64_t{1} << (index - 64), 0);
}
constexpr UInt128 shift_left_one(UInt128 value) {
return UInt128::from_words((value.high() * 2) + (value.low() >> 63),
value.low() * 2);
}
constexpr UInt128DivModResult reference_div_mod(UInt128 lhs, UInt128 rhs) {
assert(rhs != UInt128{});
UInt128 quotient;
UInt128 remainder;
for (int bit = 127; bit >= 0; bit -= 1) {
remainder = shift_left_one(remainder);
if (get_bit(lhs, bit)) {
remainder += UInt128(1);
}
if (remainder >= rhs) {
remainder -= rhs;
quotient += bit_value(bit);
}
}
return {quotient, remainder};
}
void test_unsigned_division(UInt128 lhs, UInt128 rhs) {
if (rhs == UInt128{}) {
return;
}
const UInt128DivModResult expected = reference_div_mod(lhs, rhs);
UInt128 quotient;
UInt128 remainder;
UInt128::div_mod(lhs, rhs, quotient, remainder);
assert(quotient == expected.quotient);
assert(remainder == expected.remainder);
assert(lhs / rhs == expected.quotient);
assert(lhs % rhs == expected.remainder);
assert(quotient * rhs + remainder == lhs);
assert(remainder < rhs);
UInt128 quotient_alias = lhs;
UInt128 remainder_alias;
UInt128::div_mod(quotient_alias, rhs, quotient_alias, remainder_alias);
assert(quotient_alias == expected.quotient);
assert(remainder_alias == expected.remainder);
UInt128 rhs_alias = rhs;
UInt128::div_mod(lhs, rhs_alias, rhs_alias, remainder_alias);
assert(rhs_alias == expected.quotient);
assert(remainder_alias == expected.remainder);
UInt128 lhs_alias = lhs;
UInt128::div_mod(lhs_alias, rhs, quotient_alias, lhs_alias);
assert(quotient_alias == expected.quotient);
assert(lhs_alias == expected.remainder);
}
void test_signed_division(Int128 lhs, Int128 rhs) {
if (rhs == Int128{}) {
return;
}
if (lhs == std::numeric_limits<Int128>::min() && rhs == Int128(-1)) {
return;
}
Int128 quotient;
Int128 remainder;
Int128::div_mod(lhs, rhs, quotient, remainder);
assert(lhs / rhs == quotient);
assert(lhs % rhs == remainder);
assert(quotient * rhs + remainder == lhs);
assert(abs_unsigned(remainder) < abs_unsigned(rhs));
if (remainder != Int128{}) {
assert(remainder.is_negative() == lhs.is_negative());
}
}
constexpr bool test_uint128_div_mod_fast_paths() {
UInt128 quotient;
UInt128 remainder;
UInt128::div_mod(UInt128::from_words(0, ~std::uint64_t{}),
UInt128::from_words(0, (std::uint64_t{1} << 63) + 1),
quotient, remainder);
if (quotient != UInt128(1) ||
remainder != UInt128::from_words(0, (std::uint64_t{1} << 63) - 2)) {
return false;
}
const UInt128 wide =
UInt128::from_words(0x123456789abcdef0ULL, 0xfedcba9876543210ULL);
UInt128::div_mod(wide, UInt128(1), quotient, remainder);
if (quotient != wide || remainder != UInt128{}) {
return false;
}
UInt128::div_mod(UInt128::from_words(1, 0), UInt128(2), quotient,
remainder);
if (quotient != UInt128::from_words(0, std::uint64_t{1} << 63) ||
remainder != UInt128{}) {
return false;
}
const UInt128 smaller = UInt128::from_words(1, ~std::uint64_t{});
const UInt128 larger = UInt128::from_words(2, 0);
UInt128::div_mod(smaller, larger, quotient, remainder);
return quotient == UInt128{} && remainder == smaller;
}
} // namespace
int main() {
using NicheLibrary::Int128;
using NicheLibrary::UInt128;
static_assert(test_uint128_div_mod_fast_paths(),
"UInt128 division fast paths must be constexpr-correct.");
static_assert(std::numeric_limits<UInt128>::is_integer,
"UInt128 must be integer.");
static_assert(!std::numeric_limits<UInt128>::is_signed,
"UInt128 must be unsigned.");
static_assert(std::numeric_limits<UInt128>::digits == 128,
"UInt128 must have 128 value bits.");
static_assert(std::numeric_limits<Int128>::is_integer,
"Int128 must be integer.");
static_assert(std::numeric_limits<Int128>::is_signed,
"Int128 must be signed.");
static_assert(std::numeric_limits<Int128>::digits == 127,
"Int128 must have 127 value bits.");
static_assert(static_cast<long double>(UInt128(123)) == 123.0L,
"UInt128 must convert to long double.");
static_assert(static_cast<long double>(Int128(-123)) == -123.0L,
"Int128 must convert to long double.");
static_assert(static_cast<long double>(UInt128::from_words(1, 0)) ==
0x1p64L,
"wide UInt128 must convert to long double.");
static_assert(static_cast<long double>(
Int128::from_words(~std::uint64_t{}, 0)) == -0x1p64L,
"wide negative Int128 must convert to long double.");
const UInt128 unsigned_values[] = {
UInt128(0),
UInt128(1),
UInt128(2),
UInt128(3),
UInt128::from_words(0, (std::uint64_t{1} << 32) - 1),
UInt128::from_words(0, std::uint64_t{1} << 32),
UInt128::from_words(0, (std::uint64_t{1} << 32) + 1),
UInt128::from_words(0, (std::uint64_t{1} << 63) - 1),
UInt128::from_words(0, std::uint64_t{1} << 63),
UInt128::from_words(0, ~std::uint64_t{}),
UInt128::from_words(1, 0),
UInt128::from_words(1, 1),
UInt128::from_words((std::uint64_t{1} << 32) - 1, ~std::uint64_t{}),
UInt128::from_words(std::uint64_t{1} << 32, 0),
UInt128::from_words(std::uint64_t{1} << 63, 0),
UInt128::from_words((std::uint64_t{1} << 63) + 123, 456),
UInt128::from_words(0x123456789abcdef0ULL, 0xfedcba9876543210ULL),
UInt128::from_words(0xfedcba9876543210ULL, 0x123456789abcdef0ULL),
UInt128::from_words(~std::uint64_t{}, ~std::uint64_t{}),
};
for (const UInt128 lhs : unsigned_values) {
for (const UInt128 rhs : unsigned_values) {
test_unsigned_division(lhs, rhs);
}
}
const Int128 signed_values[] = {
Int128(0),
Int128(1),
Int128(-1),
Int128(2),
Int128(-2),
Int128(3),
Int128(-3),
Int128::from_words(0, std::uint64_t{1} << 63),
Int128::from_words(~std::uint64_t{}, std::uint64_t{1} << 63),
Int128::from_words(0x123456789abcdef0ULL, 0xfedcba9876543210ULL),
Int128::from_words(0xfedcba9876543210ULL, 0x123456789abcdef0ULL),
std::numeric_limits<Int128>::max(),
std::numeric_limits<Int128>::min(),
};
for (const Int128 lhs : signed_values) {
for (const Int128 rhs : signed_values) {
test_signed_division(lhs, rhs);
}
}
{
std::stringstream stream;
stream << UInt128::from_words(~std::uint64_t{}, ~std::uint64_t{});
assert(stream.str() == "340282366920938463463374607431768211455");
}
{
std::stringstream stream;
stream << Int128::from_words(std::uint64_t{1} << 63, 0);
assert(stream.str() == "-170141183460469231731687303715884105728");
}
{
std::stringstream stream("170141183460469231731687303715884105727");
Int128 value;
stream >> value;
assert(value == std::numeric_limits<Int128>::max());
}
{
std::stringstream stream("340282366920938463463374607431768211455");
UInt128 value;
stream >> value;
assert(value == std::numeric_limits<UInt128>::max());
}
return 0;
}