bigint.cpp

有关长整形数据的相关问题

		}
		if (tmpDivisor.IsNegative()) {
			Neg = !Neg;
			tmpDivisor.Negate();
		}

		for (i = tmpDividend.m_ndw -1 ; i >= 0; --i) {
			for (mask = 0x80000000; mask; mask >>= 1) {
				tmpRemainder <<= 1;
				if ( (tmpDividend.m_value[i] & mask) != 0 )
					tmpRemainder++;
				if (tmpRemainder >= tmpDivisor) {
					if (tmpQuotient.m_ndw <= i)
						tmpQuotient.ExpandTo(i + 1);
					tmpQuotient.m_value[i] |= mask;
					tmpRemainder -= tmpDivisor;
				}
			}
		}
		if (Quotient) {
			if (tmpQuotient.IsNegative())
				tmpQuotient.Expand(1);
			tmpQuotient.Optimize();
			*Quotient = tmpQuotient;
			if (Neg)
				Quotient->Negate();
		}
		if (Remainder) {
			if (tmpRemainder.IsNegative())
				tmpRemainder.Expand(1);
			if (IsNegative())
				tmpRemainder.Negate();
			tmpRemainder.Optimize();
			*Remainder = tmpRemainder;
		}
	}
}

// Faster Division for unsigned long sized divisor
void CBigInt::Div(unsigned long Divisor, CBigInt *Quotient, CBigInt *Remainder) const {
	if (Divisor == 0L) {
		_asm {
		  mov EAX, 0
		  div EAX
		}
	}
	else if (operator !()) {
		if (Quotient) *Quotient = 0;
		if (Remainder) *Remainder = 0;
	}
	else {
		unsigned __int64 tmpRemainder = 0;
		unsigned long *tmpQuotient = new unsigned long[m_ndw];
		CBigInt tmpDividend(*this);
		bool Neg;
		if ((Neg = IsNegative()) == true)
			tmpDividend.Negate();
		int nStartResult = 0;
		
		for (int i = m_ndw - 1; i >= 0; --i) {
			tmpRemainder <<= BITS;
			tmpRemainder |= tmpDividend.m_value[i];
			tmpQuotient[i] = (unsigned long)(tmpRemainder / Divisor);
			tmpRemainder %= Divisor;
		}
		if (Quotient) {
			delete [] Quotient->m_value;
			Quotient->m_value = tmpQuotient;
			Quotient->m_ndw = m_ndw;
			Quotient->Optimize();
			if (Neg)
				Quotient->Negate();
		}
		if (Remainder) {
			*Remainder = tmpRemainder;
			if (Neg)
				Remainder->Negate();
		}
	}
}

void CBigInt::Div(long Divisor, CBigInt *Quotient, CBigInt *Remainder) const {
	if (Divisor < 0) {
		Div((unsigned long)-Divisor, Quotient, Remainder);
		if (Quotient)
			Quotient->Negate();
	}
	else
		Div((unsigned long)Divisor, Quotient, Remainder);
}

// Faster multiplication for unsigned long sized operand
CBigInt CBigInt::operator *(unsigned long Value) const {
	bool Neg;
	CBigInt tmpOp(*this);
	unsigned long carry = 0L;
	unsigned long *tmp;
	union {
		unsigned __int64 i64;
		unsigned long i32[2];
	} product;
	int i;

	if (tmpOp.IsNull())
		return tmpOp;
	if ((Neg = IsNegative()) == true)
		tmpOp.Negate();
	tmp = new unsigned long[tmpOp.m_ndw + 1];
	if (tmp == NULL) {
		tmpOp.MakeNull();
		return tmpOp;
	}
	memset(tmp, 0, (tmpOp.m_ndw + 1) * BYTES);

	product.i64 = 0;
	for (i = 0; i < tmpOp.m_ndw; ++i) {
		product.i64 = (unsigned __int64)tmpOp.m_value[i] * Value + product.i32[1];
		tmp[i] = product.i32[0];
	}
	delete [] tmpOp.m_value;

	if (product.i32[1])
		tmp[tmpOp.m_ndw] = product.i32[1];
	//else
		tmpOp.m_ndw++;
	tmpOp.m_value = tmp;
	if (tmpOp.IsNegative())
		tmpOp.Expand(1);
	tmpOp.Optimize();
	if (Neg)
		tmpOp.Negate();
	return tmpOp;
}

CBigInt CBigInt::operator *(long Value) const {
	if (Value < 0)
		return operator -().operator *((unsigned long)-Value);
	return operator *((unsigned long)Value);
}

CBigInt CBigInt::operator /(unsigned long Value) const {
	CBigInt Quotient;
	Div(Value, &Quotient, NULL);
	return Quotient;
}

CBigInt CBigInt::operator %(unsigned long Value) const {
	CBigInt Remainder;
	Div(Value, NULL, &Remainder);
	return Remainder;
}

CBigInt CBigInt::operator /(long Value) const {
	CBigInt Quotient;
	Div(Value, &Quotient, NULL);
	return Quotient;
}

CBigInt CBigInt::operator %(long Value) const {
	CBigInt Remainder;
	Div(Value, NULL, &Remainder);
	return Remainder;
}

CBigInt CBigInt::operator /(unsigned int Value) const {
	CBigInt Quotient;
	Div((unsigned long)Value, &Quotient, NULL);
	return Quotient;
}

CBigInt CBigInt::operator %(unsigned int Value) const {
	CBigInt Remainder;
	Div((unsigned long)Value, NULL, &Remainder);
	return Remainder;
}

CBigInt CBigInt::operator /(int Value) const {
	CBigInt Quotient;
	Div((long)Value, &Quotient, NULL);
	return Quotient;
}

CBigInt CBigInt::operator %(int Value) const {
	CBigInt Remainder;
	Div((long)Value, NULL, &Remainder);
	return Remainder;
}

int operator /(int A, const CBigInt &B) {
	if (B.m_ndw > 1) {
		if (B.m_ndw == 2)
			if (B.m_value[1] == 0)
				return A / B.m_value[0];
		return 0U;
	}
	return A / int(B.m_value[0]);
}

unsigned int operator /(unsigned int A, const CBigInt &B) {
	if (B.m_ndw > 1) {
		if (B.m_ndw == 2)
			if (B.m_value[1] == 0)
				return A / B.m_value[0];
		return 0;
	}
	return A / int(B.m_value[0]);
}

long operator /(long A, const CBigInt &B) {
	if (B.m_ndw > 1) {
		if (B.m_ndw == 2)
			if (B.m_value[1] == 0)
				return A / B.m_value[0];
		return 0UL;
	}
	return A / int(B.m_value[0]);
}

unsigned long operator /(unsigned long A, const CBigInt &B) {
	if (B.m_ndw > 1) {
		if (B.m_ndw == 2)
			if (B.m_value[1] == 0)
				return A / B.m_value[0];
		return 0L;
	}
	return A / int(B.m_value[0]);
}

__int64 operator /(const __int64 &A, const CBigInt &B) {
	if (B.m_ndw <= 2) {
		__int64 t = (__int64)B;
		return A / t;
	}
	else if (B.m_ndw == 3) {
		if (B.m_value[2] == 0) {
			unsigned __int64 t = (unsigned __int64)B;
			return A / t;
		}
	}
	return (__int64)0;
}

unsigned __int64 operator /(const unsigned __int64 A, const CBigInt &B) {
	if (B.m_ndw <= 2) {
		unsigned __int64 t = (unsigned __int64)B;
		return A / t;
	}
	else if (B.m_ndw == 3) {
		if (B.m_value[2] == 0) {
			unsigned __int64 t = (unsigned __int64)B;
			return A / t;
		}
	}
	return (__int64)0;
}

CBigInt operator %(int A, const CBigInt &B) {
	bool NegA = A < 0;
	bool NegB = B.IsNegative();
	
	if (B.m_ndw > 1) {
		if (NegA != NegB)
			return -B;
		return B;
	}
	return CBigInt(A % (int)B.m_value);
}

CBigInt operator %(unsigned int A, const CBigInt &B) {
	if (B.m_ndw > 1) {
		if (B.IsNegative())
			return -B;
		return B;
	}
	return CBigInt(A % (long)B.m_value[0]);
}

CBigInt operator %(long A, const CBigInt &B) {
	bool NegA = A < 0;
	bool NegB = B.IsNegative();
	
	if (B.m_ndw > 1) {
		if (NegA != NegB)
			return -B;
		return B;
	}
	return CBigInt(A % (long)B.m_value);
}

CBigInt operator %(unsigned long A, const CBigInt &B) {
	if (B.m_ndw > 1) {
		if (B.m_value[1] != 0 || B.m_ndw > 2) {
			if (B.IsNegative())
				return -B;
			return B;
		}
	}
	return CBigInt(A % (long)B.m_value[0]);
}

CBigInt operator %(const __int64 &A, const CBigInt &B) {
	bool NegA = A < 0;
	bool NegB = B.IsNegative();
	
	if (B.m_ndw > 2) {
		if (NegA != NegB)
			return -B;
		return B;
	}
	return CBigInt(A % (__int64)B.m_value);
}

CBigInt operator %(const unsigned __int64 A, const CBigInt &B) {
	if (B.m_ndw > 2) {
		if (B.m_value[2] != 0 || B.m_ndw > 3) {
			if (B.IsNegative())
				return -B;
			return B;
		}
	}
	return CBigInt(A % (__int64)B);
}
///////////////////////////////////////////////////////////////////////////////////////////////////////
// String Parsing
// Decimal, Hex, Octal, and Binary are in seperate procedures, to improve performance
///////////////////////////////////////////////////////////////////////////////////////////////////////

CBigInt& CBigInt::FromDec(const char *szVal) {
	// Determine the number of valid characters
	const char *pStart = szVal;
	while (*pStart == ' ' || *pStart == '\t')
		pStart++;
	const char *pEnd = pStart;
	while ( *pEnd >= '0' && *pEnd <= '9')
		pEnd++;
	unsigned nLen = pEnd - pStart;
	*this = 0;
	if (IsNull()) return *this;
	if (nLen == 0)
		return *this;
	const unsigned long MAXDEC = (MAXULONG - 9) / 10;

	while (pStart < pEnd && m_value[0] <= MAXDEC) {
		m_value[0] = m_value[0] * 10 + *pStart - '0';
		pStart++;
	}
	while (pStart < pEnd) {
		unsigned long Power = 1;
		unsigned long dwTmp = 0;
		while (pStart < pEnd && Power <= MAXDEC) {
			dwTmp = dwTmp * 10 + *pStart - '0';
			pStart++;
			Power *= 10;
		}
		*this *= Power;
		*this += dwTmp;
		if (IsNull()) break;
	}
	return *this;
}

CBigInt& CBigInt::FromHex(const char *szVal) {
	// Determine the number of valid characters
	const char *pStart = szVal;
	while (*pStart == ' ' || *pStart == '\t')
		pStart++;
	const char *pEnd = pStart;
	while ( (*pEnd >= '0' && *pEnd <= '9') || (*pEnd >= 'A' && *pEnd <= 'F') || (*pEnd >='a' && *pEnd <= 'f'))
		pEnd++;
	unsigned nLen = pEnd - pStart;
	if (nLen == 0) {
		*this = 0;
		return *this;
	}
	// Calculate the size of the result
	long ndw = (nLen + NIBBLES - 1) / NIBBLES;
	if (ndw != m_ndw) {
		MakeNull();
		m_value = new unsigned long[m_ndw = ndw];
		if (m_value == NULL) {
			m_ndw = 0;
			return *this;
		}
	}
	memset(m_value, 0, m_ndw * BYTES);
	int nShift = 0;
	nLen = 0;
	while (pEnd > pStart) {
		pEnd--;
		if (*pEnd >= '0' && *pEnd <= '9')
			m_value[nLen] |= (*pEnd - '0') << nShift;
		else if (*pEnd >= 'A' && *pEnd <= 'F')
			m_value[nLen] |= (*pEnd - 'A' + 10) << nShift;
		else // if (*pEnd >= 'a' && *pEnd <= 'z')
			m_value[nLen] |= (*pEnd - 'a' + 10) << nShift;
		nShift += 4;
		if (nShift >= BITS) {
			nShift = 0;
			nLen++;
		}
	}
	if (IsNegative())
		Expand(1);
	return *this;
}

CBigInt& CBigInt::FromOct(const char *szVal) {
	const char *pStart = szVal;
	while (*pStart == ' ' || *pStart == '\t')
		pStart++;
	const char *pEnd = pStart;
	while (*pEnd >= '0' && *pEnd <= '7')
		pEnd++;
	int nLen = pEnd - pStart;
	if (nLen == 0) {
		*this = 0;
		return *this;
	}
	long ndw = (nLen * 3 + BITS - 1) / BITS;
	if (ndw != m_ndw) {
		if (m_ndw)
			delete [] m_value;
		m_value = new unsigned long[m_ndw = ndw];
		if (m_value == NULL) {
			m_ndw = 0;
			return *this;
		}
	}
	memset(m_value, 0, m_ndw * BYTES);
	int nShift = 0;
	nLen = 0;
	while (pEnd > pStart) {
		pEnd--;
		m_value[nLen] |= (*pEnd - '0') << nShift;
		if ((nShift + 3 ) >= BITS) {
			nShift = nShift + 3 - BITS;
			if (nLen < m_ndw)
				m_value[++nLen] = (*pEnd - '0') >> (3 - nShift);
		}
		else
			nShift += 3;
	}
	if (IsNegative())
		Expand(1);
	Optimize();
	return *this;
}

CBigInt& CBigInt::FromBin(const char *szVal) {
	const char *pStart = szVal;
	while (*pStart == ' ' || *pStart == '\t')
		pStart++;
	const char *pEnd = pStart;
	while (*pEnd >= '0' && *pEnd <= '1')
		pEnd++;
	unsigned nLen = pEnd - pStart;
	if (nLen == 0) {
		*this = 0;
		return *this;
	}
	long ndw = (nLen * 3 + BITS - 1) / BITS;
	if (ndw != m_ndw) {
		if (m_ndw)
			delete [] m_value;
		m_value = new unsigned long[m_ndw = ndw];
		if (m_value == NULL) {
			m_ndw = 0;
			return *this;
		}
	}
	memset(m_value, 0, m_ndw * BYTES);
	int nShift = 0;
	nLen = 0;
	while (pEnd > pStart) {
		pEnd--;
		if (*pEnd == '1')
			m_value[nLen] |= 1 << nShift;
		if (++nShift >= BITS) {
			nShift = 0;
			nLen++;
		}
	}
	if (IsNegative())
		Expand(1);
	Optimize();
	return *this;
}

inline int BaseDigitValue(char digit, int Radix) {
	if (digit >= '0' || digit <= '9') {
		digit -= '0';
		return digit < Radix ? digit : -1;
	}
	if (digit >= 'a' && digit <= 'z') {
		digit -= ('a' - 10);
		return digit < Radix ? digit : -1;
	}
	if (digit >= 'A' && digit <= 'Z') {
		digit -= ('A' - 10);
		return digit < Radix ? digit : -1;
	}
	return -1;
}

CBigInt& CBigInt::FromString(const char *szVal, int Radix /* = 10 */ ) {
	// Use the fater conversions for Binary, Octal, or Hexadecimal
	if (Radix == 2)
		return FromBin(szVal);
	if (Radix == 8)
		return FromOct(szVal);
	if (Radix == 10)
		return FromDec(szVal);
	if (Radix == 16)
		return FromHex(szVal);
	if (Radix > 36)
		return (*this = 0);
	while (*szVal == ' ' || *szVal == '\t')
		szVal++;
	bool neg = false;
	if (Radix == 10) {
		if (*szVal == '+')
			szVal++;
		else if (*szVal == '-') {
			neg = true;
			szVal++;
		}
	}
	*this = 0;
	int n;
	while ((n = BaseDigitValue(*szVal, Radix)) >= 0) {
		*this *= Radix;
		*this += n;
		if(IsNull())
			return *this;
		szVal++;
	}
	if (IsNegative())
		Expand(1);
	if (neg)
		Negate();
	return *this;
}

///////////////////////////////////////////////////////////////////////////////////////////////////////
// Formatting Functions
///////////////////////////////////////////////////////////////////////////////////////////////////////
char* CBigInt::Format(char *szBuf, unsigned long cbBuf, unsigned long *pNeeded, unsigned int Radix /* = 10 */) const {
	unsigned long cbNeeded = 0;
	CBigInt tmp(*this);
	CBigInt Remainder;
	bool neg = false;

	if (IsNull()) {
		cbNeeded = 5;
		if (cbBuf >= cbNeeded && szBuf != NULL)
			strcpy(szBuf, "Null");
		else
			szBuf = NULL;
	}
	else {
		if (tmp.IsNegative()) {
			if (Radix == 10) {
				tmp.Negate();
				neg = true;
			}
			else
				tmp.Expand(1);
		}

		// The following is broken down into seperate division operations, the second one
		// being straight long integer division. This minimises the CBigInt divisions that 
		// are needed, improving performance with large numbers considerably.
		int Power = 1;
		unsigned long Divisor = (unsigned long)Radix;
		while (MAXULONG / Divisor >= Radix) {
			Power++;
			Divisor *= Radix;
		}

		do	{
			tmp.Div(Divisor, tmp, Remainder);
			for (int i = 0; i < Power; ++i) {
				// Mathemtical Note: Remainder will always be less than MAXULONG
				char rem = (char)(Remainder.m_value[0] % Radix);
				Remainder.m_value[0] /= Radix;
				if (!tmp && !rem && !Remainder)
					break;	// Finished - and we dont want leading zeros
				if (cbNeeded < cbBuf) {
					// Convert to a character
					if (rem <= 9)
						*(szBuf + cbNeeded) = (rem + '0');
					else 
						*(szBuf + cbNeeded) = (char)(rem - 10 + 'A');
				}
				cbNeeded++;
			}
		} while (tmp);
		if (neg) {
			if (cbNeeded < cbBuf)
				*(szBuf + cbNeeded) = '-';
			cbNeeded++;
		}
		if (cbNeeded < cbBuf) 
			*(szBuf + cbNeeded) = '\0';
		else if (cbBuf)
			*(szBuf + cbBuf - 1) = '\0';
		cbNeeded++;
		if (szBuf)
			strrev(szBuf);
	}
	if (pNeeded)
		*pNeeded = cbNeeded;
	return szBuf;
}

char* CBigInt::Format(unsigned int Radix /* = 10 */ ) const {
	if (m_stringBuf) {
		delete [] m_stringBuf;
		m_stringBuf = NULL;
	}
	// Calculate how many bytes needed
	unsigned long cbNeeded = 1;	// At least 1 for the trailing null character
	if (IsNull())
		cbNeeded = 5;
	else {
		int Power = 1;
		unsigned long Divisor = (unsigned long)Radix;
		while (MAXULONG / Divisor > Radix) {
			Power++;
			Divisor *= Radix;
		}
		CBigInt tmp(*this);
		if (tmp.IsNegative()) {
			tmp.Expand(1);
			if (Radix == 10)
				cbNeeded++;
		}
		while (tmp > Divisor) {
			tmp /= Divisor;
			cbNeeded += Power;
		}
		while (tmp.m_value[0]) {
			tmp.m_value[0] /= Radix;
			cbNeeded++;
		}
	}
	m_stringBuf = new char [cbNeeded];
	return Format(m_stringBuf, cbNeeded, NULL, Radix);
}