#include #include #include #include // std::popcount
#include // std::unique_ptr

namespace calx {

    //------------------------------------------------------------------------------
    // 算術演算子
    //------------------------------------------------------------------------------

    Int operator+(const Int& lhs, const Int& rhs) {
        // 特殊状態の処理
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]] {
            return IntSpecialStates::handleAddition(lhs, rhs);
        }

        // ゼロとの加算の最適化
        if (lhs.getSign() == 0) return rhs;
        if (rhs.getSign() == 0) return lhs;

        Int result;
        if (lhs.getSign() == rhs.getSign()) {
            // 同符号: 絶対値を加算 (3引数版でコピー不要)
            IntOps::addAbsolute(lhs, rhs, result);
            result.setSign(lhs.getSign());
        }
        else {
            // 異符号: 絶対値の減算 (lhs, rhs を直接渡す — m_words は絶対値)
            if (IntOps::compareAbsLess(lhs, rhs)) {
                IntOps::subtractAbsolute(rhs, lhs, result);
                result.setSign(rhs.getSign());
            }
            else {
                IntOps::subtractAbsolute(lhs, rhs, result);
                result.setSign(lhs.getSign());
            }
        }

        return result;
    }

    Int operator+(Int&& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]]
            return IntSpecialStates::handleAddition(lhs, rhs);
        if (lhs.getSign() == 0) return rhs;
        if (rhs.getSign() == 0) return std::move(lhs);

        if (lhs.getSign() == rhs.getSign()) {
            IntOps::addAbsolute(lhs, rhs);
            return std::move(lhs);
        } else {
            if (IntOps::compareAbsLess(lhs, rhs)) {
                Int result;
                IntOps::subtractAbsolute(rhs, lhs, result);
                result.setSign(rhs.getSign());
                return result;
            } else {
                IntOps::subtractAbsoluteInPlace(lhs, rhs);
                return std::move(lhs);
            }
        }
    }

    Int operator+(const Int& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]]
            return IntSpecialStates::handleAddition(lhs, rhs);
        if (rhs.getSign() == 0) return lhs;
        if (lhs.getSign() == 0) return std::move(rhs);

        if (lhs.getSign() == rhs.getSign()) {
            IntOps::addAbsolute(rhs, lhs);
            return std::move(rhs);
        } else {
            if (IntOps::compareAbsLess(rhs, lhs)) {
                Int result;
                IntOps::subtractAbsolute(lhs, rhs, result);
                result.setSign(lhs.getSign());
                return result;
            } else {
                IntOps::subtractAbsoluteInPlace(rhs, lhs);
                return std::move(rhs);
            }
        }
    }

    Int operator+(Int&& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]]
            return IntSpecialStates::handleAddition(lhs, rhs);
        if (lhs.getSign() == 0) return std::move(rhs);
        if (rhs.getSign() == 0) return std::move(lhs);

        if (lhs.getSign() == rhs.getSign()) {
            // 大きい方のバッファを再利用 (resize を最小化)
            if (lhs.size() >= rhs.size()) {
                IntOps::addAbsolute(lhs, rhs);
                return std::move(lhs);
            } else {
                IntOps::addAbsolute(rhs, lhs);
                return std::move(rhs);
            }
        } else {
            if (IntOps::compareAbsLess(lhs, rhs)) {
                IntOps::subtractAbsoluteInPlace(rhs, lhs);
                return std::move(rhs);
            } else {
                IntOps::subtractAbsoluteInPlace(lhs, rhs);
                return std::move(lhs);
            }
        }
    }

    Int operator-(const Int& lhs, const Int& rhs) {
        // 特殊状態の処理
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]] {
            return IntSpecialStates::handleSubtraction(lhs, rhs);
        }

        // ゼロとの減算の最適化
        if (lhs.getSign() == 0) {
            Int result = rhs;
            if (result.getSign() != 0) {
                result.setSign(-result.getSign());
            }
            return result;
        }
        if (rhs.getSign() == 0) {
            return lhs;
        }

        // lhs - rhs を直接計算 (rhs コピー + operator+ 経由を回避)
        // rhs の符号を反転した場合の effective sign
        int rhsEffSign = -rhs.getSign();

        Int result;
        if (lhs.getSign() == rhsEffSign) {
            // 同符号: 絶対値を加算
            IntOps::addAbsolute(lhs, rhs, result);
            result.setSign(lhs.getSign());
        }
        else {
            // 異符号: 絶対値の減算
            if (IntOps::compareAbsLess(lhs, rhs)) {
                IntOps::subtractAbsolute(rhs, lhs, result);
                result.setSign(rhsEffSign);
            }
            else {
                IntOps::subtractAbsolute(lhs, rhs, result);
                result.setSign(lhs.getSign());
            }
        }

        return result;
    }

    Int operator-(Int&& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]]
            return IntSpecialStates::handleSubtraction(lhs, rhs);
        if (lhs.getSign() == 0) {
            Int result = rhs;
            if (result.getSign() != 0) result.setSign(-result.getSign());
            return result;
        }
        if (rhs.getSign() == 0) return std::move(lhs);

        int rhsEffSign = -rhs.getSign();
        if (lhs.getSign() == rhsEffSign) {
            // 同符号 (例: 5-(-3)=8): 絶対値を加算
            IntOps::addAbsolute(lhs, rhs);
            return std::move(lhs);
        } else {
            // 異符号 (例: 5-3=2): 絶対値を減算
            if (IntOps::compareAbsLess(lhs, rhs)) {
                Int result;
                IntOps::subtractAbsolute(rhs, lhs, result);
                result.setSign(rhsEffSign);
                return result;
            } else {
                IntOps::subtractAbsoluteInPlace(lhs, rhs);
                return std::move(lhs);
            }
        }
    }

    Int operator-(const Int& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]]
            return IntSpecialStates::handleSubtraction(lhs, rhs);
        if (lhs.getSign() == 0) {
            // -rhs: 符号反転してバッファ再利用
            if (rhs.getSign() != 0) rhs.setSign(-rhs.getSign());
            return std::move(rhs);
        }
        if (rhs.getSign() == 0) return lhs;

        int rhsEffSign = -rhs.getSign();
        if (lhs.getSign() == rhsEffSign) {
            // 同符号: 絶対値を加算、符号は lhs 側
            IntOps::addAbsolute(rhs, lhs);
            rhs.setSign(lhs.getSign());
            return std::move(rhs);
        } else {
            // 異符号: 絶対値を減算
            if (IntOps::compareAbsLess(lhs, rhs)) {
                // |lhs| < |rhs|: rhs バッファを再利用
                IntOps::subtractAbsoluteInPlace(rhs, lhs);
                rhs.setSign(rhsEffSign);
                return std::move(rhs);
            } else {
                Int result;
                IntOps::subtractAbsolute(lhs, rhs, result);
                result.setSign(lhs.getSign());
                return result;
            }
        }
    }

    Int operator-(Int&& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]]
            return IntSpecialStates::handleSubtraction(lhs, rhs);
        if (lhs.getSign() == 0) {
            if (rhs.getSign() != 0) rhs.setSign(-rhs.getSign());
            return std::move(rhs);
        }
        if (rhs.getSign() == 0) return std::move(lhs);

        int rhsEffSign = -rhs.getSign();
        if (lhs.getSign() == rhsEffSign) {
            // 同符号: 絶対値を加算
            if (lhs.size() >= rhs.size()) {
                IntOps::addAbsolute(lhs, rhs);
                return std::move(lhs);
            } else {
                IntOps::addAbsolute(rhs, lhs);
                rhs.setSign(lhs.getSign());
                return std::move(rhs);
            }
        } else {
            // 異符号: 絶対値を減算
            if (IntOps::compareAbsLess(lhs, rhs)) {
                IntOps::subtractAbsoluteInPlace(rhs, lhs);
                rhs.setSign(rhsEffSign);
                return std::move(rhs);
            } else {
                IntOps::subtractAbsoluteInPlace(lhs, rhs);
                return std::move(lhs);
            }
        }
    }

    Int operator*(const Int& lhs, const Int& rhs) {
        // 特殊状態の処理
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]] {
            return IntSpecialStates::handleMultiplication(lhs, rhs);
        }

        // ゼロとの乗算
        if (lhs.getSign() == 0 || rhs.getSign() == 0) [[unlikely]] {
            return Int::Zero();
        }

        // 符号の決定
        int resultSign = lhs.getSign() * rhs.getSign();

        // 自乗検出: a * a → squaring 専用パス (対称性利用で高速)
        Int result;
        if (&lhs == &rhs) {
            IntOps::square(lhs, result);
        } else {
            IntOps::multiplyAbsolute(lhs, rhs, result);
        }
        result.setSign(resultSign);

        return result;
    }

    // 除算の共通エッジケース処理 (特殊状態とゼロ除算)
    // 戻り値: true = 結果が確定 (out に書き込み済み), false = 通常パスへ進む
    static bool handleDivisionEdgeCases(const Int& lhs, const Int& rhs, Int& out) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) [[unlikely]] {
            out = IntSpecialStates::handleDivision(lhs, rhs);
            return true;
        }
        if (rhs.getSign() == 0) [[unlikely]] {
            if (lhs.getSign() == 0) {
                // 0/0 = NaN
                out = Int::NaN();
                out.setState(NumericState::NaN, NumericError::DivideByZero);
            } else {
                // x/0 (x≠0) = ±∞ (IntSpecialStates::handleDivision と一致)
                out = (lhs.getSign() > 0) ? Int::PositiveInfinity() : Int::NegativeInfinity();
            }
            return true;
        }
        if (lhs.getSign() == 0) {
            out = Int::Zero();
            return true;
        }
        return false;
    }

    Int operator/(const Int& lhs, const Int& rhs) {
        Int early;
        if (handleDivisionEdgeCases(lhs, rhs, early)) return early;

        int resultSign = lhs.getSign() * rhs.getSign();
        Int result = lhs;
        result.setSign(1);
        IntOps::divideAbsolute(result, rhs);
        if (result.getSign() != 0) result.setSign(resultSign);
        return result;
    }

    Int operator/(Int&& lhs, const Int& rhs) {
        Int early;
        if (handleDivisionEdgeCases(lhs, rhs, early)) return early;

        int resultSign = lhs.getSign() * rhs.getSign();
        lhs.setSign(1);
        IntOps::divideAbsolute(lhs, rhs);
        if (lhs.getSign() != 0) lhs.setSign(resultSign);
        return std::move(lhs);
    }

    Int operator%(const Int& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) {
            return IntSpecialStates::handleModulo(lhs, rhs);
        }
        if (rhs.getSign() == 0) {
            Int result = Int::NaN();
            result.setState(NumericState::NaN, NumericError::DivideByZero);
            return result;
        }
        if (lhs.getSign() == 0) return Int::Zero();

        Int result = lhs;
        result.setSign(1);
        IntOps::moduloAbsolute(result, rhs);
        if (lhs.getSign() < 0 && result.getSign() != 0) result.setSign(-1);
        return result;
    }

    Int operator%(Int&& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) {
            return IntSpecialStates::handleModulo(lhs, rhs);
        }
        if (rhs.getSign() == 0) {
            Int result = Int::NaN();
            result.setState(NumericState::NaN, NumericError::DivideByZero);
            return result;
        }
        if (lhs.getSign() == 0) return Int::Zero();

        int origSign = lhs.getSign();
        lhs.setSign(1);
        IntOps::moduloAbsolute(lhs, rhs);
        if (origSign < 0 && lhs.getSign() != 0) lhs.setSign(-1);
        return std::move(lhs);
    }

    //------------------------------------------------------------------------------
    // インクリメント/デクリメント演算子
    //------------------------------------------------------------------------------

    Int& operator++(Int& value) {
        if (value.isSpecialState()) return value;
        IntOps::addDelta(value, 1);
        return value;
    }

    Int operator++(Int& value, int) {
        if (value.isSpecialState()) return value;
        Int old = value;
        IntOps::addDelta(value, 1);
        return old;
    }

    Int& operator--(Int& value) {
        if (value.isSpecialState()) return value;
        IntOps::addDelta(value, -1);
        return value;
    }

    Int operator--(Int& value, int) {
        if (value.isSpecialState()) return value;
        Int old = value;
        IntOps::addDelta(value, -1);
        return old;
    }

    //------------------------------------------------------------------------------
    // ビット演算子
    //------------------------------------------------------------------------------

    // NaN (InvalidBitOperation) を生成するヘルパー
    static Int makeBitOpNaN() {
        Int result = Int::NaN();
        result.setState(NumericState::NaN, NumericError::InvalidBitOperation);
        return result;
    }

    Int operator&(const Int& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        Int result = lhs;
        IntOps::bitwiseAnd(result, rhs);
        return result;
    }

    Int operator&(Int&& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseAnd(lhs, rhs);
        return std::move(lhs);
    }

    Int operator&(const Int& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseAnd(rhs, lhs);  // AND は可換
        return std::move(rhs);
    }

    Int operator&(Int&& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseAnd(lhs, rhs);
        return std::move(lhs);
    }

    Int operator|(const Int& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        Int result = lhs;
        IntOps::bitwiseOr(result, rhs);
        return result;
    }

    Int operator|(Int&& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseOr(lhs, rhs);
        return std::move(lhs);
    }

    Int operator|(const Int& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseOr(rhs, lhs);  // OR は可換
        return std::move(rhs);
    }

    Int operator|(Int&& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseOr(lhs, rhs);
        return std::move(lhs);
    }

    // べき乗演算子: a ^ b = pow(a, b)
    Int operator^(const Int& lhs, const Int& rhs) {
        return pow(lhs, rhs);
    }

    // ビット XOR (関数版)
    Int bitwiseXor(const Int& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        Int result = lhs;
        IntOps::bitwiseXor(result, rhs);
        return result;
    }

    Int bitwiseXor(Int&& lhs, const Int& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseXor(lhs, rhs);
        return std::move(lhs);
    }

    Int bitwiseXor(const Int& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseXor(rhs, lhs);  // XOR は可換
        return std::move(rhs);
    }

    Int bitwiseXor(Int&& lhs, Int&& rhs) {
        if (lhs.isSpecialState() || rhs.isSpecialState()) return makeBitOpNaN();
        IntOps::bitwiseXor(lhs, rhs);
        return std::move(lhs);
    }

    Int operator~(const Int& value) {
        if (value.isSpecialState()) return makeBitOpNaN();
        // ビット反転の数学的定義: ~x = -(x+1)
        Int result = value + 1;
        result = -result;
        return result;
    }

    Int operator~(Int&& value) {
        if (value.isSpecialState()) return makeBitOpNaN();
        // ビット反転の数学的定義: ~x = -(x+1)
        value += 1;
        value = -value;
        return std::move(value);
    }

    Int operator<<(const Int& value, int shift) {
        if (value.isSpecialState()) return value;
        if (shift < 0) return value >> (-shift);
        Int result = value;
        IntOps::leftShift(result, shift);
        return result;
    }

    Int operator<<(Int&& value, int shift) {
        if (value.isSpecialState()) return std::move(value);
        if (shift < 0) return std::move(value) >> (-shift);
        IntOps::leftShift(value, shift);
        return std::move(value);
    }

    Int operator>>(const Int& value, int shift) {
        if (value.isSpecialState()) return value;
        if (shift < 0) return value << (-shift);
        Int result = value;
        IntOps::rightShift(result, shift);
        return result;
    }

    Int operator>>(Int&& value, int shift) {
        if (value.isSpecialState()) return std::move(value);
        if (shift < 0) return std::move(value) << (-shift);
        IntOps::rightShift(value, shift);
        return std::move(value);
    }

    //------------------------------------------------------------------------------
    // 比較演算子
    //------------------------------------------------------------------------------

    std::partial_ordering operator<=>(const Int& lhs, const Int& rhs) {
        // Fast path: 両方 Normal (特殊状態チェック不要)
        // GMP の mpz_cmp と同等: 符号付きサイズ比較 → ワード比較
        if (lhs.m_state == NumericState::Normal &&
            rhs.m_state == NumericState::Normal) [[likely]] {
            // 符号比較
            if (lhs.m_sign != rhs.m_sign)
                return lhs.m_sign <=> rhs.m_sign;
            if (lhs.m_sign == 0)
                return std::partial_ordering::equivalent;

            // サイズ比較 (絶対値)
            size_t ln = lhs.m_words.size();
            size_t rn = rhs.m_words.size();
            if (ln != rn) {
                bool less = (ln < rn);
                if (lhs.m_sign < 0) less = !less;
                return less ? std::partial_ordering::less : std::partial_ordering::greater;
            }

            // ワード比較 (MSB から)
            const uint64_t* lp = lhs.m_words.data();
            const uint64_t* rp = rhs.m_words.data();
            for (int i = static_cast (ln) - 1; i >= 0; --i) {
                if (lp[i] != rp[i]) {
                    bool less = (lp[i] < rp[i]);
                    if (lhs.m_sign < 0) less = !less;
                    return less ? std::partial_ordering::less : std::partial_ordering::greater;
                }
            }
            return std::partial_ordering::equivalent;
        }

        // Slow path: 特殊状態 (NaN, Infinity)
        if (lhs.isNaN() || rhs.isNaN())
            return std::partial_ordering::unordered;

        if (lhs.getState() == NumericState::NegativeInfinity) {
            return (rhs.getState() == NumericState::NegativeInfinity)
                ? std::partial_ordering::equivalent : std::partial_ordering::less;
        }
        if (lhs.getState() == NumericState::PositiveInfinity) {
            return (rhs.getState() == NumericState::PositiveInfinity)
                ? std::partial_ordering::equivalent : std::partial_ordering::greater;
        }
        if (rhs.getState() == NumericState::NegativeInfinity)
            return std::partial_ordering::greater;
        if (rhs.getState() == NumericState::PositiveInfinity)
            return std::partial_ordering::less;

        // ここに来るのは片方が Normal で片方が特殊状態の場合
        // (上の条件で NaN/Inf は処理済み)
        return std::partial_ordering::equivalent;
    }

    bool operator==(const Int& lhs, const Int& rhs) {
        if (lhs.isNaN() || rhs.isNaN()) {
            return false;
        }
        return (lhs <=> rhs) == std::partial_ordering::equivalent;
    }

    //------------------------------------------------------------------------------
    // ユーティリティ関数
    //------------------------------------------------------------------------------

    Int abs(const Int& value) {
        if (value.isNaN()) return value;
        if (value.isInfinite()) {
            return (value.getState() == NumericState::NegativeInfinity)
                ? Int::PositiveInfinity() : value;
        }
        if (value.isZero()) return Int::Zero();
        if (value.getSign() < 0) {
            Int result = value;
            result.setSign(1);
            return result;
        }
        return value;
    }

    Int abs(Int&& value) {
        if (value.isNaN()) return std::move(value);
        if (value.isInfinite()) {
            if (value.getState() == NumericState::NegativeInfinity)
                return Int::PositiveInfinity();
            return std::move(value);
        }
        if (value.isZero()) return std::move(value);
        if (value.getSign() < 0) value.setSign(1);
        return std::move(value);
    }

    Int gcd(const Int& a, const Int& b) {
        // 特殊状態の処理
        if (a.isSpecialState() || b.isSpecialState()) {
            return Int::NaN();
        }

        // ゼロの処理
        if (a.getSign() == 0) {
            return abs(b);
        }
        if (b.getSign() == 0) {
            return abs(a);
        }

        // 最適化された内部実装を使用
        return IntOps::gcd(a, b);
    }

    Int lcm(const Int& a, const Int& b) {
        // 特殊状態の処理
        if (a.isSpecialState() || b.isSpecialState()) {
            return Int::NaN();
        }

        // ゼロとの最小公倍数は0
        if (a.getSign() == 0 || b.getSign() == 0) {
            return Int(0);
        }

        Int gcd_value = gcd(a, b);
        return abs((a / gcd_value) * b);
    }

    Int pow(const Int& base, unsigned int exponent) {
        // 特殊ケースの処理
        if (base.isSpecialState()) {
            if (exponent == 0) {
                return Int(1); // 通常は特殊値^0 = 1
            }
            if (base.isNaN()) {
                return Int::NaN();
            }
            if (base.isInfinite()) {
                if (exponent % 2 == 0) {
                    return Int::PositiveInfinity(); // ±∞^(2n) = +∞
                }
                else {
                    return base.getSign() > 0 ?
                        Int::PositiveInfinity() : Int::NegativeInfinity(); // ±∞^(2n+1) = ±∞
                }
            }
        }

        // 基本的なケース
        //【注意】0^0=1 となる
        //【参考】C++ で pow(0, 0) は実装依存だが、標準ライブラリでは 1 を返すことが多い

        if (exponent == 0) {
            return Int(1); // b^0 = 1（任意の値の0乗は1）
        }
        if (base.isZero()) {
            return Int::Zero(); // 0^n = 0（nが正の整数の場合）
        }
        if (exponent == 1) {
            return base; // b^1 = b
        }

        // -1の場合の特別処理
        if (base == Int(-1)) {
            return (exponent % 2 == 0) ? Int(1) : Int(-1); // (-1)^偶数 = 1, (-1)^奇数 = -1
        }

        // 1の場合の特別処理
        if (base.isOne()) {
            return Int(1); // 1^n = 1
        }

        // 巨大な指数の場合のオーバーフロー対策
        // これは実際にはunsigned int型の限界内なので、
        // Int pow(const Int& base, const Int& exponent)で考慮するほど極端なケースはないが、
        // 計算量を考慮して最適化のために含める
        if (exponent > 1000000000) { // オーバーフロー防止閾値
            Int absBase = abs(base);
            if (absBase > Int(1)) {
                // |base| > 1の場合、結果は非常に大きくなる
                if (base.isNegative() && (exponent % 2 != 0)) {
                    return Int::NegativeInfinity(); // 負の底で奇数乗の場合
                }
                return Int::PositiveInfinity();
            }
            // |base| == 1 の場合は通常処理（1 または -1）
            // absBase == 1の場合は通常処理（1または-1）
        }

        // 左→右二進べき乗法 (left-to-right binary exponentiation)
        // 右→左法と同じ乗算回数だが、末尾の不要な squaring を回避する。
        // 例: exp=6 (110₂) → x², x³=x²·x, x⁶=(x³)² で 3 乗算
        int bits = 0;
        {
            unsigned int tmp = exponent;
            while (tmp > 1) { bits++; tmp >>= 1; }
        }

        Int result = base;
        Int temp;  // 一時バッファ再利用
        for (int i = bits - 1; i >= 0; i--) {
            IntOps::mulUnchecked(result, result, temp);
            std::swap(result, temp);
            if ((exponent >> i) & 1) {
                IntOps::mulUnchecked(result, base, temp);
                std::swap(result, temp);
            }
        }

        return result;
    }

    Int pow(const Int& base, const Int& exponent) {
        // 特殊ケースの処理
        if (base.isSpecialState()) {
            if (exponent.isZero()) {
                return Int(1); // 通常は特殊値^0 = 1
            }
            if (base.isNaN() || exponent.isNaN()) {
                return Int::NaN();
            }
            if (base.isInfinite()) {
                if (exponent.isNegative()) {
                    return Int::Zero(); // ∞^(-n) = 0
                }
                // 偶数指数かどうかをチェック
                Int two(2);
                Int modResult = exponent % two;
                if (modResult.isZero()) {
                    return Int::PositiveInfinity(); // ±∞^(2n) = +∞
                }
                else {
                    return base.getSign() > 0 ?
                        Int::PositiveInfinity() : Int::NegativeInfinity(); // ±∞^(2n+1) = ±∞
                }
            }
        }

        // 指数が特殊状態の処理
        if (exponent.isSpecialState()) {
            if (exponent.isNaN()) {
                return Int::NaN();
            }
            if (exponent.isInfinite()) {
                if (exponent.isNegative()) {
                    // base が 1 または -1 の場合は特別処理
                    if (base.isOne()) {
                        return Int(1); // 1^(-∞) = 1
                    }
                    else if (base == Int(-1)) {
                        // -1^(-∞) は未定義とみなして NaN を返す
                        return Int::NaN();
                    }
                    return Int::Zero(); // |base| > 1 または |base| < 1 なら 0
                }
                else {
                    // base が 1 の場合
                    if (base.isOne()) {
                        return Int(1); // 1^∞ = 1
                    }
                    // base が -1 の場合
                    if (base == Int(-1)) {
                        // -1^∞ は未定義とみなして NaN を返す
                        return Int::NaN();
                    }
                    // |base| > 1 なら ∞, |base| < 1 なら 0
                    Int absBase = abs(base);
                    Int one(1);
                    if (absBase > one) {
                        return Int::PositiveInfinity();
                    }
                    else if (absBase < one) {
                        return Int::Zero();
                    }
                }
            }
        }

        // 基本的なケース
        //【注意】0^0=1 となる
        //【参考】C++ で pow(0, 0) は実装依存だが、標準ライブラリでは 1 を返すことが多い

        if (exponent.isZero()) {
            return Int(1);
        }
        if (base.isZero()) {
            if (exponent.isNegative()) {
                // 0^(-n) は未定義（ゼロ除算）
                return Int::NaN();
            }
            return Int::Zero();
        }
        if (exponent.isOne()) {
            return base;
        }
        if (exponent == Int(-1)) {
            // b^(-1) は 1/b だが、Int は整数なので特別扱い
            if (base.isOne() || base == Int(-1)) {
                return base; // 1^(-1) = 1, (-1)^(-1) = -1
            }
            return Int::Zero(); // 整数の逆数は小数になるため、Int としては 0
        }

        // 負の指数の処理
        if (exponent.isNegative()) {
            // 整数の範囲では、|base| > 1 なら結果は 0
            // |base| = 1 なら結果は ±1
            Int absBase = abs(base);
            Int one(1);
            if (absBase > one) {
                return Int::Zero();
            }
            else if (absBase == one) {
                // base が -1 で、exponent が奇数なら -1
                if (base.isNegative()) {
                    Int two(2);
                    Int absExp = abs(exponent);
                    Int modResult = absExp % two;
                    if (!modResult.isZero()) {
                        return Int(-1);
                    }
                }
                return Int(1);
            }
            return Int::Zero();
        }

        // exponent が非常に大きい場合: オーバーフロー扱い
        const size_t MAX_UINT = std::numeric_limits ::max();
        if (exponent.bitLength() > 32 || exponent.toUInt64() > MAX_UINT) {
            // 非常に大きい指数の場合、オーバーフロー扱いにする
            if (abs(base) > Int(1)) {
                return base.isNegative() && exponent.getBit(0) ?
                    Int::NegativeInfinity() : Int::PositiveInfinity();
            }
            else if (base.isOne()) {
                return Int(1);
            }
            else if (base == Int(-1)) {
                // -1 の偶数/奇数乗を判定
                return exponent.getBit(0) ? Int(-1) : Int(1);
            }
            else { // |base| < 1
                return Int::Zero();
            }
        }

        // 通常の指数計算（exponent が unsigned int の範囲内）
        unsigned int expValue = static_cast (exponent.toUInt64());

        // 繰り返し2乗法による計算 (3引数版でバッファ再利用)
        Int result(1);
        Int power = base;
        Int temp;
        while (expValue > 0) {
            if (expValue & 1) {
                IntOps::mulUnchecked(result, power, temp);
                std::swap(result, temp);
            }
            IntOps::square(power, temp);
            std::swap(power, temp);
            expValue >>= 1;
        }
        return result;
    }

    Int powMod(const Int& base, const Int& exponent, const Int& modulus) {
        // Montgomery 冪剰余に委譲 (奇数/偶数 m 両対応)
        return IntModular::powerMod(base, exponent, modulus);
    }

    std::size_t bitCount(const Int& value) {
        // 立っているビットの数を数える
        if (value.isNaN() || value.isInfinite() || value.getSign() < 0) {
            throw std::invalid_argument("bitCount requires non-negative normal value");
        }

        // 値が0の場合
        if (value.getSign() == 0) {
            return 0;
        }

        std::size_t count = 0;
        for (std::size_t i = 0; i < value.size(); ++i) {
            count += static_cast (std::popcount(value.word(i)));
        }

        return count;
    }

    std::pair removeFactor(const Int& value, const Int& factor) {
        Int result;
        uint64_t count = IntOps::removeFactor(value, factor, result);
        return { std::move(result), count };
    }

    bool isProbablePrime(const Int& value, int iterations) {
        // ミラー・ラビン素数判定法

        // 特殊ケースの処理
        if (value.isNaN() || value.isInfinite() || value.getSign() < 0) {
            return false;
        }

        // 小さな値の処理
        if (value.isZero() || value.isOne()) {
            return false;
        }

        if (value == 2 || value == 3) {
            return true;
        }

        // 偶数チェック
        if (value.isEven()) {
            return false; // 2以外の偶数は素数ではない
        }

        // ミラー・ラビン法の基本実装
        // value-1 = 2^s * d という形に分解
        Int d = value - 1;
        int s = 0;
        while (d.isEven()) {
            d >>= 1;
            s++;
        }

        // ランダム性を持つべきだが、簡易実装では固定値を使用
        Int a_values[] = { Int(2), Int(3), Int(5), Int(7), Int(11), Int(13), Int(17), Int(19), Int(23) };
        int num_tests = (iterations < 9) ? iterations : 9;

        for (int i = 0; i < num_tests; ++i) {
            Int a = a_values[i];

            // value以上の場合はスキップ
            if (a >= value) {
                continue;
            }

            // x = a^d mod value を計算
            Int x = powMod(a, d, value);

            if (x.isOne() || x == value - 1) {
                continue;
            }

            bool is_witness = true;
            for (int j = 1; j < s; ++j) {
                { Int sq; IntOps::square(x, sq); x = sq % value; }
                if (x == value - 1) {
                    is_witness = false;
                    break;
                }
            }

            if (is_witness) {
                return false; // 合成数
            }
        }

        return true; // おそらく素数
    }

    //--------------------------------------------------------------------------
    // 単一ワード算術演算子 (GMP _ui/_si 相当)
    //--------------------------------------------------------------------------

    // === addScalar ===

    Int addScalar(const Int& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] return lhs;
        if (rhs == 0) return lhs;
        if (lhs.getSign() == 0) return Int(rhs);
        Int result(lhs);
        IntOps::addWord(result, rhs);
        return result;
    }

    Int addScalar(Int&& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] return std::move(lhs);
        if (rhs == 0) return std::move(lhs);
        if (lhs.getSign() == 0) return Int(rhs);
        IntOps::addWord(lhs, rhs);
        return std::move(lhs);
    }

    // === subScalar ===

    Int subScalar(const Int& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] return lhs;
        if (rhs == 0) return lhs;
        if (lhs.getSign() == 0) { Int r(rhs); r.setSign(-1); return r; }
        Int result(lhs);
        IntOps::subWord(result, rhs);
        return result;
    }

    Int subScalar(Int&& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] return std::move(lhs);
        if (rhs == 0) return std::move(lhs);
        if (lhs.getSign() == 0) {
            lhs = Int(rhs);
            lhs.setSign(-1);
            return std::move(lhs);
        }
        IntOps::subWord(lhs, rhs);
        return std::move(lhs);
    }

    Int rsubScalar(uint64_t lhs, const Int& rhs) {
        if (rhs.isSpecialState()) [[unlikely]] return -rhs;
        if (rhs.getSign() == 0) return Int(lhs);
        if (lhs == 0) return -rhs;
        Int result(rhs);
        result.setSign(-result.getSign());
        IntOps::addWord(result, lhs);
        return result;
    }

    // === mulScalar ===

    Int mulScalar(const Int& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] return lhs;
        if (lhs.getSign() == 0 || rhs == 0) return Int(0);
        if (rhs == 1) return lhs;
        Int result(lhs);
        IntOps::multiplyWord(result, rhs);
        return result;
    }

    Int mulScalar(Int&& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] return std::move(lhs);
        if (lhs.getSign() == 0 || rhs == 0) return Int(0);
        if (rhs == 1) return std::move(lhs);
        IntOps::multiplyWord(lhs, rhs);
        return std::move(lhs);
    }

    // === divScalar ===

    Int divScalar(const Int& lhs, uint64_t rhs) {
        if (rhs == 0) { Int r; r.setState(NumericState::NaN); return r; }
        if (lhs.isSpecialState()) [[unlikely]] return lhs;
        if (lhs.getSign() == 0) return Int(0);
        if (rhs == 1) return lhs;
        Int result(lhs);
        IntOps::divWord(result, rhs);
        return result;
    }

    Int divScalar(Int&& lhs, uint64_t rhs) {
        if (rhs == 0) { Int r; r.setState(NumericState::NaN); return r; }
        if (lhs.isSpecialState()) [[unlikely]] return std::move(lhs);
        if (lhs.getSign() == 0) return std::move(lhs);
        if (rhs == 1) return std::move(lhs);
        IntOps::divWord(lhs, rhs);
        return std::move(lhs);
    }

    // === modScalarU (余り uint64_t) ===

    uint64_t modScalarU(const Int& lhs, uint64_t rhs) {
        if (rhs == 0 || lhs.isSpecialState() || lhs.getSign() == 0)
            return 0;
        size_t n = lhs.size();
        constexpr size_t STACK_LIMIT = 64;
        uint64_t stack_buf[STACK_LIMIT];
        std::unique_ptr heap_buf;
        uint64_t* q = stack_buf;
        if (n > STACK_LIMIT) {
            heap_buf.reset(new uint64_t[n]);
            q = heap_buf.get();
        }
        return mpn::divmod_1(q, lhs.data(), n, rhs);
    }

    // === int64_t 版 (符号分解して uint64_t 版に委譲) ===

    static uint64_t abs64(int64_t v) {
        return (v >= 0) ? static_cast (v)
                        : static_cast (-(v + 1)) + 1u;
    }

    Int addScalar(const Int& lhs, int64_t rhs) {
        return (rhs >= 0) ? addScalar(lhs, static_cast (rhs))
                          : subScalar(lhs, abs64(rhs));
    }
    Int addScalar(Int&& lhs, int64_t rhs) {
        return (rhs >= 0) ? addScalar(std::move(lhs), static_cast (rhs))
                          : subScalar(std::move(lhs), abs64(rhs));
    }

    Int subScalar(const Int& lhs, int64_t rhs) {
        return (rhs >= 0) ? subScalar(lhs, static_cast (rhs))
                          : addScalar(lhs, abs64(rhs));
    }
    Int subScalar(Int&& lhs, int64_t rhs) {
        return (rhs >= 0) ? subScalar(std::move(lhs), static_cast (rhs))
                          : addScalar(std::move(lhs), abs64(rhs));
    }
    Int rsubScalar(int64_t lhs, const Int& rhs) {
        if (lhs >= 0) return rsubScalar(static_cast (lhs), rhs);
        return -(addScalar(rhs, abs64(lhs)));
    }

    Int mulScalar(const Int& lhs, int64_t rhs) {
        Int result = mulScalar(lhs, abs64(rhs));
        if (rhs < 0 && result.getSign() != 0) result.setSign(-result.getSign());
        return result;
    }
    Int mulScalar(Int&& lhs, int64_t rhs) {
        Int result = mulScalar(std::move(lhs), abs64(rhs));
        if (rhs < 0 && result.getSign() != 0) result.setSign(-result.getSign());
        return result;
    }

    Int divScalar(const Int& lhs, int64_t rhs) {
        Int result = divScalar(lhs, abs64(rhs));
        if (rhs < 0 && result.getSign() != 0) result.setSign(-result.getSign());
        return result;
    }
    Int divScalar(Int&& lhs, int64_t rhs) {
        Int result = divScalar(std::move(lhs), abs64(rhs));
        if (rhs < 0 && result.getSign() != 0) result.setSign(-result.getSign());
        return result;
    }

    Int modScalar(const Int& lhs, int64_t rhs) {
        uint64_t rem = modScalarU(lhs, abs64(rhs));
        if (rem == 0) return Int(0);
        Int result(rem);
        if (lhs.getSign() < 0) result.setSign(-1);
        return result;
    }

    // === 複合代入 (uint64_t) ===

    Int& Int::plusEqScalar(uint64_t rhs) {
        if (isSpecialState()) return *this;
        if (rhs == 0) return *this;
        if (getSign() == 0) { *this = Int(rhs); return *this; }
        IntOps::addWord(*this, rhs);
        return *this;
    }
    Int& Int::minusEqScalar(uint64_t rhs) {
        if (isSpecialState()) return *this;
        if (rhs == 0) return *this;
        if (getSign() == 0) { *this = Int(rhs); setSign(-1); return *this; }
        IntOps::subWord(*this, rhs);
        return *this;
    }
    Int& Int::mulEqScalar(uint64_t rhs) {
        if (isSpecialState()) return *this;
        if (getSign() == 0 || rhs == 0) { *this = Int(0); return *this; }
        if (rhs == 1) return *this;
        IntOps::multiplyWord(*this, rhs);
        return *this;
    }
    Int& Int::divEqScalar(uint64_t rhs) {
        if (rhs == 0) { setState(NumericState::NaN); return *this; }
        if (isSpecialState() || getSign() == 0 || rhs == 1) return *this;
        IntOps::divWord(*this, rhs);
        return *this;
    }
    Int& Int::modEqScalar(uint64_t rhs) {
        if (rhs == 0 || isSpecialState() || getSign() == 0) return *this;
        uint64_t rem = *this % rhs;
        int old_sign = getSign();
        *this = Int(rem);
        if (rem != 0 && old_sign < 0) setSign(-1);
        return *this;
    }

    // === 複合代入 (int64_t) ===

    Int& Int::plusEqScalar(int64_t rhs) {
        return (rhs >= 0) ? plusEqScalar(static_cast (rhs))
                          : minusEqScalar(abs64(rhs));
    }
    Int& Int::minusEqScalar(int64_t rhs) {
        return (rhs >= 0) ? minusEqScalar(static_cast (rhs))
                          : plusEqScalar(abs64(rhs));
    }
    Int& Int::mulEqScalar(int64_t rhs) {
        mulEqScalar(abs64(rhs));
        if (rhs < 0 && getSign() != 0) setSign(-getSign());
        return *this;
    }
    Int& Int::divEqScalar(int64_t rhs) {
        divEqScalar(abs64(rhs));
        if (rhs < 0 && getSign() != 0) setSign(-getSign());
        return *this;
    }
    Int& Int::modEqScalar(int64_t rhs) {
        int old_sign = getSign();
        modEqScalar(abs64(rhs));
        if (old_sign < 0 && getSign() > 0) setSign(-1);
        return *this;
    }

    //--------------------------------------------------------------------------
    // 単一ワード比較演算子
    //--------------------------------------------------------------------------

    std::partial_ordering cmpScalar(const Int& lhs, int64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] {
            if (lhs.isNaN()) return std::partial_ordering::unordered;
            if (lhs.isInfinite()) return (lhs.getSign() > 0) ? std::partial_ordering::greater
                                                              : std::partial_ordering::less;
        }
        int rhs_sign = (rhs > 0) ? 1 : (rhs < 0) ? -1 : 0;
        if (lhs.getSign() != rhs_sign) {
            return (lhs.getSign() < rhs_sign) ? std::partial_ordering::less
                                               : std::partial_ordering::greater;
        }
        if (rhs_sign == 0) return std::partial_ordering::equivalent;

        uint64_t abs_rhs = abs64(rhs);
        if (lhs.size() > 1) {
            return (lhs.getSign() > 0) ? std::partial_ordering::greater
                                        : std::partial_ordering::less;
        }
        uint64_t abs_lhs = lhs.word(0);
        if (abs_lhs == abs_rhs) return std::partial_ordering::equivalent;
        bool lhs_abs_greater = (abs_lhs > abs_rhs);
        if (lhs.getSign() < 0) lhs_abs_greater = !lhs_abs_greater;
        return lhs_abs_greater ? std::partial_ordering::greater
                               : std::partial_ordering::less;
    }

    bool eqScalar(const Int& lhs, int64_t rhs) {
        if (lhs.isSpecialState()) return false;
        int rhs_sign = (rhs > 0) ? 1 : (rhs < 0) ? -1 : 0;
        if (lhs.getSign() != rhs_sign) return false;
        if (rhs_sign == 0) return true;
        if (lhs.size() != 1) return false;
        return lhs.word(0) == abs64(rhs);
    }

    std::partial_ordering cmpScalar(const Int& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) [[unlikely]] {
            if (lhs.isNaN()) return std::partial_ordering::unordered;
            if (lhs.isInfinite()) return (lhs.getSign() > 0) ? std::partial_ordering::greater
                                                              : std::partial_ordering::less;
        }
        if (lhs.getSign() < 0) return std::partial_ordering::less;
        if (lhs.getSign() == 0) {
            return (rhs == 0) ? std::partial_ordering::equivalent
                              : std::partial_ordering::less;
        }
        if (rhs == 0) return std::partial_ordering::greater;
        if (lhs.size() > 1) return std::partial_ordering::greater;
        uint64_t v = lhs.word(0);
        if (v == rhs) return std::partial_ordering::equivalent;
        return (v > rhs) ? std::partial_ordering::greater
                         : std::partial_ordering::less;
    }

    bool eqScalar(const Int& lhs, uint64_t rhs) {
        if (lhs.isSpecialState()) return false;
        if (rhs == 0) return lhs.getSign() == 0;
        if (lhs.getSign() != 1 || lhs.size() != 1) return false;
        return lhs.word(0) == rhs;
    }

} // namespace calx