int96.cpp

96位大数运算实现

  }
  if (B.IsNegative())
  {
    bBNegative = TRUE;
    B.Negate();
  }

  CInt96 rVal;
  CInt96 b1 = ((unsigned __int64)B.m_LSB) * ((unsigned __int64)A.m_LSB);
  CInt96 b2 = ((unsigned __int64)B.m_CSB) * ((unsigned __int64)A.m_LSB);
  CInt96 b3 = ((unsigned __int64)B.m_MSB) * ((unsigned __int64)A.m_LSB);
  CInt96 b4 = ((unsigned __int64)B.m_LSB) * ((unsigned __int64)A.m_CSB);
  CInt96 b5 = ((unsigned __int64)B.m_CSB) * ((unsigned __int64)A.m_CSB);
  CInt96 b6 = ((unsigned __int64)B.m_LSB) * ((unsigned __int64)A.m_MSB);

  rVal += b1;
  rVal += b2 << 32;
  rVal += b3 << 64;
  rVal += b4 << 32;
  rVal += b5 << 64;
  rVal += b6 << 64;

  if ((bANegative && !bBNegative) || (!bANegative && bBNegative))
    rVal.Negate();
  return rVal;
}

BOOL CInt96::GetBit(int nIndex) const
{
  ASSERT(nIndex >= 0 && nIndex < 96);

  BOOL rVal;
  DWORD dwBitMask = 0x80000000 >> (nIndex % 32);
  if (nIndex < 32)
    rVal = ((m_MSB & dwBitMask) != 0);
  else if (nIndex < 64)
    rVal = ((m_CSB & dwBitMask) != 0);
  else
    rVal = ((m_LSB & dwBitMask) != 0);

  return rVal;
}

void CInt96::SetBit(int nIndex, BOOL value)
{
  ASSERT(nIndex >= 0 && nIndex < 96);

  DWORD dwBitMask = 0x80000000 >> (nIndex % 32);
  if (!value)
    dwBitMask = ~dwBitMask;
  if (nIndex < 32)
  {
    if (value)
      m_MSB = m_MSB | dwBitMask;
    else
      m_MSB = m_MSB & dwBitMask;
  }
  else if (nIndex < 64)
  {
    if (value)
      m_CSB = m_CSB | dwBitMask;
    else
      m_CSB = m_CSB & dwBitMask;
  }
  else
  {
    if (value)
      m_LSB = m_LSB | dwBitMask;
    else
      m_LSB = m_LSB & dwBitMask;
  }
}

CInt96 CInt96::operator^(const CInt96& value) const
{
  CInt96 rVal;
  rVal.m_LSB = m_LSB ^ value.m_LSB;
  rVal.m_CSB = m_CSB ^ value.m_CSB;
  rVal.m_MSB = m_MSB ^ value.m_MSB;
  return rVal;
}

CInt96 CInt96::operator|(const CInt96& value) const
{
  CInt96 rVal;
  rVal.m_LSB = m_LSB | value.m_LSB;
  rVal.m_CSB = m_CSB | value.m_CSB;
  rVal.m_MSB = m_MSB | value.m_MSB;
  return rVal;
}

CInt96 CInt96::operator&(const CInt96& value) const
{
  CInt96 rVal;
  rVal.m_LSB = m_LSB & value.m_LSB;
  rVal.m_CSB = m_CSB & value.m_CSB;
  rVal.m_MSB = m_MSB & value.m_MSB;
  return rVal;
}

CInt96& CInt96::operator^=(const CInt96& value)
{
  m_LSB ^= value.m_LSB;
  m_CSB ^= value.m_CSB;
  m_MSB ^= value.m_MSB;
  return *this;
}

CInt96& CInt96::operator|=(const CInt96& value)
{
  m_LSB |= value.m_LSB;
  m_CSB |= value.m_CSB;
  m_MSB |= value.m_MSB;
  return *this;
}

CInt96& CInt96::operator&=(const CInt96& value)
{
  m_LSB &= value.m_LSB;
  m_CSB &= value.m_CSB;
  m_MSB &= value.m_MSB;
  return *this;
}

CInt96& CInt96::operator%=(const CInt96& value)
{
  *this = *this % value;
  return *this;
}

CInt96 CInt96::operator%(const CInt96& value) const
{
  CInt96 Remainder;
  CInt96 Quotient;
  Modulus(value, Quotient, Remainder);
  return Remainder;
}
 
CInt96 CInt96::operator/(const CInt96& value) const
{
  CInt96 Remainder;
  CInt96 Quotient;
  Modulus(value, Quotient, Remainder);
  return Quotient;
}

void CInt96::Modulus(const CInt96& divisor, CInt96& Quotient, CInt96& Remainder) const
{
  //Correctly handle negative values
  CInt96 tempDividend(*this);
  CInt96 tempDivisor(divisor);
  BOOL bDividendNegative = FALSE;
  BOOL bDivisorNegative = FALSE;
  if (tempDividend.IsNegative())
  {
    bDividendNegative = TRUE;
    tempDividend.Negate();
  }
  if (tempDivisor.IsNegative())
  {
    bDivisorNegative = TRUE;
    tempDivisor.Negate();
  }

  //Handle the special case's
  if (tempDivisor.IsZero())
  {
    //force a Divide by Zero exception
    _asm
    {
      mov EAX, 0
      div EAX
    }
  }
  else if (tempDividend.IsZero())
  {
    Quotient = CInt96(0);
    Remainder = CInt96(0);
  }
  else
  {
    Remainder.Zero();
    for (int i=0; i<96; i++)
    {
      Remainder += tempDividend.GetBit(i);
      BOOL bBit = (Remainder >= tempDivisor);
      Quotient.SetBit(i, bBit);
      if (bBit)
        Remainder -= tempDivisor;
    
      if ((i!=95) && !Remainder.IsZero())
        Remainder <<= 1;
    }
  }

  if ((bDividendNegative && !bDivisorNegative) || (!bDividendNegative && bDivisorNegative))
  {
    //Ensure the following formula applies for negative dividends
    //dividend = divisor * Quotient + Remainder
    Quotient.Negate();
  }
}

CInt96::operator int()
{
  if (IsNegative())
  {
    CInt96 t(*this);
    t.Negate();
    return -t;
  }
  else
  {
    ASSERT(m_CSB == 0 && m_MSB == 0 && ((m_LSB & 0x80000000) == 0));
    return (int) m_LSB;
  }
}

CInt96::operator unsigned int()
{
  ASSERT(m_CSB == 0 && m_MSB == 0);
  ASSERT(!IsNegative());
  return m_LSB;
}

CInt96::operator __int64()
{
  if (IsNegative())
  {
    CInt96 t(*this);
    t.Negate();
    return -t;
  }
  else
  {
    ASSERT(m_MSB == 0 && ((m_CSB & 0x80000000) == 0));
    return (((__int64) m_CSB) << 32) + m_LSB;
  }
}

CInt96::operator unsigned __int64()
{
  ASSERT(m_MSB == 0);
  ASSERT(!IsNegative());
  return (((unsigned __int64) m_CSB) << 32) + m_LSB;
}

CString CInt96::FormatAsHex(BOOL bLeadingZeros) const
{
  CString rVal;

  CString sTemp;

  if (bLeadingZeros)
  {
    sTemp.Format(_T("%08x"), m_MSB);
    rVal += sTemp;
  }
  else
  {
    if (m_MSB)
    {
      sTemp.Format(_T("%x"), m_MSB);
      rVal += sTemp;
    }
  }

  if (bLeadingZeros)
  {
    sTemp.Format(_T("%08x"), m_CSB);
    rVal += sTemp;
  }
  else
  {
    if (m_CSB)
    {
      if (m_MSB)
        sTemp.Format(_T("%08x"), m_CSB);
      else
        sTemp.Format(_T("%x"), m_CSB);        
      rVal += sTemp;
    }
  }

  if (bLeadingZeros)
  {
    sTemp.Format(_T("%08x"), m_LSB);
    rVal += sTemp;
  }
  else
  {
    if (m_LSB)
    {
      if (m_MSB || m_CSB)
        sTemp.Format(_T("%08x"), m_LSB);
      else
        sTemp.Format(_T("%x"), m_LSB);
      rVal += sTemp;
    }
  }

  if (rVal.IsEmpty())
    rVal = _T("0");

  return rVal;
}

CString CInt96::FormatAsBinary(BOOL bLeadingZeros) const
{
  CString rVal;

  BOOL bInLeadingZeros = TRUE;
  LPTSTR pszBuffer = rVal.GetBuffer(97);
  int nCurOffset = 0;
  for (int i=0; i<96; i++)
  {
    if (GetBit(i))
    {
      pszBuffer[nCurOffset] = _T('1');
      bInLeadingZeros = FALSE;
      nCurOffset++;
    }
    else
    {
      if (bLeadingZeros || (!bLeadingZeros && !bInLeadingZeros))
      {
        pszBuffer[nCurOffset] = _T('0');
        nCurOffset++;
      }
    }
  }
  if (nCurOffset == 0)
  {
    pszBuffer[nCurOffset] = _T('0');
    nCurOffset++;
  }
  pszBuffer[nCurOffset] = _T('\0');
  rVal.ReleaseBuffer();

  return rVal;
}

CString CInt96::FormatAsDecimal() const
{
  CString rVal;
  LPTSTR pszBuffer = rVal.GetBuffer(97);

  CInt96 t(*this);
  BOOL bNegative = t.IsNegative();
  if (bNegative)
    t.Negate();

  int i = 0;
  while (t >= CInt96(10))
  {
    CInt96 remainder = t % CInt96(10);
    pszBuffer[i] = (TCHAR) (remainder.m_LSB + _T('0'));

    //Get ready for the next loop
    t /= 10;
    ++i;
  }

  pszBuffer[i] = (TCHAR) (t.m_LSB + _T('0'));
  pszBuffer[i+1] = _T('\0');
  rVal.ReleaseBuffer();
  rVal.MakeReverse();

  if (bNegative)
    rVal = _T("-") + rVal;

  return rVal;
}

BOOL CInt96::ConvertFromBinaryString(const CString& sText)
{
  //Remove any leading or trailing spaces
  CString sTemp(sText);
  sTemp.TrimLeft();
  sTemp.TrimRight();

  //Is the string too long?
  int nLength = sTemp.GetLength();
  if (nLength > 96)
  {
    TRACE(_T("Binary string was too long for conversion\n"));
    return FALSE;
  }

  //Iterate through each digit
  CInt96 t;
  for (int i=nLength-1; i>=0; i--)
  {
    TCHAR c = sTemp.GetAt(i);

    if (c == _T('1'))
      t.SetBit(95 - (nLength - 1 - i), TRUE);
    else if (c != _T('0'))
    {
      TRACE(_T("Binary string did not exclusively contain 1's or 0's\n"));
      return FALSE;
    }
  }

  *this = t;
  return TRUE;
}

BOOL CInt96::ConvertFromHexString(const CString& sText)
{
  //Remove any leading or trailing spaces
  CString sTemp(sText);
  sTemp.TrimLeft();
  sTemp.TrimRight();

  //Is the string too long?
  int nLength = sTemp.GetLength();
  if (nLength > 24)
  {
    TRACE(_T("Hex string was too long for conversion\n"));
    return FALSE;
  }

  //Iterate through each digit
  CInt96 t;
  for (int i=0; i<nLength; i++)
  {
    TCHAR c = sTemp.GetAt(i);

    if (c >= _T('0') && c <= _T('9'))
      t += CInt96(c - _T('0'));
    else if (c >= _T('A') && c <= _T('F'))
      t += CInt96(c - _T('A') + 10);
    else if (c >= _T('a') && c <= _T('f'))
      t += CInt96(c - _T('a') + 10);
    else
    {
      TRACE(_T("Hex string did not exclusively contain hex digits\n"));
      return FALSE;
    }

    if (i<(nLength-1))
      t <<= 4;
  }

  *this = t;
  return TRUE;
}

BOOL CInt96::ConvertFromDecimalString(const CString& sText)
{
  //Remove any leading or trailing spaces
  CString sTemp(sText);
  sTemp.TrimLeft();
  sTemp.TrimRight();

  //Handle a negative decimal value
  int nLength = sTemp.GetLength();
  BOOL bNegative = FALSE;
  if (nLength && sTemp.GetAt(0) == _T('-'))
  {
    bNegative = TRUE;
    sTemp = sTemp.Right(nLength - 1);
    sTemp.TrimLeft();
    nLength = sTemp.GetLength();
  }

  //Is the string too long?
  if (nLength > 29)
  {
    TRACE(_T("Decimal string was too long for conversion\n"));
    return FALSE;
  }

  //Iterate through each digit
  CInt96 t;
  for (int i=0; i<nLength; i++)
  {
    TCHAR c = sTemp.GetAt(i);

    if (c >= _T('0') && c <= _T('9'))
      t += CInt96(c - _T('0'));
    else
    {
      TRACE(_T("decimal string did not exclusively contain digits between 0 and 9\n"));
      return FALSE;
    }

    if (i<(nLength-1))
      t *= 10;
  }

  if (bNegative)
    t.Negate();

  *this = t;
  return TRUE;
}