// Copyright (C) 2026 Kiyotsugu Arai
// SPDX-License-Identifier: LGPL-3.0-or-later

// IntBase.cpp
// Int クラスの基本実装

#include <math/core/mp/Int/IntBase.hpp>
#include <math/core/mp/Int/IntSpecialStates.hpp>
#include <math/core/mp/Int/IntOps.hpp>
#include <math/core/mp/Int/IntIO.hpp>
#include <math/core/numeric_state.hpp>
#include <math/core/common.hpp> // OverflowError などの例外クラスのため
#include <sstream>
#include <string>
#include <cmath>
#include <iomanip> // std::setfill, std::setw など
#include <algorithm> // std::reverse, std::max
#include <bit> // C++20の std::countl_zero など

namespace calx {

    // デフォルトコンストラクタ
    Int::Int() : m_sign(0), m_state(NumericState::Normal), m_error(NumericError::None) {
        // ゼロに初期化 - m_wordsは空のままで良い
    }

    // int値からのコンストラクタ
    Int::Int(int value) : m_state(NumericState::Normal), m_error(NumericError::None) {
        if (value == 0) {
            m_sign = 0;
            // m_wordsは空のまま
        }
        else if (value > 0) {
            m_sign = 1;
            m_words.push_back(static_cast<uint64_t>(value));
        }
        else {
            m_sign = -1;
            m_words.push_back(static_cast<uint64_t>(-static_cast<int64_t>(value)));
        }
    }

    // int64_t値からのコンストラクタ
    Int::Int(int64_t value) : m_state(NumericState::Normal), m_error(NumericError::None) {
        if (value == 0) {
            m_sign = 0;
            // m_wordsは空のまま
        }
        else if (value > 0) {
            m_sign = 1;
            m_words.push_back(static_cast<uint64_t>(value));
        }
        else if (value == INT64_MIN) {
            // INT64_MINは特別扱い
            m_sign = -1;
            m_words.push_back(static_cast<uint64_t>(INT64_MAX) + 1);
        }
        else {
            m_sign = -1;
            m_words.push_back(static_cast<uint64_t>(-value));
        }
    }

    // uint64_t値からのコンストラクタ
    Int::Int(uint64_t value) : m_state(NumericState::Normal), m_error(NumericError::None) {
        if (value == 0) {
            m_sign = 0;
            // m_wordsは空のまま
        }
        else {
            m_sign = 1;
            m_words.push_back(value);
        }
    }

    // 文字列からのコンストラクタ
    Int::Int(std::string_view str, int base) {
        *this = IntIOUtils::fromString(str, base);
    }

    // コピーコンストラクタ
    Int::Int(const Int& other)
        : m_words(other.m_words),
        m_sign(other.m_sign),
        m_state(other.m_state),
        m_error(other.m_error) {
    }

    // ムーブコンストラクタ
    Int::Int(Int&& other) noexcept
        : m_words(std::move(other.m_words)),
        m_sign(other.m_sign),
        m_state(other.m_state),
        m_error(other.m_error) {
        other.m_sign = 0;
        other.m_state = NumericState::Normal;
        other.m_error = NumericError::None;
    }

    // 代入演算子
    Int& Int::operator=(const Int& other) {
        if (this != &other) {
            m_words = other.m_words;
            m_sign = other.m_sign;
            m_state = other.m_state;
            m_error = other.m_error;
        }
        return *this;
    }

    // ムーブ代入演算子
    Int& Int::operator=(Int&& other) noexcept {
        if (this != &other) {
            m_words = std::move(other.m_words);
            m_sign = other.m_sign;
            m_state = other.m_state;
            m_error = other.m_error;

            other.m_sign = 0;
            other.m_state = NumericState::Normal;
            other.m_error = NumericError::None;
        }
        return *this;
    }

    // int値の代入
    Int& Int::operator=(int value) {
        if (value == 0) {
            m_words.clear();
            m_sign = 0;
        }
        else if (value > 0) {
            m_words.clear();
            m_words.push_back(static_cast<uint64_t>(value));
            m_sign = 1;
        }
        else {
            m_words.clear();
            m_words.push_back(static_cast<uint64_t>(-static_cast<int64_t>(value)));
            m_sign = -1;
        }
        m_state = NumericState::Normal;
        m_error = NumericError::None;
        return *this;
    }

    // 特殊状態の取得メソッド
    Int Int::nan() {
        Int result;
        result.m_state = NumericState::NaN;
        result.m_error = NumericError::ExplicitNaN;
        return result;
    }

    Int Int::infinity() {
        Int result;
        result.m_state = NumericState::PositiveInfinity;
        result.m_sign = 1;
        return result;
    }

    Int Int::negInfinity() {
        Int result;
        result.m_state = NumericState::NegativeInfinity;
        result.m_sign = -1;
        return result;
    }

    // 内部状態の正規化
    void Int::normalize() {
        // ワード配列から先頭のゼロを削除
        while (!m_words.empty() && m_words.back() == 0) {
            m_words.pop_back();
        }

        // ゼロかどうかのチェック
        if (m_words.empty()) {
            m_sign = 0;
        }

        // ワード数の人為的上限なし。メモリ不足時は std::bad_alloc が送出される。
    }

    size_t Int::trimZeroWords() {
        // MSB 側のゼロワード除去 (Int::normalize() と同等)
        while (!m_words.empty() && m_words.back() == 0) {
            m_words.pop_back();
        }
        if (m_words.empty()) {
            m_sign = 0;
            return 0;
        }
        // LSB 側のゼロワード除去 (SboWords::erase = memmove, alloc なし)
        size_t lsb = 0;
        while (lsb < m_words.size() - 1 && m_words[lsb] == 0) {
            ++lsb;
        }
        if (lsb > 0) {
            m_words.erase(m_words.begin(), m_words.begin() + lsb);
        }
        return lsb;
    }

    // 文字列変換
    std::string Int::toString(int base) const {
        return IntIOUtils::toString(*this, base);
    }

    // 16進数文字列表現
    std::string Int::toHexString(bool uppercase) const {
        // 特殊状態の処理
        std::string specialResult = IntSpecialStates::handleToString(*this);
        if (!specialResult.empty()) {
            return specialResult;
        }

        if (isZero()) {
            return "0";
        }

        std::string result;
        // 16進数表現を生成
        for (auto it = m_words.rbegin(); it != m_words.rend(); ++it) {
            std::stringstream ss;
            ss << std::hex;
            if (uppercase) {
                ss << std::uppercase;
            }
            ss << std::setfill('0');
            // 最初の値以外は16桁になるように0埋め
            if (it != m_words.rbegin()) {
                ss << std::setw(16);
            }
            ss << *it;
            result += ss.str();
        }

        // 先頭の0を削除
        result.erase(0, result.find_first_not_of('0'));
        if (result.empty()) {
            return "0";
        }

        // 符号を追加
        if (m_sign < 0) {
            result = "-" + result;
        }

        return result;
    }

    // 2進数文字列表現
    std::string Int::toBinaryString() const {
        // 特殊状態の処理
        std::string specialResult = IntSpecialStates::handleToString(*this);
        if (!specialResult.empty()) {
            return specialResult;
        }

        if (isZero()) {
            return "0";
        }

        std::string result;
        for (auto it = m_words.rbegin(); it != m_words.rend(); ++it) {
            uint64_t word = *it;
            for (int i = 63; i >= 0; --i) {
                if (word & (1ULL << i)) {
                    result += '1';
                }
                else if (!result.empty() || i == 0) {
                    // 先頭の0は無視するが、すでに値が追加されている場合や最下位ビットの場合は追加
                    result += '0';
                }
            }
        }

        // 符号を追加
        if (m_sign < 0) {
            result = "-" + result;
        }

        return result;
    }

    // 8進数文字列表現
    std::string Int::toOctalString() const {
        // 特殊状態の処理
        std::string specialResult = IntSpecialStates::handleToString(*this);
        if (!specialResult.empty()) {
            return specialResult;
        }

        if (isZero()) {
            return "0";
        }

        Int copy = *this;
        if (copy.m_sign < 0) {
            copy.m_sign = 1; // 符号は最後に処理
        }

        std::string result;
        Int base(8);

        // 数値を8進数で文字列に変換
        while (!copy.isZero()) {
            Int remainder;
            copy = IntOps::divmod(copy, base, remainder);
            result.push_back('0' + remainder.toInt());
        }

        // 結果を反転（最下位桁から最上位桁へ）
        std::reverse(result.begin(), result.end());

        // 符号を追加
        if (m_sign < 0) {
            result = "-" + result;
        }

        return result;
    }

    // int型への変換
    int Int::toInt() const {
        if (isNaN() || isInfinite()) {
            throw OverflowError("Cannot convert NaN or infinity to int");
        }

        if (isZero()) {
            return 0;
        }

        // 1ワードまでしか変換できない
        if (m_words.size() > 1) {
            // INT_MIN の特殊ケース: 負の値で2ワード目が必要な場合
            if (m_words.size() == 2 && m_words[1] == 0 && m_sign < 0) {
                // このケースは許容
            }
            else {
                throw OverflowError("Int value too large for int conversion");
            }
        }

        uint64_t wordValue = m_words[0];

        // 正の値の場合
        if (m_sign > 0) {
            if (wordValue > static_cast<uint64_t>(std::numeric_limits<int>::max())) {
                throw OverflowError("Int value too large for int conversion");
            }
            return static_cast<int>(wordValue);
        }

        // 負の値の場合
        // 特別なケース: INT_MIN (-2147483648) は 2147483648 の負数
        if (wordValue == static_cast<uint64_t>(std::numeric_limits<int>::max()) + 1) {
            return std::numeric_limits<int>::min();
        }

        if (wordValue > static_cast<uint64_t>(std::numeric_limits<int>::max())) {
            throw OverflowError("Int value too small for int conversion");
        }

        return -static_cast<int>(wordValue);
    }

    // 64ビット整数への変換
    int64_t Int::toInt64() const {
        if (isNaN() || isInfinite()) {
            throw OverflowError("Cannot convert NaN or infinity to int64_t");
        }

        if (isZero()) {
            return 0;
        }

        if (m_words.size() > 1 ||
            (m_sign > 0 && m_words[0] > static_cast<uint64_t>(std::numeric_limits<int64_t>::max())) ||
            (m_sign < 0 && m_words[0] > static_cast<uint64_t>(std::numeric_limits<int64_t>::max()) + 1)) {
            throw OverflowError("Int value too large for int64_t conversion");
        }

        int64_t value = static_cast<int64_t>(m_words[0]);
        if (m_sign < 0) {
            if (value < 0 && value != INT64_MIN) {
                throw OverflowError("Int value too small for int64_t conversion");
            }
            if (value == INT64_MIN) {
                return INT64_MIN;
            }
            value = -value;
        }
        return value;
    }

    // 符号なし64ビット整数への変換
    uint64_t Int::toUInt64() const {
        if (isNaN() || isInfinite() || m_sign < 0) {
            throw OverflowError("Cannot convert NaN, infinity, or negative value to uint64_t");
        }

        if (isZero()) {
            return 0;
        }

        if (m_words.size() > 1) {
            throw OverflowError("Int value too large for uint64_t conversion");
        }

        return m_words[0];
    }

    // size_t型への変換
    size_t Int::toSizeT() const {
        if (isNaN() || isInfinite() || m_sign < 0) {
            throw OverflowError("Cannot convert NaN, infinity, or negative value to size_t");
        }

        if (isZero()) {
            return 0;
        }

        if (m_words.size() > 1 || (sizeof(size_t) < sizeof(uint64_t) &&
            m_words[0] > static_cast<uint64_t>(std::numeric_limits<size_t>::max()))) {
            throw OverflowError("Int value too large for size_t conversion");
        }

        return static_cast<size_t>(m_words[0]);
    }

    // 倍精度浮動小数点数への変換
    double Int::toDouble() const {
        if (isNaN()) {
            return std::numeric_limits<double>::quiet_NaN();
        }

        if (m_state == NumericState::PositiveInfinity) {
            return std::numeric_limits<double>::infinity();
        }

        if (m_state == NumericState::NegativeInfinity) {
            return -std::numeric_limits<double>::infinity();
        }

        if (isZero()) {
            return 0.0;
        }

        double result = 0.0;
        double factor = 1.0;

        for (size_t i = 0; i < m_words.size(); ++i) {
            result += static_cast<double>(m_words[i]) * factor;
            factor *= static_cast<double>(UINT64_MAX) + 1.0;
        }

        if (m_sign < 0) {
            result = -result;
        }

        return result;
    }

    double Int::toDouble2Exp(int64_t* exp) const {
        if (isZero() || isNaN() || isInfinite()) {
            *exp = 0;
            if (isNaN()) return std::numeric_limits<double>::quiet_NaN();
            if (m_state == NumericState::PositiveInfinity) return std::numeric_limits<double>::infinity();
            if (m_state == NumericState::NegativeInfinity) return -std::numeric_limits<double>::infinity();
            return 0.0;
        }

        size_t bl = bitLength();
        *exp = static_cast<int64_t>(bl);

        // 上位 53 ビットを取得して [0.5, 1.0) の double を構成
        size_t n = m_words.size();
        uint64_t top = m_words[n - 1];
        int top_bits = 64 - std::countl_zero(top);

        // 上位 53 ビットを収集して mantissa ∈ [2^52, 2^53) を構成
        uint64_t mantissa;
        if (top_bits >= 53) {
            mantissa = top >> (top_bits - 53);
        } else {
            int need = 53 - top_bits;
            mantissa = top << need;  // まず左シフトで 53 ビット幅に拡張
            if (n >= 2 && need <= 64) {
                uint64_t w1 = m_words[n - 2];
                mantissa |= (w1 >> (64 - need));
            }
            // n==1 かつ top_bits < 53: 下位ビットは 0 で埋まる (正しい)
        }

        // d = mantissa / 2^53 ∈ [0.5, 1.0)
        double d = static_cast<double>(mantissa) * (1.0 / static_cast<double>(1ULL << 53));
        // d ∈ [0.25, 0.5) → 修正: 2 倍して exp を 1 減らす
        // 実際: mantissa は 53 ビット値で MSB=1 なので mantissa ∈ [2^52, 2^53)
        // d = mantissa / 2^53 ∈ [0.5, 1.0) ✓

        if (m_sign < 0) d = -d;
        return d;
    }

    bool Int::isDivisibleBy2Exp(size_t b) const {
        if (b == 0 || isZero()) return true;
        if (isNaN() || isInfinite()) return false;

        size_t full_words = b / 64;
        size_t rem_bits = b % 64;
        size_t n = m_words.size();

        // 下位 full_words 個が全 0 か
        size_t check = std::min(full_words, n);
        for (size_t i = 0; i < check; ++i) {
            if (m_words[i] != 0) return false;
        }
        if (full_words >= n) return true;  // b > bitLength なら全ビット 0 の範囲内

        // 残りビットのマスクチェック
        if (rem_bits > 0) {
            uint64_t mask = (1ULL << rem_bits) - 1;
            if ((m_words[full_words] & mask) != 0) return false;
        }
        return true;
    }

    bool Int::isCongruent2Exp(const Int& c, size_t b) const {
        if (b == 0) return true;
        if (isNaN() || isInfinite() || c.isNaN() || c.isInfinite()) return false;

        // 下位 b ビットが一致するか (符号を考慮して差の下位ビットをチェック)
        // 同符号: 絶対値の下位 b ビットを直接比較
        // 異符号: (this - c) の下位 b ビットが 0 か
        // 簡易実装: 差を取って isDivisibleBy2Exp
        // ただし O(n) の減算が発生。最適化は必要に応じて。
        Int diff = *this - c;
        return diff.isDivisibleBy2Exp(b);
    }

    // ビット長の計算
    size_t Int::bitLength() const {
        if (isZero() || isNaN() || isInfinite()) {
            return 0;
        }

        if (m_words.empty()) {
            return 0;
        }

        // 最上位ワードのビット数を計算
        uint64_t msw = m_words.back();

        // C++20の関数を使用
#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
        int msw_bits = 64 - std::countl_zero(msw);
#else
    // 古いコンパイラ向けのフォールバック
        int msw_bits = 0;
        for (int i = 63; i >= 0; --i) {
            if ((msw & (1ULL << i)) != 0) {
                msw_bits = i + 1;
                break;
            }
        }
#endif

        // 総ビット数
        return (m_words.size() - 1) * 64 + msw_bits;
    }

    // 特定位置のビット取得
    bool Int::getBit(size_t position) const {
        if (isZero() || isNaN() || isInfinite()) {
            return false;
        }

        size_t word_index = position / 64;
        size_t bit_index = position % 64;

        if (word_index >= m_words.size()) {
            return false;
        }

        return (m_words[word_index] & (1ULL << bit_index)) != 0;
    }

    // ビットセット
    void Int::setBit(size_t position) {
        if (isSpecialState()) return;
        if (m_sign < 0) {
            // 負の数: 2の補数セマンティクスで OR 演算
            *this |= (Int(1) << static_cast<int>(position));
            return;
        }
        size_t word_index = position / 64;
        size_t bit_index = position % 64;
        if (word_index >= m_words.size()) {
            m_words.resize(word_index + 1, 0);
        }
        m_words[word_index] |= (1ULL << bit_index);
        if (m_sign == 0) m_sign = 1;
    }

    // ビットクリア
    void Int::clearBit(size_t position) {
        if (isSpecialState()) return;
        if (m_sign < 0) {
            // 負の数: 2の補数セマンティクスで AND 演算
            *this &= ~(Int(1) << static_cast<int>(position));
            return;
        }
        size_t word_index = position / 64;
        size_t bit_index = position % 64;
        if (word_index >= m_words.size()) return;  // 既に 0
        m_words[word_index] &= ~(1ULL << bit_index);
        normalize();
    }

    // ビット反転
    void Int::complementBit(size_t position) {
        if (isSpecialState()) return;
        if (m_sign < 0) {
            // 負の数: 2の補数セマンティクスで XOR 演算
            Int mask = Int(1) << static_cast<int>(position);
            IntOps::bitwiseXor(*this, mask);
            return;
        }
        size_t word_index = position / 64;
        size_t bit_index = position % 64;
        if (word_index >= m_words.size()) {
            m_words.resize(word_index + 1, 0);
        }
        m_words[word_index] ^= (1ULL << bit_index);
        if (m_sign == 0) m_sign = 1;
        normalize();
    }

    // scanBit1: startPos 以降の最初のセットビットの位置
    size_t Int::scanBit1(size_t startPos) const {
        if (isSpecialState()) return SIZE_MAX;

        if (m_sign < 0) {
            // 負の数: 2の補数 = ~(|this|-1)
            // scanBit1 = (|this|-1) で最初の 0-bit を探す
            Int mag_minus_1 = abs(*this) - 1;
            size_t word_index = startPos / 64;
            size_t bit_index = startPos % 64;
            // (|this|-1) のワード内で 0 ビットを探す
            if (word_index < mag_minus_1.m_words.size()) {
                uint64_t word = ~mag_minus_1.m_words[word_index];
                word >>= bit_index;
                if (word != 0) {
                    return startPos + static_cast<size_t>(std::countr_zero(word));
                }
                for (size_t i = word_index + 1; i < mag_minus_1.m_words.size(); i++) {
                    uint64_t w = ~mag_minus_1.m_words[i];
                    if (w != 0) {
                        return i * 64 + static_cast<size_t>(std::countr_zero(w));
                    }
                }
            }
            // ストレージ外は全て 0 → 反転すると全て 1
            size_t beyond = mag_minus_1.m_words.size() * 64;
            return (startPos >= beyond) ? startPos : beyond;
        }

        if (isZero()) return SIZE_MAX;

        size_t word_index = startPos / 64;
        size_t bit_index = startPos % 64;
        if (word_index >= m_words.size()) return SIZE_MAX;

        // 最初のワード (部分)
        uint64_t word = m_words[word_index] >> bit_index;
        if (word != 0) {
            return startPos + static_cast<size_t>(std::countr_zero(word));
        }
        // 後続のワード
        for (size_t i = word_index + 1; i < m_words.size(); i++) {
            if (m_words[i] != 0) {
                return i * 64 + static_cast<size_t>(std::countr_zero(m_words[i]));
            }
        }
        return SIZE_MAX;
    }

    // scanBit0: startPos 以降の最初のクリアビットの位置
    size_t Int::scanBit0(size_t startPos) const {
        if (isSpecialState()) return SIZE_MAX;

        if (m_sign < 0) {
            // 負の数: 2の補数 = ~(|this|-1)
            // scanBit0 = (|this|-1) で最初の 1-bit を探す
            Int mag_minus_1 = abs(*this) - 1;
            size_t word_index = startPos / 64;
            size_t bit_index = startPos % 64;
            if (word_index < mag_minus_1.m_words.size()) {
                uint64_t word = mag_minus_1.m_words[word_index] >> bit_index;
                if (word != 0) {
                    return startPos + static_cast<size_t>(std::countr_zero(word));
                }
                for (size_t i = word_index + 1; i < mag_minus_1.m_words.size(); i++) {
                    if (mag_minus_1.m_words[i] != 0) {
                        return i * 64 + static_cast<size_t>(std::countr_zero(mag_minus_1.m_words[i]));
                    }
                }
            }
            // ストレージ外は全て 0 → 反転すると全て 1 → 0 ビットなし
            return SIZE_MAX;
        }

        if (isZero()) return startPos;  // 全ビット 0

        size_t word_index = startPos / 64;
        size_t bit_index = startPos % 64;

        if (word_index < m_words.size()) {
            // 最初のワード (部分) で 0 ビットを探す
            uint64_t word = ~m_words[word_index];
            word >>= bit_index;
            if (word != 0) {
                return startPos + static_cast<size_t>(std::countr_zero(word));
            }
            // 後続のワード
            for (size_t i = word_index + 1; i < m_words.size(); i++) {
                if (m_words[i] != UINT64_MAX) {
                    return i * 64 + static_cast<size_t>(std::countr_zero(~m_words[i]));
                }
            }
        }
        // ストレージ外は全て 0
        size_t beyond = m_words.size() * 64;
        return (startPos >= beyond) ? startPos : beyond;
    }

    // hammingDistance: 2つの整数の異なるビット数 (GMP mpz_hamdist 互換)
    size_t Int::hammingDistance(const Int& a, const Int& b) {
        // 特殊状態
        if (a.isSpecialState() || b.isSpecialState()) return SIZE_MAX;
        // 符号が異なる場合は無限大 (GMP と同じ)
        if ((a.m_sign < 0) != (b.m_sign < 0)) return SIZE_MAX;

        if (a.m_sign >= 0 && b.m_sign >= 0) {
            // 両方非負: XOR の popcount
            size_t max_size = std::max(a.m_words.size(), b.m_words.size());
            size_t count = 0;
            for (size_t i = 0; i < max_size; i++) {
                uint64_t wa = (i < a.m_words.size()) ? a.m_words[i] : 0;
                uint64_t wb = (i < b.m_words.size()) ? b.m_words[i] : 0;
                count += static_cast<size_t>(std::popcount(wa ^ wb));
            }
            return count;
        }

        // 両方負: 2の補数 = ~(|x|-1)
        // hamming(-a, -b) = popcount( ~(|a|-1) XOR ~(|b|-1) ) = popcount( (|a|-1) XOR (|b|-1) )
        Int a_mag_m1 = abs(a) - 1;
        Int b_mag_m1 = abs(b) - 1;
        size_t max_size = std::max(a_mag_m1.m_words.size(), b_mag_m1.m_words.size());
        size_t count = 0;
        for (size_t i = 0; i < max_size; i++) {
            uint64_t wa = (i < a_mag_m1.m_words.size()) ? a_mag_m1.m_words[i] : 0;
            uint64_t wb = (i < b_mag_m1.m_words.size()) ? b_mag_m1.m_words[i] : 0;
            count += static_cast<size_t>(std::popcount(wa ^ wb));
        }
        return count;
    }

    // ストリーム出力
    std::ostream& operator<<(std::ostream& os, const Int& value) {
        os << value.toString();
        return os;
    }

    // ストリーム入力
    std::istream& operator>>(std::istream& is, Int& value) {
        std::string str;
        is >> str;
        value = Int(str);
        return is;
    }

    // ビットカウント関数
    size_t Int::countLeadingZeros() const {
        if (isZero() || isNaN() || isInfinite()) {
            return 64;
        }
        if (m_words.empty()) {
            return 64;
        }
        // 最上位ワードのゼロビット数
        uint64_t msw = m_words.back();

        // C++20の関数を使用
#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
        size_t zeros = std::countl_zero(msw);
#else
    // 古いコンパイラ向けのフォールバック
        size_t zeros = 0;
        for (int i = 63; i >= 0; --i) {
            if ((msw & (1ULL << i)) == 0) {
                zeros++;
            }
            else {
                break;
            }
        }
#endif

        // 最上位ワードの未使用ビット + 下位ワードの全ビット
        return zeros + static_cast<size_t>(64 * (m_words.size() - 1));
    }

    size_t Int::countTrailingZeros() const {
        if (isZero() || isNaN() || isInfinite()) {
            return 64;  // 特殊ケースは変更なし
        }

        if (m_words.empty()) {
            return 64;  // 空の場合も変更なし
        }

        // 最下位ワードから順に調べる
        for (size_t i = 0; i < m_words.size(); ++i) {
            if (m_words[i] != 0) {
                uint64_t word = m_words[i];

                // C++20の関数を使用
#if defined(__cpp_lib_bitops) && __cpp_lib_bitops >= 201907L
                return std::countr_zero(word) + i * 64;
#else
            // 古いコンパイラ向けのフォールバック - 修正版
                size_t zeros = 0;
                for (size_t j = 0; j < 64; ++j) {
                    if ((word & (1ULL << j)) == 0) {
                        zeros++;
                    }
                    else {
                        // 最初に1のビットが見つかったら終了
                        return zeros + i * 64;
                    }
                }
                // このワードが全て0の場合（通常はここには到達しないはず）
                return 64 + i * 64;
#endif
            }
        }

        // 全てのワードが0の場合
        return 64 * m_words.size();
    }

    size_t Int::popcount() const {
        if (isSpecialState()) return SIZE_MAX;
        if (m_sign < 0) return SIZE_MAX;  // 負数: 2の補数で無限個の 1
        if (m_sign == 0) return 0;

        size_t count = 0;
        for (size_t i = 0; i < m_words.size(); ++i) {
            count += static_cast<size_t>(std::popcount(m_words[i]));
        }
        return count;
    }

    // 内部使用の絶対値比較関数
    int Int::compareAbsoluteValues(const Int& lhs, const Int& rhs) {
        // ワード数での比較
        if (lhs.m_words.size() < rhs.m_words.size()) {
            return -1;
        }
        if (lhs.m_words.size() > rhs.m_words.size()) {
            return 1;
        }

        // 同じワード数の場合、上位ワードから比較
        for (size_t i = lhs.m_words.size(); i-- > 0; ) {
            if (lhs.m_words[i] < rhs.m_words[i]) {
                return -1;
            }
            if (lhs.m_words[i] > rhs.m_words[i]) {
                return 1;
            }
        }

        // 全て等しい場合
        return 0;
    }

    // 単項マイナス演算子
    // operator-() の特殊状態パス (NaN/Infinity)
    // インライン版から呼ばれるスローパス
    Int Int::negate_slow() const {
        if (isNaN()) return *this;
        if (m_state == NumericState::PositiveInfinity) return NegativeInfinity();
        if (m_state == NumericState::NegativeInfinity) return PositiveInfinity();
        // ここには到達しないはず
        return *this;
    }

    // 左シフト代入演算子
    Int& Int::operator<<=(int shift) {
        // 特殊状態の処理
        if (isNaN() || isInfinite() || isZero()) {
            return *this;
        }

        // 負のシフトは右シフトとして処理
        if (shift < 0) {
            return (*this >>= -shift);
        }

        // ゼロシフトは何もしない
        if (shift == 0) {
            return *this;
        }

        // ワード境界を超えるシフト
        size_t word_shift = shift / 64;
        int bit_shift = shift % 64;

        // 準備としてサイズを拡張
        size_t old_size = m_words.size();
        if (bit_shift != 0 && (m_words.empty() || m_words.back() >> (64 - bit_shift) != 0)) {
            // ビットシフトで追加ワードが必要な場合
            m_words.resize(old_size + word_shift + 1);
        }
        else {
            // それ以外の場合
            m_words.resize(old_size + word_shift);
        }

        // ワード境界シフト
        if (word_shift > 0) {
            // 上位ワードから処理することで、データの上書きを防ぐ
            for (size_t i = old_size; i-- > 0; ) {
                m_words[i + word_shift] = m_words[i];
            }
            // 下位ワードをゼロクリア
            for (size_t i = 0; i < word_shift; ++i) {
                m_words[i] = 0;
            }
        }

        // ビット単位のシフト
        if (bit_shift > 0) {
            // 最後のワードから処理
            uint64_t carry = 0;
            for (size_t i = word_shift; i < m_words.size(); ++i) {
                uint64_t new_carry = m_words[i] >> (64 - bit_shift);
                m_words[i] = (m_words[i] << bit_shift) | carry;
                carry = new_carry;
            }
        }

        // 正規化（不要な先頭のゼロを削除）
        normalize();
        return *this;
    }

    // 右シフト代入演算子
    Int& Int::operator>>=(int shift) {
        // 特殊状態の処理
        if (isNaN() || isInfinite() || isZero()) {
            return *this;
        }

        // 負のシフトは左シフトとして処理
        if (shift < 0) {
            return (*this <<= -shift);
        }

        // ゼロシフトは何もしない
        if (shift == 0) {
            return *this;
        }

        // ワード境界を超えるシフト
        size_t word_shift = shift / 64;
        if (word_shift >= m_words.size()) {
            // 全てのビットがシフトアウトされる
            m_words.clear();
            m_sign = 0;
            return *this;
        }

        // ワード内のビットシフト
        int bit_shift = shift % 64;
        if (bit_shift == 0) {
            // ワード単位のシフトのみ
            m_words.erase(m_words.begin(), m_words.begin() + word_shift);
        }
        else {
            // ワード単位 + ビット単位のシフト
            for (size_t i = 0; i < m_words.size() - word_shift; ++i) {
                m_words[i] = (i + word_shift < m_words.size()) ?
                    ((m_words[i + word_shift] >> bit_shift) |
                        ((i + word_shift + 1 < m_words.size()) ? (m_words[i + word_shift + 1] << (64 - bit_shift)) : 0)) : 0;
            }
            m_words.resize(m_words.size() - word_shift);
        }

        // ゼロか確認
        normalize();
        return *this;
    }

    Int& Int::operator+=(const Int& other) {
        if (isSpecialState() || other.isSpecialState()) {
            *this = IntSpecialStates::handleAddition(*this, other);
            return *this;
        }
        if (other.getSign() == 0) return *this;
        if (getSign() == 0) { *this = other; return *this; }

        if (m_sign == other.m_sign) {
            IntOps::addAbsolute(*this, other);
        } else {
            if (IntOps::compareAbsLess(*this, other)) {
                Int result;
                IntOps::subtractAbsolute(other, *this, result);
                result.setSign(other.m_sign);
                *this = std::move(result);
            } else {
                IntOps::subtractAbsoluteInPlace(*this, other);
            }
        }
        return *this;
    }

    Int& Int::operator-=(const Int& other) {
        if (isSpecialState() || other.isSpecialState()) {
            *this = IntSpecialStates::handleSubtraction(*this, other);
            return *this;
        }
        if (other.getSign() == 0) return *this;
        if (getSign() == 0) {
            *this = other;
            if (m_sign != 0) m_sign = -m_sign;
            return *this;
        }

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

    Int& Int::operator*=(const Int& other) {
        *this = *this * other;
        return *this;
    }

    Int& Int::operator/=(const Int& other) {
        *this = *this / other;
        return *this;
    }

    Int& Int::operator%=(const Int& other) {
        *this = *this % other;
        return *this;
    }

    Int& Int::operator&=(const Int& other) {
        *this = *this & other;
        return *this;
    }

    Int& Int::operator|=(const Int& other) {
        *this = *this | other;
        return *this;
    }

    Int& Int::operator^=(const Int& other) {
        *this = pow(*this, other);
        return *this;
    }

    // setState実装
    void Int::setState(NumericState state, NumericError error) {
        m_state = state;
        m_error = error;

        // 特殊状態の場合のみ符号を上書き (Normal パスでは分岐なし)
        if (state != NumericState::Normal) [[unlikely]] {
            if (state == NumericState::NaN) {
                m_sign = 0;
            }
            else if (state == NumericState::PositiveInfinity) {
                m_sign = 1;
            }
            else if (state == NumericState::NegativeInfinity) {
                m_sign = -1;
            }
        }
    }

    // 特殊状態のファクトリメソッド（NaNなど）
    Int Int::NaN() {
        Int result;
        result.m_state = NumericState::NaN;
        result.m_error = NumericError::ExplicitNaN;
        return result;
    }

    Int Int::PositiveInfinity() {
        Int result;
        result.m_state = NumericState::PositiveInfinity;
        result.m_sign = 1;
        return result;
    }

    Int Int::NegativeInfinity() {
        Int result;
        result.m_state = NumericState::NegativeInfinity;
        result.m_sign = -1;
        return result;
    }

    // 内部メソッド
    void Int::setNaN(NumericError error) {
        m_state = NumericState::NaN;
        m_error = error;
        m_sign = 0; // NaNの符号は通常ゼロとして扱う
    }

    // digitCount の実装
    size_t Int::digitCount(int base) const {
        // 基数の検証
        if (base < 2 || base > 36) {
            return 0;  // 無効な基数
        }
        // 特殊状態の場合
        if (isSpecialState()) return 0;
        // 0 の場合は桁数 1
        if (isZero()) return 1;

        // 絶対値を取る
        Int abs_val = abs(*this);

        // 2 の累乗の基数の場合は最適化
        if (base == 2) {
            return abs_val.bitLength();
        } else if (base == 16) {
            return (abs_val.bitLength() + 3) / 4;  // 4ビット = 1桁
        } else if (base == 8) {
            return (abs_val.bitLength() + 2) / 3;  // 3ビット ≈ 1桁
        }

        // 一般の基数: 文字列変換して桁数を数える
        std::string str = abs_val.toString(base);
        return str.length();
    }

    // sizeInBase の実装 (GMP mpz_sizeinbase 互換)
    size_t Int::sizeInBase(int base) const {
        // 基数の検証
        if (base < 2 || base > 62) return 0;
        // 特殊状態の場合
        if (isSpecialState()) return 0;
        // 0 の場合は桁数 1
        if (isZero()) return 1;

        size_t bits = bitLength();

        // 2のべき乗基数の場合: 正確な結果
        if ((base & (base - 1)) == 0) {
            int bits_per_digit = 0;
            int b = base;
            while (b > 1) { b >>= 1; bits_per_digit++; }
            return (bits + bits_per_digit - 1) / bits_per_digit;
        }

        // 一般の基数: double 精度対数による推定
        // 結果は正確または 1 大きい (GMP と同じセマンティクス)
        double log_base = std::log(static_cast<double>(base));
        size_t result = static_cast<size_t>(bits * std::log(2.0) / log_base) + 1;
        return result;
    }

    // ilog2 の実装
    size_t Int::ilog2() const {
        // 特殊状態・ゼロ・負の場合は 0
        if (isSpecialState() || !isPositive()) return 0;
        // floor(log2(n)) = bitLength - 1
        return bitLength() - 1;
    }

    // ilog10 の実装
    size_t Int::ilog10() const {
        // 特殊状態・ゼロ・負の場合は 0
        if (isSpecialState() || !isPositive()) return 0;
        // digitCount(10) は正確な10進桁数を返す
        // floor(log10(n)) = digitCount - 1
        return digitCount(10) - 1;
    }

    // isDivisible の実装
    bool Int::isDivisible(const Int& divisor) const {
        // 特殊状態の処理
        if (isSpecialState() || divisor.isSpecialState()) return false;
        // 0 で割る判定は意味がない
        if (divisor.isZero()) return false;
        // 0 は任意の数で割り切れる
        if (isZero()) return true;
        // this % divisor == 0 で判定
        return (*this % divisor).isZero();
    }

    // isCongruent の実装
    bool Int::isCongruent(const Int& other, const Int& modulus) const {
        // 特殊状態の処理
        if (isSpecialState() || other.isSpecialState() || modulus.isSpecialState()) return false;
        // modulus が 0 なら判定不可
        if (modulus.isZero()) return false;
        // (this - other) % modulus == 0 で判定
        return (*this - other).isDivisible(modulus);
    }

} // namespace calx