首页
社区
课程
招聘
问答 CTF 排行榜 知识库 工具下载 看雪峰会 看雪商城 证书查询
  1. 社区
  2. 付费问答
    3. 发新帖
[旧帖] [邀请码已发][原创]大整数实现 by 软件工程专业大一学生(求邀请码) 0.00雪花
发表于: 2010-5-3 22:46 2204

[旧帖] [邀请码已发][原创]大整数实现 by 软件工程专业大一学生(求邀请码) 0.00雪花

杨智渊 活跃值
2010-5-3 22:46
2204
#include <cstdlib>
#include <iostream>
#include <stdlib.h>

using namespace std;

class BigInt// extended int supporting numbers up to 1024 digits
{
public:
    // constructors
  BigInt();// initialized to 0
  BigInt(int);// the first digit mustn't be 0
  BigInt(char*);// the first digit mustn't be 0

    // input & output
    friend istream& operator >> (istream&, BigInt&);
  friend ostream& operator << (ostream&, const BigInt&);

    // arithmetic operators
    friend const BigInt operator ++ (BigInt& num);
    friend const BigInt operator ++ (BigInt& num, int);
    friend const BigInt operator -- (BigInt& num);
    friend const BigInt operator -- (BigInt& num, int);

    friend const BigInt operator + (const BigInt&);// positive sign
    friend const BigInt operator - (const BigInt&);// negative sign
    const BigInt operator = (const BigInt&);

  friend const BigInt operator + (const BigInt&, const BigInt&);
  friend const BigInt operator - (const BigInt&, const BigInt&);
  friend const BigInt operator * (const BigInt&, const BigInt&);
  friend const BigInt operator / (const BigInt&, const BigInt&);
  friend const BigInt operator % (const BigInt&, const BigInt&);

    friend const BigInt operator += (BigInt&, const BigInt&);
  friend const BigInt operator -= (BigInt&, const BigInt&);
  friend const BigInt operator *= (BigInt&, const BigInt&);
  friend const BigInt operator /= (BigInt&, const BigInt&);
  friend const BigInt operator %= (BigInt&, const BigInt&);

    // relational operators
  friend bool operator == (const BigInt&, const BigInt&);
  friend bool operator != (const BigInt&, const BigInt&);
  friend bool operator > (const BigInt&, const BigInt&);
  friend bool operator >= (const BigInt&, const BigInt&);
  friend bool operator < (const BigInt&, const BigInt&);
  friend bool operator <= (const BigInt&, const BigInt&);
private:
    int sign;// 1 for positive and zero, -1 for negative 
  int big[1024];
    int size;
};

int main()
{//test code
}

BigInt::BigInt()
{
    sign = 1;
    big[0] = 0;
    size = 1;
}

BigInt::BigInt(int i)
{
    sign = (i >= 0 ? 1 : -1);

    char str[100];
    _itoa_s(abs(i), str, 10);
    for (unsigned int a = 0; a < strlen(str); a++)
        big[strlen(str) - 1 - a] = str[a] - 48;
    size = static_cast<int>(strlen(str));
}

BigInt::BigInt(char* str)
{
  sign = (str[0] == '-' ? -1 : 1);

  char *absStr;
  if (str[0] != '-')
    absStr = str;
  else
    absStr = str + 1;
  for (unsigned int a = 0; a < strlen(absStr); a++)
    big[strlen(absStr) - 1 - a] = absStr[a] - 48;

  size = static_cast<int>(strlen(absStr));
}

istream& operator >> (istream& input, BigInt& num)
{
    char str[1024];
    input >> str;

  num.sign = (str[0] == '-' ? -1 : 1);

  char *absStr;
  if (str[0] != '-')
    absStr = str;
  else
    absStr = str + 1;
  for (unsigned int a = 0; a < strlen(absStr); a++)
    num.big[strlen(absStr) - 1 - a] = absStr[a] - 48;

  num.size = static_cast<int>(strlen(absStr));

    return input;
}

ostream& operator << (ostream& output, const BigInt& num)
{
    if (num.sign == -1)
        cout << '-';
    for (int a = num.size - 1; a >= 0; a--)
        output << num.big[a];

    return output;
}

const BigInt operator ++ (BigInt& num)
{
    num += 1;
    return num;
}

const BigInt operator ++ (BigInt& num, int)
{
    BigInt temp = num;
    num += 1;
    return temp;
}

const BigInt operator -- (BigInt& num)
{
    num -= 1;
    return num;
}

const BigInt operator -- (BigInt& num, int)
{
    BigInt temp = num;
    num -= 1;
    return temp;
}

const BigInt operator + (const BigInt& num)
{
    return num;
}

const BigInt operator - (const BigInt& num)
{
    BigInt result = num;
    result.sign *= -1;
    return result;
}

const BigInt BigInt::operator = (const BigInt& num0)
{
    sign = num0.sign;
    size = num0.size;
    for (int a = 0; a < num0.size; a++)
        big[a] = num0.big[a];

    return num0;
}

const BigInt operator + (const BigInt& num0, const BigInt& num1)
{
    if (num0.sign == num1.sign)// num0 and num1 have the same sign, compute the num0 + num1
    {
        BigInt sum = (num0.size > num1.size ? num0 : num1);
        int temp;
        int carry = 0;
        for (int a = 0; a < min(num0.size, num1.size); a++)
        {
            temp =  num0.big[a] + num1.big[a] + carry;
            sum.big[a] = temp % 10;
            carry = temp / 10;
        }
        if (num0.size > num1.size)
        {
            for (int a = num1.size; a < num0.size; a++)
            {
                temp =  num0.big[a];
                sum.big[a] = temp % 10 + carry;
                carry = temp / 10;
            }
        }
        else if (num1.size > num0.size)
        {
            for (int a = num0.size; a < num1.size; a++)
            {
                temp =  num1.big[a];
                sum.big[a] = temp % 10 + carry;
                carry = temp / 10;
            }
        }
        if (carry != 0)
        {
            sum.big[sum.size] = carry;
            sum.size++;
        }
        
        return sum;
    }
    else if (num0.sign > 0)// num0 is positive, num1 is negative, compute num0 - absNum1
        return (num0 - (-num1));
    else// num0 is negative, num1 is positive, compute num1 - absNum0
        return (num1 - (-num1));
}

const BigInt operator - (const BigInt& num0, const BigInt& num1)
{
    if (num0.sign > 0 && num1.sign > 0)// num0 and num1 are both positive
    {
        if (num0 > num1)// num0 > num1, compute num0 - num1
        {
            BigInt result = num0;
            for (int a = 0; a < num1.size; a++)
            {
                if (result.big[a] >= num1.big[a])
                    result.big[a] -= num1.big[a];
                else
                {
                    result.big[a + 1] -= 1;
                    result.big[a] -= num1.big[a];
                    result.big[a] += 10;
                }
            }
            for (int a = 0; a < result.size; a++)
            {
                if (result.big[a] < 0)
                {
                    result.big[a] += 10;
                    result.big[a + 1] -= 1;
                }
            }
            for (int a = result.size - 1; a >= 0; a--)
            {
                if (result.big[a] == 0)
                    result.size--;
                else
                    break;
            }
            return result;
        }
        else if (num0 < num1)// num0 < num1, num0 - num1 = -(num1 < num0)
        {
            return -(num1 - num0);
        }
        else// num0 == num1, num0 - num1 = 0
        {
            
            return BigInt();
        }
    }
    else if (num0.sign > 0 && num1.sign < 0)// num0 is positive, num1 is negative, num0 - num1 = num0 + absNum1
    {
        return (num0 + (-num1));
    }
    else if (num0.sign < 0 && num1.sign > 0)// num0 is negative, num1 is positive, num0 - num1 = -(absNum0 + num1)
    {
        return -(num1 + (-num0));
    }
    else// num0 and num1 are both negative, num0 - num1 = absNum1 - absNum0
    {
        return (-num1) - (-num0);
    }
}

const BigInt operator * (const BigInt& num0, const BigInt& num1)
{
    if (num0 == 0 || num1 == 0)
        return 0;
    else
    {
        BigInt result;
        BigInt temp;
        for (int a = 0; a < num1.size; a++)// compute absNum0 * absNum1
        {
            temp.sign = 1;
            temp.size = num0.size + a;
            for (int b = 0; b < a; b++)
                temp.big = 0;
            for (int b = 0; b < num0.size; b++)
                temp.big[a + b] = num0.big;
            for (int b = 0; b < num1.big[a]; b++)
                result = result + temp;
        }
        result.sign = num0.sign * num1.sign;// compute result's sign

        return result;
    }
}

const BigInt operator / (const BigInt& num0, const BigInt& num1)
{
    if (num1 == 0)
    {
        cout << "Wrong divide!\n";
        exit(1);
    }
    BigInt absNum0 = num0, absNum1 = num1, result;
    absNum0.sign = 1;
    absNum1.sign = 1;
    if (absNum0 < absNum1)
        return result;
    else
    {
        result.size = 0;
        BigInt temp0 = absNum0;
        BigInt temp1;
        int resDigit = absNum0.size - absNum1.size;// means which digit of result
        int sizeDif = temp0.size - absNum1.size;// size difference
        while (temp0 >= absNum1)// compute absNum0 / absNum1
        {
          // initialize temp1
          temp1.size = absNum1.size + sizeDif;
          for (int a = 0; a < temp1.size; a++)
            temp1.big[a] = (a < sizeDif ? 0 : absNum1.big[a - sizeDif]);
          // get digit result
            int i;
            for (i = 0; i < 10; i++)
            {
                if (temp0 < temp1)
                    break;
                temp0 = temp0 - temp1;
            }
            if (result.size == 0)
            {
                if (i > 0)
                {
                    result.size = resDigit + 1;
                    result.big[resDigit] = i;
                    for (int a = 0; a < resDigit; a++)
                        result.big[a] = 0;
                }sizeDif--;resDigit--;
            }
            else
            {
                result.big[resDigit] = i;
                resDigit--;
                sizeDif--;
            }
        }
        result.sign = num0.sign * num1.sign;// compute result's sign
        return result;    
    }
}

const BigInt operator % (const BigInt& num0, const BigInt& num1)
{
    return num0 - (num0 / num1) * num1;
}

const BigInt operator += (BigInt& num0, const BigInt& num1)
{
    num0 = num0 + num1;
    return num0;
}

const BigInt operator -= (BigInt& num0, const BigInt& num1)
{
    num0 = num0 - num1;
    return num0;
}

const BigInt operator *= (BigInt& num0, const BigInt& num1)
{
    num0 = num0 * num1;
    return num0;
}

const BigInt operator /= (BigInt& num0, const BigInt& num1)
{
    num0 = num0 / num1;
    return num0;
}

const BigInt operator %= (BigInt& num0, const BigInt& num1)
{
    num0 = num0 % num1;
    return num0;
}

bool operator == (const BigInt& num0, const BigInt& num1)
{
    if (num0.sign != num1.sign || num0.size != num1.size)
        return 0;
    for (int a = 0; a < num0.size; a++)
        if (num0.big[a] != num1.big[a])
            return 0;
    return 1;
}

bool operator != (const BigInt& num0, const BigInt& num1)
{
    return !(num0 == num1);
}

bool operator > (const BigInt& num0, const BigInt& num1)
{
     if (num0.sign != num1.sign)
         return (num0.sign > 0);
     if (num0.size > num1.size)
         return (num0.sign > 0);
     if (num0.size < num1.size)
         return (num0.sign < 0);
     for (int a = num0.size - 1; a >= 0; a--)
     {
         if (num0.big[a] > num1.big[a])
            return (num0.sign > 0 ? 1 : 0);
         else if (num0.big[a] < num1.big[a])
             return (num0.sign < 0 ? 1 : 0);
     }
     return 0;
}

bool operator >= (const BigInt& num0, const BigInt& num1)
{
    return (num0 == num1) || (num0 > num1);
}

bool operator < (const BigInt& num0, const BigInt& num1)
{
    return !(num0 > num1 || num0 == num1);
}

bool operator <= (const BigInt& num0, const BigInt& num1)
{
    return !(num0 > num1);
}

[课程]Linux pwn 探索篇！

上传的附件：
收藏
免费 ・0
支持
分享
最新回复 (5)
杨智渊
雪    币： 39
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
2 楼
顺便求测试，求讨论
2010-5-3 22:54
0
garyzjq
雪    币： 463
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
3 楼
这是什么情况…看不懂了…
2010-5-3 23:08
0
younghust
雪    币： 76
活跃值： (25)
能力值： ( LV3，RANK：20 )
在线值：
发帖
回帖
粉丝
私信
4 楼
最好说清楚程序是干什么的，有什么用处
如果是大一的话，应该鼓励一下。
2010-5-4 11:26
0
杨智渊
雪    币： 39
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
5 楼
多谢批评，我一定注意
2010-5-4 18:07
0
杨智渊
雪    币： 39
活跃值： (10)
能力值： ( LV2，RANK：10 )
在线值：
发帖
回帖
粉丝
私信
6 楼
程序说明：
1.extend type "int" to "BigInt"
2.BigInt requirements:
–Implemented as a class
–Support numbers up to 1024 digits
–Arithmetic & relational operators
–Read from stdin, write to stdout
–Certain constructors
2010-5-4 18:11
0
游客
登录 | 注册 方可回帖
回帖 表情 雪币赚取及消费
高级回复
返回
//