cbiguint.cpp

64位数的计算

//****************************************************
// CBIGUINT.CPP
//
// Source file for a 64 bit unsigned integer class
// REQUIRES: CBIGUINT.HPP
//
// Designed, Written and Tested by
//		Michael Potter  02/13/95
//		Compuserve 70414,2121
//
// Although I retain all copyright privileges to this 
// code and accompanying documentation, feel free to 
// use the code in anyway you deem useful free of 
// charge.  I do ask that if you re-distribute the 
// source code that you leave it unaltered with my 
// name at the top. Future additions to and versions 
// of this code may not be free. If you happen to 
// find any errors, omissions or possible 
// optimizations in my code I would gratefully 
// appreciate a line or two on the subject. I will 
// re-release the corrected code with an 
// acknowledgment of your help and give you an 
// unrestricted license to all upgrades and additions 
// for a period of one year.
//****************************************************

#include "windows.h"
#include "CBigUint.hpp"


CBigUINT& CBigUINT::setBit(int bitNum,BOOL on)
{
	DWORD mask = 1;
    DWORD * target;
	if (bitNum < 32)
		{
        target = &m_low;
		}
	else
		{
		bitNum -= 32;
        target = &m_high;
		}
	mask <<= bitNum;
	if (on)
		{
		*target |= mask;
		}
	else
		{
		*target &= ~mask;
		}
	return *this;
}

BOOL CBigUINT::isBitSetOn(int bitNum) const
{
	DWORD mask = 1;
    DWORD target;
	if (bitNum < 32)
		{
        target = m_low;
		}
	else
		{
		bitNum -= 32;
        target = m_high;
		}
	mask <<= bitNum;
	return ((target & mask) != 0);
}

BOOL CBigUINT::operator<(const CBigUINT& bu) const
{
	if ((m_high < bu.m_high)||
	    ((m_high == bu.m_high)&&(m_low < bu.m_low)))
		{
		return TRUE;
		}
	return FALSE;
}

BOOL CBigUINT::operator>(const CBigUINT& bu) const
{
	if ((m_high > bu.m_high)||
	    ((m_high == bu.m_high)&&(m_low > bu.m_low)))
		{
		return TRUE;
		}
	return FALSE;
}

BOOL CBigUINT::operator>=(const CBigUINT& bu) const
{
	if ((m_high > bu.m_high)||
	    ((m_high == bu.m_high)&&(m_low >= bu.m_low)))
		{
		return TRUE;
		}
	return FALSE;
}

BOOL CBigUINT::operator<=(const CBigUINT& bu) const
{
	if ((m_high < bu.m_high)||
	    ((m_high == bu.m_high)&&(m_low <= bu.m_low)))
		{
		return TRUE;
		}
	return FALSE;
}

CBigUINT CBigUINT::operator+(const CBigUINT& bu) const
{
	CBigUINT retVal(0,0);
	retVal.m_low = m_low + bu.m_low;
	if (retVal.m_low < max(m_low,bu.m_low))
		{
		retVal.m_high++;      //recognize overflow into high DWORD
		}
	retVal.m_high += m_high + bu.m_high;
	if (retVal.m_high < max(m_high,bu.m_high))
		{
		retVal.setToError();  // recognize full overflow
		}
	return retVal;
}

CBigUINT CBigUINT::operator-(const CBigUINT& bu) const
{
	CBigUINT retVal;
	if ((bu > *this)||(bu.isError())||(isError()))
		{
		retVal.setToError();	 // recognize an underflow/error
		}
	else
		{
		if (bu.m_low > m_low)
			{
			// recognize a carry from high DWORD
			retVal.m_low = ((DWORD)0xFFFFFFFF - bu.m_low) + m_low + 1;
			retVal.m_high = m_high - bu.m_high - 1;
			}
		else
			{
			retVal.m_low = m_low - bu.m_low;
			retVal.m_high = m_high - bu.m_high;
			}
		}
	return retVal;
}					

CBigUINT CBigUINT::operator*(const CBigUINT& bu) const
{
	CBigUINT retVal(0,0);
	if ((bu.isError())||(isError()))
		{
		retVal.setToError();  // recognize that we have an erroneous value
		                      // in our equation				  
		return retVal;
		}
	
	CBigUINT minMul(min(*this,bu));
	CBigUINT maxMul(max(*this,bu));

	BOOL lostBit = FALSE;
	while (minMul != 0)
		{
		if (minMul.m_low & BU_DWORD_LOWBIT)
			{
			if (lostBit)
				{
				retVal.setToError();  //recognize the overflow
				return retVal;
				}
			retVal += maxMul;
			}
		minMul >>= 1;
		if (maxMul.m_high & BU_DWORD_HIGHBIT)
			{
			lostBit = TRUE;	//mark that continuation will cause an overflow
			}
		maxMul <<= 1;
		}
	return retVal;	
}

CBigUINT CBigUINT::divideBy(const CBigUINT bu,CBigUINT& remainder) const
{
	CBigUINT retVal(0,0);
	if ((bu.isError())||(isError())||(bu == 0))
		{
		retVal.setToError();  // recognize a divide by zero or the use 
		                      // of an already errouneous number
		remainder = retVal;
		return retVal;
		}

	CBigUINT divider(bu);
	CBigUINT dividee(*this);
	int index = 0;
	while ((divider < dividee)&&((divider.m_high & BU_DWORD_HIGHBIT) == 0))
		{
		divider <<= 1;			 // bring the divder up to the level
		index++;				   // of the dividee
		}
	if ((divider > dividee)&&(index != 0))
		{
		divider >>= 1;			// bring the divider down one level
		index--;				  // if we went to far
		} 

	while (divider <= dividee)
		{
		dividee -= divider;			// subtract the promoted divider 
		retVal.setBit(index,TRUE);	// set the bit to mark our subtraction
		while ((divider > dividee)&&(index != 0))
			{
			divider >>= 1;			// go down to the next level 
			index--;				  // but never below what we started with
			}
		}

	remainder = dividee;		  // the remainder is what we have left
	return retVal;
}


CBigUINT CBigUINT::operator/(const CBigUINT& bu) const
{
	CBigUINT tempVal;

	return (divideBy(bu,tempVal));
}

CBigUINT CBigUINT::operator%(const CBigUINT& bu) const
{
	CBigUINT retVal;
	divideBy(bu,retVal);
	return retVal;
}

CBigUINT CBigUINT::operator+(DWORD d) const
{
	CBigUINT tempVal(d); 
	return (tempVal + *this);
}	

CBigUINT CBigUINT::operator-(DWORD d) const
{
	CBigUINT tempVal(d); 
	return (*this - tempVal);
}		  

CBigUINT CBigUINT::operator*(DWORD d) const
{
	CBigUINT tempVal(d); 
	return (tempVal * *this);
}

CBigUINT CBigUINT::divideBy(DWORD d,CBigUINT& remainder) const
{
	CBigUINT tempVal(d);
	return divideBy(tempVal,remainder);
}

CBigUINT CBigUINT::operator/(DWORD d) const
{
	CBigUINT tempVal(d);
	CBigUINT junk; 
	return divideBy(tempVal,junk);
}

CBigUINT CBigUINT::operator%(DWORD d) const
{
	CBigUINT tempVal(d);
	CBigUINT retVal;
	divideBy(tempVal,retVal);
	return retVal;
}

CBigUINT CBigUINT::operator|(const CBigUINT& bu) const
{
	CBigUINT retVal;
	retVal.m_high = (m_high | bu.m_high);
	retVal.m_low = (m_low | bu.m_low);
	return retVal;
}

CBigUINT CBigUINT::operator&(const CBigUINT& bu) const
{
	CBigUINT retVal;
	retVal.m_high = (m_high & bu.m_high);
	retVal.m_low = (m_low & bu.m_low);
	return retVal;
}

CBigUINT CBigUINT::operator^(const CBigUINT& bu) const
{
	CBigUINT retVal;
	retVal.m_high = (m_high ^ bu.m_high);
	retVal.m_low = (m_low ^ bu.m_low);
	return retVal;
}	

CBigUINT CBigUINT::operator~() const
{
	CBigUINT retVal;
	retVal.m_high = ~m_high;
	retVal.m_low = ~m_low;
	return retVal;
}

CBigUINT CBigUINT::operator<<(int numBits) const
{
	CBigUINT retVal(*this);
	while (numBits)
		{
		retVal.m_high <<= 1;
		if (retVal.m_low & BU_DWORD_HIGHBIT)
			{
			retVal.m_high |= BU_DWORD_LOWBIT;
			}
		retVal.m_low <<= 1;
		numBits--;
		}
	return retVal;
}

CBigUINT CBigUINT::operator>>(int numBits) const
{
	CBigUINT retVal(*this);
	while (numBits)
		{
		retVal.m_low >>= 1;
		if (retVal.m_high & BU_DWORD_LOWBIT)
			{
			retVal.m_low |= BU_DWORD_HIGHBIT;
			}
		retVal.m_high >>= 1;
		numBits--;
		}
	return retVal;
}

CBigUINT& CBigUINT::operator++()
{
	m_low++;
	if (m_low == 0)
		{
		m_high++;
		if (m_high == 0)
			{
			setToError();
			}
		}
	return *this;
}

CBigUINT& CBigUINT::operator--()
{
	if (m_low == 0)
		{
		if (m_high == 0)
			{
			setToError();
			}
		else
			{
			m_high--;
			m_low = BU_DWORD_ERR;
			}
		}
	else
		{
		m_low--;
		}
	return *this;
}

CBigUINT CBigUINT::operator++(int)
{
	CBigUINT retVal(*this);
	++*this;
	return retVal;
}

CBigUINT CBigUINT::operator--(int)
{
	CBigUINT retVal(*this);
	--*this;
	return retVal;
}

BOOL CBigUINT::fillString(TCHAR * str,DWORD maxChars,DWORD style) const
{
	if ((str == NULL)||(maxChars < 8))
		{
        NOROOM:
		return FALSE;  // don't have the room
		}
	if (isError())
		{
		lstrcpy(str,TEXT("#ERROR#"));
		return TRUE;
        }
 	CBigUINT tempVar(*this);
    CBigUINT remainder;
	DWORD index;
	int front,back;
	TCHAR tempChar;
    DWORD divider;
	if (style & BU_DECIMAL)
		{
		divider = (DWORD)10;
        index = 0;
		}
	else
		{
		if (style & BU_HEXADECIMAL)
			{
			divider = (DWORD)16;
			str[0] = TEXT('0');
			str[1] = TEXT('x');
        	index = 2;
			}
		else //assume binary as default
			{
			divider = (DWORD)2;
        	index = 0;
			}
        }
	do
		{
		tempVar = tempVar.divideBy(divider,remainder);
		if ((divider == 10)&&(style & BU_USE_COMMAS))
			{
			if (((index + 1)%4) == 0)
				{
				if ((index + 1) >= maxChars)
					{
					goto NOROOM;
					}
				str[index] = TEXT(',');
                index++;
                }
			}
		if ((index + 1) >= maxChars)
			{
			goto NOROOM;
			}
		if (remainder.m_low < 10)
        	{
			str[index] = LOWORD(remainder.m_low) + TEXT('0');
			}
		else
			{
			str[index] = LOWORD(remainder.m_low - 10) + TEXT('A');
            }
		index++; 
		}
	while (tempVar != 0);
	if (style & BU_DECIMAL)
		{
		front = 0;
		back = index - 1;
		}
	else
    	{
		if (style & BU_HEXADECIMAL)
			{
			while (index < 18)
				{
				if ((index + 1) >= maxChars)
					{
					goto NOROOM;
					}
				str[index] = TEXT('0');
    	        index++;
				}
			front = 2;
        	back = 17;
			}
		else 	//assume binary by default
			{
			front = 0;
			back = index - 1;
			if ((index + 1) >= maxChars)
				{
				goto NOROOM;
				}
			str[index] = TEXT('b');
        	index++;
			}
        }
	while (front < back)
		{
		tempChar = str[front];
		str[front] = str[back];
		str[back] = tempChar;
		front++;
        back--;
		}
	str[index] = (TCHAR)0;
    return TRUE;
}