Hỏi về cộng 2 số nguyên lớn và bigint

nguyenhieuckt · December 21, 2018, 2:50am

Em đang làm bài toán cộng 2 số nguyên lớn thì đọc trên mạng thấy dùng bigint và cách này rất ngắn. Ai giải thích hộ em bigint với code dùm 1 đoạn để e hiểu được không ạ ?

rogp10 · December 21, 2018, 1:39am

Cộng bằng tay thôi mà

Dùng hex (cơ số 16) luôn vậy. Đặt tính: 0x2E8 + 0x4A79
i = 0: 8 + 9 + carry = 17, 17 - 16 = 1 viết 1 nhớ 1
i = 1: 0xE + 0x7 + carry = 22, 22 - 16 = 6, viết 6 nhớ 1
…
i = 3, 4 + carry = 4 viết 4.

Kết quả là 0x4D61.

noz1995 · December 21, 2018, 1:36am

Sử dụng kiểu dữ liệu int - long…
Ưu điểm là tính nhanh, nhược điểm là kích thước của chuỗi bit phải cố định và bằng 2^n

BigInt bản chất là string
Tính BigInt thì như con người theo cách bạn @rogp10 đưa ra nên muốn tính to bao nhiêu cũng được, chừng nào máy vẫn còn RAM và CPU

rogp10 · December 21, 2018, 1:41am

Và cơ số có thể lấy luôn là 2^32

string chỉ dùng để hiển thị thôi bên trong vẫn có thể dùng uint32_t bt…

vanhieu · December 21, 2018, 2:30am

Bạn có ther dùng mảng(vector chẳng hạn) hoặc string. Mỗi phần tử sẽ là 1 chữ số. Lấy thêm một biến nữa để lưu dấu của nó. Vote dùng vector để không phải convert mỗi khi tính
Chẳng hạn thế này:

struct BigInt{
    int sign;
    vector<int> val;
}

Như vậy, với phép cộng, trừ thì đơn giản rồi. Nhớ check dấu và xử lý trường hợp 2 số không bằng nhau là được.

Nếu dùng Java hay các ngôn ngữ bậc cao khác thì có thư viện BigInt rồi

Một số code BigInt mình search cho bạn:

github.com

maemual/BigInt/blob/master/BigInt.cpp

#include"BigInt.h"
#include<vector>
#include<string.h>

BigInt BigInt::ZERO = BigInt(0);
BigInt BigInt::ONE  = BigInt(1);
BigInt BigInt::TWO  = BigInt(2);
BigInt BigInt::TEN  = BigInt(10);

BigInt::BigInt(){
    vec.clear();
    sign_ = true;
}

BigInt::BigInt(int i_val){
    vec.clear();
    if (i_val >= 0)
        sign_ = true;
    else{
        sign_ = false;

This file has been truncated. show original

https://codeforces.com/blog/entry/16380

github.com

panks/BigInteger/blob/master/BigIntegerSingleFile.cpp

/*
 * @author panks
 * Big Integer library in C++, single file implementation.
 */
#include <iostream>
#include <string>
#include <sstream>
#include <cmath>
#define MAX 10000 // for strings

using namespace std;
class BigInteger {
private:
    string number;
    bool sign;
public:
    BigInteger(); // empty constructor initializes zero
    BigInteger(string s); // "string" constructor
    BigInteger(string s, bool sin); // "string" constructor
    BigInteger(int n); // "int" constructor

This file has been truncated. show original

Mình có chia sẻ 1 solution giải quyết số nguyên lớn ở đây. Code này thì khá là tối ưu, nhưng bù lại để hiểu nó cũng tốn thời gian đấy

tntxtnt · December 21, 2018, 3:40am

C++ bigint thì GMP hoặc MPIR trên Windows thẳng tiến, nhưng mà chủ thớt chắc ko cần tới mấy thứ này :V

nên xài kèm với Boost.Multiprecision cho thân thiện. Muốn thử thì vào https://wandbox.org/ thêm compiler options -lgmp vào nữa là được.

Ví dụ tìm số Fibonacci thứ 10000:

#include <boost/multiprecision/gmp.hpp>
#include <iostream>

using BigInt = boost::multiprecision::mpz_int;

int main()
{
    BigInt a = 0;
    BigInt b = 1;
    for (int k = 2; k < 10000; ++k)
    {
        BigInt c = a + b;
        a = b;
        b = c;
    }
    std::cout << b << "\n";
}

xài y hệt int bình thường :V