C ++ умножение 2 строк, представляющих десятичное значение числа - PullRequest
Новая
       16

C ++ умножение 2 строк, представляющих десятичное значение числа

0 голосов
/ 03 апреля 2011

Идея состоит в том, чтобы перегрузить operator *, чтобы он мог умножить две строки, представляющие десятичное значение числа. Оператор является частью большего класса, но это не важно. Алгоритм такой же, как в начальной школе:)

Вот мой код: 

Bignumber operator* (Bignumber x, Bignumber y ){
    int i, j, transfer=0, tmp, s1, s2, k;
    char add[1];
    string sol;
    string a, b;
    Bignumber v1, v2;
    a=x.GetValue();
    b=y.GetValue();

    a.insert(0,"0");
    b.insert(0,"0");

    for(i=a.length()-1; i>=0; i--){
        s1 = (int) a[i]-48;
        for(k=a.length()-i-1; k >0 ; k--){
            sol+="0";
        }
        for(j=b.length()-1; j >=0; j--){
            s2=(int) b[j]-48;
            tmp=s1*s2+transfer;
            if(tmp >= 10){
                 transfer=tmp/10;
                 tmp=tmp-(10*transfer);
             }
            itoa(tmp, add, 10);
            sol.insert(0, add);
        }
        v1=sol;
        v2=v1+v2;
        sol.erase(0);
        transfer=0;
    }
    return v2;
}

Это работает нормально в большинстве случаев, но для некоторых случайных значений это не работает должным образом. как например для 128 * 28 он возвращает 4854 вместо 3584.

Есть идеи, в чем может быть проблема?

operator s + и = уже перегружены для класса Bignumber и работают нормально.

Ответы [ 2 ]

3 голосов
/ 03 апреля 2011

Хотя мой первый ответ решит вашу проблему (в любом случае, по моим тестам), здесь есть альтернативная реализация;У меня нет вашего Bignumber класса, поэтому я написал небольшой поддельный класс для проверки: 

#include <string>
#include <ios>
#include <iostream>
#include <ostream>
#include <sstream>

class Bignumber
{
    static inline unsigned long long strtoull(std::string const& str)
    {
        unsigned long long val;
        return std::istringstream(str) >> val ? val : 0uLL;
    }

    unsigned long long val_;

public:
    Bignumber() : val_() { }
    explicit Bignumber(unsigned long long const val) : val_(val) { }
    explicit Bignumber(std::string const& str) : val_(strtoull(str)) { }

    Bignumber& operator +=(Bignumber const rhs)
    {
        val_ += rhs.val_;
        return *this;
    }

    std::string GetValue() const
    {
        std::ostringstream oss;
        oss << val_;
        return oss.str();
    }
};

Bignumber operator *(Bignumber const x, Bignumber const y)
{
    typedef std::string::const_reverse_iterator cr_iter_t;

    std::string const& a = '0' + x.GetValue();
    std::string const& b = '0' + y.GetValue();

    Bignumber ret;
    for (cr_iter_t a_iter = a.rbegin(), a_iter_end = a.rend(); a_iter != a_iter_end; ++a_iter)
    {
        unsigned transfer = 0u;
        std::string sol(a.end() - a_iter.base(), '0');
        for (cr_iter_t b_iter = b.rbegin(), b_iter_end = b.rend(); b_iter != b_iter_end; ++b_iter)
        {
            unsigned tmp = static_cast<unsigned>(*a_iter - '0') * static_cast<unsigned>(*b_iter - '0') + transfer;
            if (tmp >= 10u)
            {
                transfer = tmp / 10u;
                tmp -= transfer * 10u;
            }
            sol.insert(sol.begin(), static_cast<char>(tmp + '0'));
        }
        ret += Bignumber(sol);
    }
    return ret;
}

int main()
{
    Bignumber const z = Bignumber(123456789uLL) * Bignumber(987654321uLL);
    std::cout << std::boolalpha << (z.GetValue() == "121932631112635269") << std::endl;
}
1 голос
/ 03 апреля 2011

itoa завершает нулевую строку, которую записывает, поэтому add слишком мал для записи в него данных, что приводит к повреждению памяти.Измените определение add на char add[2];, и оно должно работать.

...