C++ 大整数

C++ Big Integer

提问by Andrea

I'm trying to implement a BigInteger Class in C++. But, first of all, I've a base question, how the "base data" can be represented? For example, the most stupid way is to have a fixed (or dynamic) array of char and store each single number of an integer in a char. But, ok, this is a very stupid way, and I'm here for your suggestions.

我正在尝试用 C++ 实现一个 BigInteger 类。但是，首先，我有一个基本问题，“基本数据”如何表示？例如，最愚蠢的方法是拥有一个固定（或动态）的 char 数组并将整数的每个单个数字存储在一个 char 中。但是，好吧，这是一种非常愚蠢的方式，我在这里是为了您的建议。

回答by Tim

There are a bunch of suggestions here for existing implementations: C++ handling very large integers

这里有一些针对现有实现的建议： C++处理非常大的整数

If you have to implement your own (e.g. for homework), then you have to decide the best way, and how "big" you need to handle. You could use an array of DWORDs, and handle overflowing from one to the next.

如果您必须实现自己的（例如家庭作业），那么您必须决定最佳方式，以及您需要处理的“大”。您可以使用一组 DWORD，并处理从一个到下一个溢出。

Although, for some of the Project Euler stuff, I actually implemented a BigNumber class built on a string. It turned out to be the simplest to implement for +-*/, and scaled to significantly longer numbers than I could get with a few unsigned long longs. And the performance was perfectly adequate for solving those puzzles.

虽然，对于一些 Project Euler 的东西，我实际上实现了一个基于字符串的 BigNumber 类。结果证明对于 +-*/ 实现是最简单的，并且扩展到比我用几个unsigned long longs得到的数字要长得多的数字。性能完全足以解决这些难题。

So, you face a tradeoff between ease of implementation and optimal performance. Have fun ;-)

因此，您需要在易于实施和最佳性能之间进行权衡。玩得开心 ;-）

回答by Thanatos

You can create a big integer in exactly the way you describe. In fact, the first time I implemented such a class, that's exactly the way I did it. It helped me implement the arithmetic operations (+, -, etc) since it was in the base (10) that I was used to.

您可以完全按照您描述的方式创建一个大整数。事实上，我第一次实现这样一个类，正是我这样做的方式。它帮助我实现了算术运算（+、-等），因为它在我习惯的基数 (10) 中。

A natural enhancement to your "array of chars" is to keep it in base 10, but use 4 bits for the digit, instead of the whole byte. Thus, the number 123,456 might be represented by the bytes 12 34 56instead of the string 123456. (Three bytes as opposed to six.)

对“字符数组”的自然增强是将其保留在 10 基数中，但使用 4 位作为数字，而不是整个字节。因此，数字 123,456 可能由 bytes12 34 56而不是 string 表示123456。（三个字节而不是六个字节。）

From there, you could make the storage for the number in base two. The basic arithmetic operations such as addition work exactly the same in base 2 as they do in base 10. Thus, the number 65565 could be stored using the bytes FF FF. (In a vector of unsigned chars, for example.) Some implementations of BigInts use larger chunks, such as shortor long, for efficiency.

从那里，您可以为以二为基数的数字进行存储。基本算术运算（例如加法）在基数 2 中的工作方式与在基数 10 中的工作完全相同。因此，可以使用 bytes 存储数字 65565 FF FF。（unsigned char例如，在s的向量中。）BigInts 的一些实现使用更大的块，例如shortor long，以提高效率。

Base-10 big ints can be useful if you're doing a lot of displaying and/or serializing to base-10, and want to avoid the conversion to base-2.

如果您要进行大量显示和/或序列化为 base-10，并且想要避免转换为 base-2，则 Base-10 大整数可能会很有用。

回答by Noam Shaked Cohen

That's my decimal base implementation. string for the value and a bool for the sign (Note: notice that bool = true => the number is negative). pretty much all the basic functions are here tested & ready to use.

那是我的十进制基础实现。值的字符串和符号的布尔值（注意：注意 bool = true => 数字是负数）。几乎所有的基本功能都在这里测试并准备好使用。

Pay Attention:the bitwise operators were implemented a bit (sda-ka-dish) differently, all explained in the getBinary()function.

注意：按位运算符的实现方式略有不同（sda-ka-dish），所有这些都在getBinary()函数中进行了解释。

knock yourself out.

把自己打昏。

#include <string>
#ifndef AC1_INFINT_H
#define AC1_INFINT_H


class InfInt {
    std::string value;
    bool sign = 0;
public:


InfInt();
InfInt(const std::string&);
InfInt(long int);
InfInt operator=(long int);
explicit operator int() const;

std::string getValue() const;
bool getSign() const;
InfInt operator+(const InfInt&) const;
InfInt operator-(const InfInt&) const;
InfInt operator*(const InfInt&) const;
InfInt operator/(const InfInt&) const;
InfInt operator%(const InfInt&) const;

bool operator<(const InfInt&) const;
bool operator>(const InfInt&) const;
bool operator<=(const InfInt&) const;
bool operator>=(const InfInt&) const;
bool operator==(const InfInt&) const;
void operator+=(const InfInt&);
void operator-=(const InfInt&);
void operator++();
void operator--();
//void operator++();
//void operator--();


//BitWise
InfInt operator&(const InfInt&) const;
InfInt operator<<(const InfInt&) const;
InfInt operator>>(const InfInt& a) const;
void operator<<=(const InfInt&);
void operator>>=(const InfInt&);
void operator&=(const InfInt&);
InfInt operator^(const InfInt&) const;
InfInt operator|(const InfInt&) const;




unsigned long length() const;
std::string align(const unsigned long) const;
void initFromBinary(const std::string);





private:

std::string getBinary() const;

std::string subtract(const InfInt&) const;
std::string add(const InfInt&) const;
void setSign(const bool);
InfInt alignLeft(const unsigned long) const;

};

std::ostream& operator<<(std::ostream& os, const InfInt&);


#endif //AC1_INFINT_H

and the cpp file (I guess Ctrl + F will do better if you look for a specific operator):

和 cpp 文件（我猜 Ctrl + F 如果您寻找特定的运算符会做得更好）：

//
// Created by NSC on 11/7/18.
//
#include <string.h>
#include <cstring>
#include "LargeIntegers.h"

unsigned long InfInt::length() const{
    if (value == "0")
    return 0;
    return value.length();
}

InfInt::InfInt(){
    value = "0";
}

InfInt::InfInt(const std::string &s) {
    unsigned long start = s.find_first_not_of("0-");

    if (!std::strcmp(&s[start],"")) {
    std::strcpy(&value[0], "0");
    }

    if(s[0] == '-') {
    sign = 1;
    }
    value = &s[start];
}

InfInt::InfInt(long int a) {
    sign =0;
    if (a < 0){
    sign = 1;
    a *= -1;
    }

    value = std::to_string(a);
}

InfInt InfInt::operator=(long int a){
    return *new InfInt(a);
}

std::string InfInt::getValue() const{
    return value;
}

bool InfInt::getSign() const{
    return sign;
}

void InfInt::setSign(const bool s){
    sign = s;
}

InfInt::operator int() const{
    int final = 0 ;
    int pow = 1;
    for (long i = length() - 1 ; i >= 0; i--) {
    final +=  pow * (value[i] - '0');
    pow*= 10;
    }
    if (sign)
    final *= -1;
    return final;
}

std::string InfInt::getBinary() const{
    //if the number is 0
    if (!length())
    return "0";
    InfInt temp = *new InfInt(value);
    //sign at the start and then from lsb to msb
    std::string result = "";
    result = result + (char)((int)sign + '0');
    std::string current;

    while (temp > 0){
    current=  (temp%2).getValue();
    if (current.length() == 0)
        result = result + "0";
    else
        result = result + current;
    temp = temp/2;
    }

    return result;
}

void InfInt::initFromBinary(const std::string b){
    sign = b[0] - '0';
    InfInt temp = 0;
    InfInt shift = 1;
    for (long i=1; i<b.length(); i++){
    temp += *new InfInt((int)(b[i] - '0')) * shift;
    shift = shift * 2;
    }

    value = temp.value;
}

std::ostream& operator<<(std::ostream& os, const InfInt& a){
    if (a.length() == 0 || a.getValue()[0] == '0') {
    std::string zero = "0";
    return os << zero;
    }
    if (a.getSign())
    return os << "-" + a.getValue();
    else
    return os<< a.getValue();
}

std::string InfInt::align(const unsigned long l) const{
    std::string newStr = value;
    for (unsigned long i=0; i<l; i++){
    newStr = "0" + newStr;
    }
    return newStr;
}

InfInt InfInt::alignLeft(const unsigned long l ) const{
    std::string newStr = value;
    for (unsigned long i=0; i<l; i++){
    newStr = newStr + "0";
    }
    return newStr;
}

void InfInt::operator++(){
    *this+=1;
}

void InfInt::operator--(){
    *this= *this - 1;
}

//adding the values of the input w/o their sign
std::string InfInt::add(const InfInt & a) const {
    unsigned long numOfZeros = value.length() - a.length();
    std::string aligned = a.align(numOfZeros);
    //now this and a are in the same length

    std::string result;
    int x = 0;
    bool carry = 0;

    for (long i = value.length() -1; i>=0; i--){
    //according to the ascii table '0' = 0 + 48 so subtracting 48 is a more sufficient way to convert
    x=value[i] + aligned[i] - 96 + carry;
    carry = x/10;
    result = (char)(x%10 + 48) + result;
    }

    //in case of "overflow"
    if (carry)
    result = "1" + result;

    return result;
}

InfInt InfInt::operator+(const InfInt & a) const{
    //a + (-b) = a - b
    if (!getSign() && a.getSign()) {
    InfInt * temp = new InfInt(a.value);
    return *this - *temp;
    }

    //(-a) + b = b - a
    if (getSign() && !a.getSign()) {
    //temp is positive. temp = -a
    InfInt * temp = new InfInt(value);
    return a - *temp;
    }

    //a + b = b + a
    if (value.length() < a.length())
    return a.operator+(*this);

    std::string result = this->add(a);

    //(-a) + (-b) = -(a + b)
    if (getSign() && a.getSign())
    return *new InfInt('-' + result);

    return *new InfInt(result);
}

//when this function is called, we can be sure that a > b
std::string InfInt::subtract(const InfInt& a) const{

    if (a.length() > length())
    return a.subtract(*this);
    long numOfZeros = this->length() - a.length();
    std::string aligned = a.align(numOfZeros);
    //now this and a are in the same length

    std::string result = "";
    int x = 0;
    bool carry = 0;

    for (long i = value.length() -1; i>=0; i--){
    x=value[i] - aligned[i] - carry;
    carry = false;
    if (x < 0){
        x+=10;
        carry = true;
    }
    result = (char)(x + 48) + result;
    }

    return result;
}

InfInt InfInt::operator-(const InfInt &a) const{
    if (length() == 0)
    return a * *new InfInt(-1);
    if (a.length() == 0)
    return *this * *new InfInt(-1);
    //both positive
    if (!getSign() && !a.getSign()) {
    if (*this > a)
        return *new InfInt(this->subtract(a));

    // a - b = -(b - a)
    InfInt * result = new InfInt(a.subtract(*this));
    result->setSign(true);
    return *result;
    }

    //a - (-b) = a + b
    if (!getSign() && a.getSign())
    return *new InfInt(this->add(a));

    //(-a) - b = - (a + b)
    if (getSign() && !a.getSign()) {
    InfInt result = this->add(a);
    result.setSign(true);
    return result;
    }

    //(-a) - (-b) = b - a
    InfInt temp1 = *new InfInt(value);
    InfInt temp2 = *new InfInt(a.value);
    return temp2 - temp1;
//    if (a > *this)
//        return *new InfInt(a.subtract(*this));
//
//    InfInt * result = new InfInt(this->subtract(a));
//    result->setSign(true);
//    return *result;
}

void InfInt::operator+=(const InfInt& a){
    InfInt temp = *this + a;
    value = temp.value;
    sign = temp.sign;
}

void InfInt::operator-=(const InfInt& a){
    InfInt temp = *this - a;
    value = temp.value;
    sign = temp.sign;
}

InfInt InfInt::operator*(const InfInt& a) const{

    InfInt final = 0;
    std::string result;
    InfInt* temp;


    int carry;
    int current;

    //fast mult algorithm. the same we were taught in elementary.
    for(long i=length() - 1;i >= 0; i--){
    carry = 0;
    result = "";
    for (long j=a.length() - 1; j >= 0; j--){
        current = (value[i] - '0') * (a.value[j] - '0') + carry;
        result = (char)(current % 10 + '0') + result;
        carry = current / 10;
    }

    if (carry > 0)
        result = (char)(carry + '0') + result;

    temp = new InfInt(result);
    final += *new InfInt(temp->alignLeft(length() - i - 1));
    }

    final.setSign(sign ^ a.sign);
    return final;
}

//long division implementation
InfInt InfInt::operator/(const InfInt& a) const {
    if (a.length() == 0 || a.getValue()[0] == '0') {
    throw "Devision By Zero";
    }

    //divider = |a|
    InfInt divider = *new InfInt(a.getValue());
    if (divider > *new InfInt(value))
    return *new InfInt();

    std::string result;
    int idx = 0;

    //temp is the part of the divided that's being currently focused
    InfInt temp = value[idx] - '0';
    while (temp < divider.value)
    temp = temp * 10 + (value[++idx] - '0');

    while(idx < length()) {

    if (temp == 0){
        result = result + "0";
        idx++;
    }
    else {
        // Find prefix of number that's larger
        // than a.value.


        InfInt multNum = 1;
        InfInt leftover = temp - divider;
        while (leftover >= divider) {
            leftover -= divider;
            multNum += 1;
        }

        leftover = temp - (multNum * divider);
        result = result + multNum.getValue();

        temp = leftover * 10 + (value[++idx] - '0');
        temp.setSign(false);
    }
    }
    // If a.value is greater than value
    if (result.length() == 0)
    return *new InfInt();

    InfInt final = *new InfInt(result);
    final.setSign(this->sign ^ a.getSign());
    return final;
}

InfInt InfInt::operator%(const InfInt& a) const {
    if (a.length() == 0 || a.getValue()[0] == '0') {
    throw "Modulo By Zero";
    }

    if (a > *this)
    return *new InfInt(*this);
    //divider = |a|
    InfInt divider = *new InfInt(a.getValue());

    if (divider > *new InfInt(value))
    return (*this + a) % a;
    std::string result;
    int idx = 0;
    InfInt leftover;

    InfInt temp = value[idx] - '0';
    while (temp < divider.value)
    temp = temp * 10 + (value[++idx] - '0');

    while(idx < length()) {
    // Find prefix of number that's larger
    // than a.value.


    InfInt multNum = 0;
    leftover = temp;
    while (leftover >= divider) {
        leftover -= divider;
        multNum += 1;
    }

    leftover = temp - (multNum * divider);
    leftover.setSign(false);

    temp = leftover * 10 + (value[++idx] - '0');
    }
    // If a.value is greater than value

    return leftover;
}

bool InfInt::operator<(const InfInt& a) const{
    if (getSign() && !a.getSign())
    return true;
    if (!getSign() && a.getSign())
    return false;

    unsigned long l1 = length(), l2 = a. length();

    //both positive
    if (!getSign() && !a.getSign()) {
    if (l1 > l2)
        return false;

    if (l1 < l2)
        return true;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return false;

        if (value[i] < a.value[i])
            return true;
    }
    }

    else {
    if (l1 > l2)
        return true;

    if (l1 < l2)
        return false;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return true;

        if (value[i] < a.value[i])
            return false;
    }
    }

    //equal
    return false;
}

bool InfInt::operator<=(const InfInt& a) const{
    if (getSign() && !a.getSign())
    return true;
    if (!getSign() && a.getSign())
    return false;

    unsigned long l1 = length(), l2 = a. length();

    //both positive
    if (!getSign() && !a.getSign()) {
    if (l1 > l2)
        return false;

    if (l1 < l2)
        return true;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return false;

        if (value[i] < a.value[i])
            return true;
    }
    }

    else {
    if (l1 > l2)
        return true;

    if (l1 < l2)
        return false;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return true;

        if (value[i] < a.value[i])
            return false;
    }
    }

    //equal
    return true;
}

bool InfInt::operator>(const InfInt& a) const{
    if (getSign() && !a.getSign())
    return false;
    if (!getSign() && a.getSign())
    return true;

    unsigned long l1 = length(), l2 = a. length();

    //both negative
    if (getSign() && a.getSign()) {
    if (l1 > l2)
        return false;

    if (l1 < l2)
        return true;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return false;

        if (value[i] < a.value[i])
            return true;
    }
    }

    else {
    if (l1 > l2)
        return true;

    if (l1 < l2)
        return false;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return true;

        if (value[i] < a.value[i])
            return false;
    }
    }

    //equal
    return false;
}

bool InfInt::operator>=(const InfInt& a) const{
    if (getSign() && !a.getSign())
    return false;
    if (!getSign() && a.getSign())
    return true;

    unsigned long l1 = length(), l2 = a. length();

    //both negative
    if (getSign() && a.getSign()) {
    if (l1 > l2)
        return false;

    if (l1 < l2)
        return true;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return false;

        if (value[i] < a.value[i])
            return true;
    }
    }

    else {
    if (l1 > l2)
        return true;

    if (l1 < l2)
        return false;

    for (long i = 0; i < l1; i++) {
        if (value[i] > a.value[i])
            return true;

        if (value[i] < a.value[i])
            return false;
    }
    }

    //equal
    return true;
}

bool InfInt::operator==(const InfInt& a) const{

    if (length() == 0 && a.length() == 0)
    return true;

    //if the signs are not the same
    if (getSign() ^ a.getSign())
    return false;

    if (length() != a.length())
    return false;

    for(long i = 0; i < length(); i++){
    if (value[i] != a.value[i])
        return false;
    }

    return true;
}

void InfInt::operator<<=(const InfInt& a){

    InfInt result = *this << a;

    value = result.getValue();
    sign = result.getSign();
}

void InfInt::operator>>=(const InfInt& a){

    InfInt result = *this >> a;

    value = result.getValue();
    sign = result.getSign();
}

void InfInt::operator&=(const InfInt& a){
     InfInt temp = *this & a;
     value = temp.getValue();
     sign = temp.getSign();
}

InfInt InfInt::operator^(const InfInt& a) const{
    std::string b1 = this->getBinary();
    std::string b2 = a.getBinary();

    long l1 = b1.length();
    long l2 = b2.length();

    //adding zeros from right doesn't change the value of the number
    int numOfZeros;

    if (l1 > l2) {
    numOfZeros = l1- l2;
    for (int i=0; i < numOfZeros; i++)
        b2 = b2 + "0";
    }
    else if (l2 > l1) {
    numOfZeros = l2- l1;
    for (int i=0; i < numOfZeros; i++)
        b1 = b1 + "0";
    }

    std::string result = "";

    for (int i = 0; i<l1+1; i++){
    if (b1[i] == '1' ^ b2[i] == '1')
        result = result + "1";
    else
        result = result + "0";
    }

    InfInt final = *new InfInt();
    final.initFromBinary(result);
    return final;
}

InfInt InfInt::operator|(const InfInt& a) const{
    std::string b1 = this->getBinary();
    std::string b2 = a.getBinary();

    long l1 = b1.length();
    long l2 = b2.length();

    //adding zeros from right doesn't change the value of the number
    int numOfZeros;

    if (l1 > l2) {
    numOfZeros = l1- l2;
    for (int i=0; i < numOfZeros; i++)
        b2 = b2 + "0";
    }
    else if (l2 > l1) {
    numOfZeros = l2- l1;
    for (int i=0; i < numOfZeros; i++)
        b1 = b1 + "0";
    }

    std::string result = "";

    for (int i = 0; i<l1; i++){
    if (b1[i] == '1' || b2[i] == '1')
        result = result + "1";
    else
        result = result + "0";
    }

    InfInt final = *new InfInt();
    final.initFromBinary(result);
    return final;
}

InfInt InfInt::operator&(const InfInt& a) const {
    std::string b1 = this->getBinary();
    std::string b2 = a.getBinary();

    long l1 = b1.length();
    long l2 = b2.length();

    //adding zeros from right doesn't change the value of the number
    int numOfZeros;

    if (l1 > l2) {
    numOfZeros = l1- l2;
    for (int i=0; i < numOfZeros; i++)
        b2 = b2 + "0";
    }
    else if (l2 > l1) {
    numOfZeros = l2- l1;
    for (int i=0; i < numOfZeros; i++)
        b1 = b1 + "0";
    }

    std::string result = "";

    for (int i = 0; i<l1; i++){
    if (b1[i] == '1' && b2[i] == '1')
        result = result + "1";
    else
        result = result + "0";
    }

    InfInt final = *new InfInt();
    final.initFromBinary(result);
    return final;
}

InfInt InfInt::operator<<(const InfInt& a) const {
    std::string b = this->getBinary();
    std::string result = "";
    result = result + b[0];

    //adding 0's multiplies by 2
    for (InfInt i = 0; i < a; i+=1){
    result = result + "0";
    }

    //adding the original bits after adding zeros
    for (long j = 1 ; j < b.length(); j ++){
    result = result + b[j];
    }

    InfInt final = *new InfInt();
    final.initFromBinary(result);
    return final;
}

InfInt InfInt::operator>>(const InfInt& a) const {
    std::string b = this->getBinary();

    b.erase(1, (int) a);

    InfInt final = *new InfInt();
    final.initFromBinary(b);
    return final;
}