Xử lý số lớn bằng C++ hướng đối tượng

#1

Hôm nay rảnh ngồi làm chương trình tính số lớn:

#include<iostream>
#include<conio.h>
using namespace std;

class NumberXL {
private:
    char numberXL[200];         //sâu ký tự
    bool sign;                  //dấu, true=dương, false=âm
    int len;                    //độ dài của số
public:
    friend istream& operator>>(istream& in, NumberXL& numberXL);
    friend ostream& operator<<(ostream& out, NumberXL& numberXL);
    friend void BackWardsNumberXL(NumberXL& numberXL);
    NumberXL operator+(NumberXL numberXL2);
};

void BackWardsNumberXL(NumberXL& numberXL) {
    int len = numberXL.len;
    for (int i = 0; i <= (len - 1) / 2; i++) {
        char temp = numberXL.numberXL[i];
        numberXL.numberXL[i] = numberXL.numberXL[len - 1 - i];
        numberXL.numberXL[len - 1 - i] = temp;
    }
}

istream& operator>>(istream& in, NumberXL& numberXL) {
    char temp;
    int i = 0;

    //xét ký tự đầu tiêm, ,
    do {
        temp = _getch();
    } while ((temp < '0' || temp > '9') && temp != '-' && temp != '+');
//nếu là '-'(số âm) thì numberXL.sign=false
    if (temp == '-') {
        numberXL.sign = false;
        cout << temp;
    }
//nếu là '+'(số dương) thì numberXL.sign=true
    else if (temp == '+') {
        numberXL.sign = true;
        cout << temp;
    }
//nếu ký tự đầu tiên không phải '+' hoặc '-' -> số dương numberXL.sign = true
//gán numberXL.sign = true
//gán ký tự đầu tiên bằng số vừa nhập
    else {
        numberXL.sign = true;
        cout << temp;
        numberXL.numberXL[i++] = temp;
    }

//nhập số
    do {
        do {
            temp = _getch();
        } while ((temp < '0' || temp > '9') && temp != 13);
        cout << temp;
        if (temp == 13) {
            temp = '\0';
        }
        numberXL.numberXL[i] = temp;
    } while (numberXL.numberXL[i++] != '\0');

//độ dài của số
    numberXL.len = strlen(numberXL.numberXL);

    cout << endl;
    return in;
}

ostream& operator<<(ostream& out, NumberXL& numberXL) {
    int len = numberXL.len;

    //nếu số âm thì in ra ký tư '-'
    if (!numberXL.sign) {
        out << "-";
    }

//in số
    for (int i = 0; i < len; i++) {
        out << numberXL.numberXL[i];
    }

    return out;
}

NumberXL NumberXL::operator + (NumberXL numberXL2) {
    NumberXL countXL;
    int len_number1, len_number2, lenMIN, lenMAX;
    char nho = '0';

    //xét dấu của countXL.sign
//nếu cả 2 số cùng mang dâu dương thì tổng cũng mang dấu dương -> countXL.sign = true
    if (this->sign == true && numberXL2.sign == true)
        countXL.sign = true;
//nếu cả 2 số cùng mang dấu âm thì tổng cũng mang dấu âm -> countXL.sign = false
    else if (this->sign == false && numberXL2.sign == false)
        countXL.sign = false;
////số thứ nhất âm và số thứ hai dương -a+b=b-a
//else if (this->sign == true && numberXL2.sign == false)
//  return numberXL2 - *this;

//lấy độ dài 2
//lưu trong len_number1, len_number2
    len_number1 = this->len;
    len_number2 = numberXL2.len;

//tìm độ dài
    lenMIN = len_number1<len_number2 ? len_number1 : len_number2;
    lenMAX = len_number1>len_number2 ? len_number1 : len_number2;

//đảo ngược hai xâu
    BackWardsNumberXL(*this);
    BackWardsNumberXL(numberXL2);

//tính tổng
//vị trí không lệch
    for (int i = 0; i < lenMIN; i++) {
        countXL.numberXL[i] = (this->numberXL[i] + numberXL2.numberXL[i] + nho - 3 * 48) % 10 + 48;
        nho = (this->numberXL[i] + numberXL2.numberXL[i] + nho - 3 * 48) / 10 + 48;
    }

//vị trí lệch
    if (len_number1 > len_number2) {
        for (int i = len_number2; i < len_number1; i++) {
            countXL.numberXL[i] = (this->numberXL[i] + nho - 2 * 48) % 10 + 48;
            nho = (this->numberXL[i] + nho - 2 * 48) / 10 + 48;
        }
    } else {
        for (int i = len_number1; i < len_number2; i++) {
            countXL.numberXL[i] = (numberXL2.numberXL[i] + nho - 2 * 48) % 10 + 48;
            nho = (numberXL2.numberXL[i] + nho - 2 * 48) / 10 + 48;
        }
    }

//nếu sau tính tổng mà biến nho != '0' thì nho được lưu vào cuối xâu
    if (nho != '0') {
        countXL.numberXL[lenMAX] = nho;

        //chèn ký tự kết thúc xâu
        countXL.numberXL[lenMAX + 1] = '\0';

        //độ đai của countXL
        countXL.len = lenMAX + 1;
    } else {
        //chèn ký tự kết thúc xâu
        countXL.numberXL[lenMAX] = '\0';

        //độ đai của countXL
        countXL.len = lenMAX;
    }

//đảo ngược lại xâu rồi return
    BackWardsNumberXL(*this);
    BackWardsNumberXL(numberXL2);
    BackWardsNumberXL(countXL);
    return countXL;
}

void main() {
    NumberXL a, b;
    cout << "nhap so thu 1: ";
    cin >> a;
    cout << "nhap so thu 2: ";
    cin >> b;
    cout << a << "+" << b << "=" << a + b;
}

http://codepad.org/vQvbB6ZO
Chưa làm:

  • chưa tính được -a+b=b-a, a+(-b) (ít thời gian quá nên chưa định nghĩa phép trừ)
  • không backspace khi nhập số

Đã làm:

  • tính được -a+(-b)=-(a+b)

PS:- code tào lao mong mọi người góp ý

P/S2: Post dùm LaCry TYar

4 Likes
#2

File BigInt.h

#pragma once
#include <iostream>
#include <string>

using namespace std;

class BigInt
{
public:
    BigInt(int n = 0);
    BigInt(string);
    BigInt& operator=(const BigInt &x);
    friend ostream& operator<<(ostream &os, BigInt &x);
    BigInt& operator++();
    BigInt operator++(int);
    BigInt& operator--();
    BigInt operator--(int);
    BigInt operator+=(BigInt &s);
    BigInt operator + (const BigInt &s);
    BigInt operator - (BigInt &s);
    bool operator == (BigInt &s);
    bool operator != (BigInt &s);
    bool operator > (BigInt &s);
    bool operator < (BigInt &s);
    bool operator >= (BigInt &s);
    BigInt operator~();
    friend BigInt abs(BigInt x);
    inline int getBit(int pos) const;
    inline void setBit(int pos);
    string toString();
    string squareString(int);
    string addString(string, string);
    string StringDiv2(string);

private:
    int data[8];
}

File BigInt.cpp

#include "BigInt.h"

BigInt::BigInt(int x)
{
    // Khoi tao cac bit 0
    for (int i = 0; i < 8; ++i)
        this->data[i] = 0;

    // Chuyen int --> BigInt
    this->data[7] = abs(x);

    // Neu x < 0 thi chuyen sang bu 2
    if (x < 0)
        *this = (~(*this)) + 1;

}

BigInt::BigInt(string x)
{
    int isNegative = 0; // Kiem tra so am
    if (x[0] == '-')
    {
        isNegative = 1;
        x.erase(0, 1);
    }
    // Xoa so 0 thua dau so
    int i = 0;
    while (x[i] == '0' && x.length() > 1) i++;
    x.erase(0, i);
    i = 255;

    // Chuyen decimal sang binary
    *this = 0;
    while (x != "0")
    {
        int du = (x[x.length() - 1] - 48) % 2;
        if (du == 1)
        {
            this->setBit(i);
        }
        x = StringDiv2(x);
        i--;
    }

    //Doi sang so bu 2 neu la so am
    if (isNegative == 1)
        *this = ~(*this) + 1;
}

ostream& operator<<(ostream &os, BigInt &x)
{
    os << x.toString();
    return os;
}

BigInt BigInt::operator+=(BigInt &s)
{
    return *this + s;
}

BigInt& BigInt::operator=(const BigInt &x)
{
    if (this == &x) return *this;
    for (int i = 0; i < 8; i++)
        this->data[i] = x.data[i];
    return *this;
}

BigInt BigInt::operator+(const BigInt &s)
{
    BigInt res;
    int carry = 0;
    unsigned int bit, sbit;
    for (int i = 255; i > 0; i--)
    {
        bit = this->getBit(i);
        sbit = s.getBit(i);
        switch (bit + sbit + carry)
        {
        case 3:
            carry = 1;
            res.setBit(i);
            break;
        case 2:
            carry = 1;
            break;
        case 1:
            res.setBit(i);
            carry = 0;
            break;
        }
    }
    return res;
}

BigInt BigInt::operator-(BigInt &s)
{
    BigInt t;
    t = *this + 1 + (~s);
    return t;
}

bool BigInt::operator==(BigInt &s)
{
    for (int i = 7; i > 0; i--)
        if (this->data[i] != s.data[i])
            return false;
    return true;
}

bool BigInt::operator!=(BigInt &s)
{
    return !(*this == s);
}

bool BigInt::operator>=(BigInt &x)
{
    BigInt t = *this - x;
    if ((1 << 31 & t.data[3]) == 0)
        return true;
    return false;
}

bool BigInt::operator<(BigInt &x)
{
    return !((*this) >= x);
}

bool BigInt::operator>(BigInt &x)
{
    return (x < (*this));
}

BigInt BigInt::operator~()
{
    BigInt t = *this;
    for (int i = 0; i < 8; ++i)
        t.data[i] = ~t.data[i];
    return t;
}

BigInt abs(BigInt x)
{
    if (x < BigInt(0))
        x = (~x) + 1;
    return x;
}

int BigInt::getBit(int pos) const
{
    //int bit = this->data[pos / 32] & (1 << (31 - pos % 32));
    //return bit >> (pos % 32);
    return ((data[pos / 32]) >> (31 - pos % 32)) & 1;
}

void BigInt::setBit(int pos)
{
    this->data[pos / 32] ^= 1 << (31 - pos % 32); // ^=
}

string BigInt::toString()
{
    string result = "0";
    BigInt temp = abs(*this);
    for (int i = 255; i > 0; i--)
    {
        int bit = temp.getBit(i);
        if (bit == 1)
        {
            string t = temp.squareString(255 - i);
            result = temp.addString(result, t);
        }
    }
    if ((*this) < BigInt(0))
        result.insert(0, "-");

    return result;
}

string BigInt::squareString(int n)
{
    string result = "1";
    if (n == 0)
        return "1";
    for (int i = 0; i < n; i++)
    {
        result = addString(result, result);
    }
    return result;
}

string BigInt::addString(string a, string b)
{
    int alen = a.length();
    int blen = b.length();
    if (blen > alen)
    {
        string t = a;
        a = b;
        b = t;
        int tmp = alen;
        alen = blen;
        blen = tmp;
    }
    char *c = new char[alen];
    int carry = 0;//Bien nho khi cong vao lon hon 10.
    for (int i = alen - 1; i >= 0; i--)
    {
        int dva = a[i] - 48;
        int j = i - (alen - blen);
        int dvb;
        if (j < 0) dvb = 0;
        else dvb = b[j] - 48;

        int s = dva + dvb + carry;
        if (s >= 10)
        {
            c[i] = s % 10 + 48;
            carry = 1;
        }
        else
        {
            c[i] = s + 48;
            carry = 0;
        }
    }
    if (carry == 1)
    {
        char *kq = new char[alen + 1];
        kq[0] = '1';
        for (int i = 0; i < alen; i++)
        {
            kq[i + 1] = c[i];
        }
        string rs(kq, alen + 1);
        return rs;
    }
    else
    {
        string rs(c, alen);
        return rs;
    }
}

string BigInt::StringDiv2(string str) //Ham chia 2
{
    string temp;
    unsigned short int i = 0, j = 0, k = 0;
    if (str == "1")
        return "0";
    temp.resize(str.length());
    if (str[0] - 48 < 2)
    {
        i = 1;
        j = 10;
    }
    for (; i < str.length(); i++)
    {
        temp[k++] = ((str[i] - 48 + j) / 2 + 48);
        j = ((str[i] - 48 + j) % 2) * 10;
    }
    temp.resize(k);
    return temp;
}

BigInt& BigInt::operator++()
{
    *this = *this + 1;
    return *this;
}

BigInt BigInt::operator++(int)
{
    BigInt temp = *this;
    ++*this;
    return temp;
}

BigInt& BigInt::operator--()
{
    *this = *this + -1;
    return *this;
}

BigInt BigInt::operator--(int)
{
    BigInt temp = *this;
    --*this;
    return temp;
}
2 Likes
#3

Mình đã move bài này lên trên để cho dễ nhìn hơn

–Đạt

#4

Rất hay, các bạn hãy tập làm quen với việc xử lý số lớn, đây không phải là một vấn đề quá khó, nhưng nó giúp ta hiểu được giới hạn của kiểu int là không thể tính toán trên số rất lớn. Và vì vậy chúng ta cần phải sử dụng các “thủ thuật” để thực hiện được trên giới hạn có sẵn.

1 Like
#5

I moved a post to a new topic: This-> trong C++ có ý nghĩa gì?

#6

Vì code của @Gio là C nên Đạt đã di chuyển sang phần xử lý số lớn dùng C
I moved 3 posts to an existing topic: Xử lý số lớn - part1

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?