求实现大整数基本运算的类模版？

sjtwenzhou

关于这个大整数(比如long long)的基本运算等相关问题，我也看了不少帖子，存储方式不一样，实现思路也不尽相同。我想能不能把这些基本运算编成一个类模版，希望大家提供一些金典的算法或者好的实现思路！
    其中基本运算包括，加，减，乘，除，模，乘方，输出等；存储方式比如，数组，链表等均可。

superandy

除法不好实现。

珈蓝易拉罐

大整数，作成一个类不更好吗？
模板范化啥东西呢？

zfy010317

怎么输出成字符串?都不好办:(

sjtwenzhou

楼上说的对，应该是做成一个类，我上面写的可能有点让人误解，其实就是想把这些功能封装成一个类，呵呵，谢谢你的修正！

sjtwenzhou

怎么输出成字符串?都不好办:(
------------------------------------------------
输出就这样实现，下面这个可以是类成员函数，当然我们也可以写个<< 重载函数，希望可以抛砖引玉，呵呵，
void print_bigint(long long n)  
{  
        if (n>=10)  
                print_bigint(n/10);  
        printf("%d",int(n%10));  
}

superandy

给你一个只支持*=(int)的
class BigInt
{
    typedef unsigned long              FUNDUS_T;
    typedef unsigned long long int     ACCUMULATE_T;
    typedef vector<FUNDUS_T>           CONTAINER_T;
    enum {FUNDUS = 1000000000};
    enum {FUNDUS_LEN = numeric_limits<FUNDUS_T>::digits10};

public:
    BigInt(FUNDUS_T x = 0)
    {
        c.reserve(65535);
        do
        {
            c.push_back(x % FUNDUS);
            x /= FUNDUS;   
        } while (x != 0);
    }

public:   
    BigInt & operator*=(FUNDUS_T x)
    {
        ACCUMULATE_T carry = 0;
        for (CONTAINER_T::iterator i = c.begin(); i != c.end(); ++i)
        {
            carry = ACCUMULATE_T(*i) * x + carry;
            *i = carry % FUNDUS;
            carry /= FUNDUS;  
        }

        if (carry != 0)
        {
            c.push_back(carry);
        }        
        
        return *this;
    }

public:   
    template <typename OSTREAM_T>
        friend OSTREAM_T & operator<<(OSTREAM_T &, const BigInt &);

private:   
    CONTAINER_T c;  
};

    template<typename OSTREAM_T>
        OSTREAM_T & operator<<(OSTREAM_T & os, const BigInt & x)
    {
        BigInt::CONTAINER_T::const_reverse_iterator iter = x.c.rbegin();
        os << *iter;
        ++iter;
        while (iter != x.c.rend())
        {
            os << setw(BigInt::FUNDUS_LEN) << setfill('0') << *iter;
            ++iter;
        }

        return os;
    }

zfy010317

输出就这样实现，下面这个可以是类成员函数，当然我们也可以写个<< 重载函数，希望可以抛砖引玉，呵呵，
void print_bigint(long long n)
{
if (n>=10)
print_bigint(n/10);
printf("%d",int(n%10));
}
----------------------------------------------------
大数不是一组数,10进制的分组和2进制的分组并不相同.

sjtwenzhou

大数不是一组数,10进制的分组和2进制的分组并不相同.
-----------------------------------
我不是很理解这句话的意思？

谢谢 jixingzhong(瞌睡虫·星辰)  你提供的链接确有，以前曾浏览过，但是没有注意到。

zfy010317

比如 16进制的 0xff00 ,分开 0xff, 0x00 . 分组很自然,合并很直观.
但是10进制,必须将所有的数合并了,才知道每一个数位的情况(但是就是不能将所有的数合并才
分开的,这不就是矛盾了么)
比如:
255, 0  和 65280 没有一点共同性.