当前位置： 文江博客话题详情

您应该如何表示 BigInt（大数）类中的数据？

发布于 2024-10-08 15:07:32 字数 131 浏览 5 评论 0原文

我正在尝试在 C++ 中实现 BigInteger 类。

基础数据如何表示？最简单的方法是使用固定或动态的 char 数组，并将整数的每个数字存储在 char 中。还有更好的办法吗？

原文

I'm trying to implement a BigInteger class in C++.

How can the base data be represented? The most naive way is to have a fixed or dynamic array of char and store each digit of an integer in a char. Is there any better way?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（3）

天荒地未老 2024-10-15 15:07:32

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

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

不过，对于欧拉项目的一些内容，我实际上实现了一个基于字符串构建的 BigNumber 类。事实证明，它是最简单的 +-*/ 实现方法，并且可以扩展到比我用几个 unsigned long long 所能得到的要长得多的数字。其性能完全足以解决这些难题。

因此，您面临着易于实施和最佳性能之间的权衡。玩得开心 ;-）

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

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.

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.

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

回复 原文
塔塔猫 2024-10-15 15:07:32

这是我的十进制实现。 string 代表值，bool 代表符号（注意：bool = true => 数字是负数）。
几乎所有基本功能都在这里进行了测试和测试准备使用。

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

把自己打垮。

#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

和 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;
}

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.

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

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):

//
// 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;
}
回复 原文
愛上了 2024-10-15 15:07:32

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

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

从那里，您可以以二为基数存储数字。加法等基本算术运算在基数 2 中的工作方式与在基数 10 中的工作方式完全相同。因此，可以使用字节 FF FF 来存储数字 65565。 （例如，在 unsigned char 向量中。）BigInt 的某些实现使用较大的块，例如 short 或 long，以提高效率。

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

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.

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 56 instead of the string 123456. (Three bytes as opposed to six.)

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 short or long, for efficiency.

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.

回复 原文
~没有更多了~

关于作者

二货你真萌

暂无简介

0 文章
0 评论
23 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

1CH1MKgiKxn9p

文章 0 评论 0

ゞ记忆︶ㄣ

文章 0 评论 0

JackDx

文章 0 评论 0

信远

文章 0 评论 0

yaoduoduo1995

文章 0 评论 0

霞映澄塘

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文