📄 hugeinteger.cpp
字号:
if(left == 0 || right == 0 || Abs(left) < Abs(right))
return 0;
/************************************************
* 用位串方式实现除法:
* 计算方法根手算一样，只不过当作二进制数运算。
*************************************************/
int lbitnum = left.GetBitNum();
int rbitnum = right.GetBitNum();
int index = lbitnum - rbitnum;
CHugeInteger divided = left.ExtractBits(lbitnum - 1, lbitnum - rbitnum);
CHugeInteger divider = Abs(right);
while(index >= 0){
if(divided >= divider){
result = result * 2 + 1; // 后面补1
divided -= divider;
}
else{
result *= 2; // 后面补0
}
index--;
if(index >= 0){
if(left.GetBit(index)){
divided = divided * 2 + 1;
}
else{
divided *= 2;
}
}
}
// 确定结果正负号
if(left.m_nSign == right.m_nSign){
result.m_nSign = 1;
}
else{
result.m_nSign = -1;
}
return result;
}
/*******************************************************\
* 函数：operator /= () *
* 功能：计算两个数的相除的商 *
* 输入：right --- 除数 *
* 输出：无 *
* 返回：*this,商 *
\*******************************************************/
CHugeInteger& CHugeInteger::operator /= (unsigned int right)
{
*this = *this / right;
return *this;
}
CHugeInteger& CHugeInteger::operator /= (CHugeInteger& right)
{
*this = *this / right;
return *this;
}
/*******************************************************\
* 函数：operator % () *
* 功能：计算两个数的相除的余数 *
* 输入：right --- 除数 *
* 输出：无 *
* 返回：余数 *
\*******************************************************/
CHugeInteger CHugeInteger::operator % (CHugeInteger& right)
{
return *this - (*this / right) * right;
}
int CHugeInteger::operator % (unsigned int right)
{
CHugeInteger div = *this / right;
CHugeInteger minus = *this - (div * right);
int lResult = minus.m_ulValue[0];
if( minus.m_nSign < 0 ){
lResult = 0 - lResult;
}
return lResult;
}
/*******************************************************\
* 函数：operator %= () *
* 功能：计算两个数的相除的余数 *
* 输入：right --- 除数 *
* 输出：无 *
* 返回：*this,余数 *
\*******************************************************/
CHugeInteger& CHugeInteger::operator %= (CHugeInteger& right)
{
*this = *this - (*this / right) * right;
return *this;
}
CHugeInteger& CHugeInteger::operator %= (unsigned int right)
{
CHugeInteger div = *this / right;
*this = *this - (div * right);
return *this;
}
/*******************************************************\
* 函数：operator ^= () *
* 功能：计算以该整数为底的幂指数 *
* 输入：right --- 指数 *
* 输出：无 *
* 返回：幂指数值 *
\*******************************************************/
CHugeInteger CHugeInteger::operator ^ (unsigned int right)
{
CHugeInteger result;
if(right == 0){
result = 1;
}
else if(right == 1){
result = *this;
}
else{
result = (*this) ^ (right / 2);
result *= result;
if(right % 2 == 1){
result *= *this;
}
}
return result;
}
/*******************************************************\
* 函数：operator ^= () *
* 功能：计算以该整数为底的幂指数 *
* 输入：right --- 指数 *
* 输出：无 *
* 返回：*this,幂指数值 *
\*******************************************************/
CHugeInteger& CHugeInteger::operator ^= (unsigned int right)
{
*this = *this ^ right;
return *this;
}
/*******************************************************\
* 函数：Factorial() *
* 功能：计算阶乘 *
* 输入：n --- 整数 *
* bDouble --- 是否为双阶乘 *
* 输出：无 *
* 返回：阶乘值 *
\*******************************************************/
CHugeInteger CHugeInteger::Factorial(unsigned int n, bool bDouble)
{
CHugeInteger result = 1;
for(unsigned int i = n; i >= 2; i--){
if(bDouble && ((n - i) % 2) != 0){
continue;
}
result *= i;
}
return result;
}
/*******************************************************\
* 函数：Abs() *
* 功能：取整数的绝对值 *
* 输入：n --- 整数 *
* 输出：无 *
* 返回：绝对值 *
\*******************************************************/
CHugeInteger CHugeInteger::Abs(CHugeInteger& n)
{
CHugeInteger result = n;
if(result.m_nSign != 0)
result.m_nSign = 1;
return result;
}
/*******************************************************\
* 函数：Compare() *
* 功能：比较两个整数的大小 *
* 输入：hInteger --- 被比较的整数 *
* 输出：无 *
* 返回：1 --- *this > hInteger *
* 0 --- *this == hInteger *
* -1 --- *this < hInteger *
\*******************************************************/
int CHugeInteger::Compare(CHugeInteger& hInteger)
{
if(m_nSign > hInteger.m_nSign){
return 1;
}
else if(m_nSign < hInteger.m_nSign){
return -1;
}
else{ // 符号相同
if(m_nLength > hInteger.m_nLength){
return 1 * m_nSign;
}
if(m_nLength < hInteger.m_nLength){
return -1 * m_nSign;
}
else{ // 长度相同
for(int i = m_nLength-1; i >= 0; i--){
if(m_ulValue[i] > hInteger.m_ulValue[i]){
return 1 * m_nSign;
}
if(m_ulValue[i] < hInteger.m_ulValue[i]){
return -1 * m_nSign;
}
}
return 0;
}
}
}
/*******************************************************\
* 函数：GetBitNum() *
* 功能：获取该整数的位数(不考虑)正负号 *
* 输入：无 *
* 输出：无 *
* 返回：位数 *
\*******************************************************/
int CHugeInteger::GetBitNum()
{
if(m_nSign == 0){
return 0;
}
else{
int lBitNum = m_nLength * sizeof(unsigned int) * 8;
while(lBitNum > 0){
if(GetBit(lBitNum - 1)){
return lBitNum;
}
lBitNum--;
}
return 0;
}
}
/*******************************************************\
* 函数：GetBit() *
* 功能：获取该整数的某位的值 *
* 输入：bitIndex --- 位序号(从右往左0,1,2...) *
* 输出：无 *
* 返回：true --- 该位为1 *
* false --- 该位为0 *
\*******************************************************/
bool CHugeInteger::GetBit(unsigned int bitIndex)
{
unsigned int value = 1;
value = value << ( bitIndex % BITNUM_UINT );
if( value & m_ulValue[bitIndex / BITNUM_UINT] ){
return true;
}
else{
return false;
}
}
/*******************************************************\
* 函数：SetBit() *
* 功能：设置该整数某位的值 *
* 输入：bitIndex --- 位序号(从右往左0,1,2...) *
* bSet --- bit value 1 or not *
* 输出：无 *
* 返回：位数 *
\*******************************************************/
void CHugeInteger::SetBit(unsigned int bitIndex, bool bSet)
{
unsigned int value = 1;
if(!bSet){
value = 0;
}
value = value << (bitIndex % BITNUM_UINT);
m_ulValue[bitIndex / BITNUM_UINT] |= value;
if( (bitIndex / BITNUM_UINT) > (m_nLength - 1) ){
m_nLength = bitIndex / BITNUM_UINT + 1;
}
}
/*******************************************************\
* 函数：ExtractBits() *
* 功能：从该整数中抽取一部分位串，作为一个新整数 *
* 输入：lindex --- 左端位序号(从右往左0,1,2...) *
* rindex --- 右端位序号(从右往左0,1,2...) *
* bSign --- 是否保留原整数的正负号 *
* 输出：无 *
* 返回：新整数 *
\*******************************************************/
CHugeInteger CHugeInteger::ExtractBits(int lindex,
int rindex, bool bSign)
{
if(lindex < rindex)
return 0;
CHugeInteger result = 0;
for(int i = lindex ; i >= rindex; i--){
result.SetBit(i - rindex, this->GetBit(i));
}
if(bSign){
result.m_nSign = this->m_nSign;
}
else{
result.m_nSign = 1;
}
return result;
}
/*******************************************************\
* 函数：Format() *
* 功能：将整数格式化输出 *
* 输入：system --- 按几进制输出(2,8,10,16等) *
* 输出：strOutText --- 输出字符串 *
* 返回：true --- 输出成功 *
* false --- 输出失败(参数错误) *
\*******************************************************/
bool CHugeInteger::Format(string& strOutText, unsigned int system)
{
if( system > 16 ){
return false;
}
strOutText = "";
CHugeInteger temp = *this;
CHugeInteger zero = 0;
if( temp == zero ){
strOutText = "0";
return true;
}
while( temp > zero ){
int mod = temp % system;
temp = temp / system;
switch(mod){
case 0: strOutText = "0" + strOutText; break;
case 1: strOutText = "1" + strOutText; break;
case 2: strOutText = "2" + strOutText; break;
case 3: strOutText = "3" + strOutText; break;
case 4: strOutText = "4" + strOutText; break;
case 5: strOutText = "5" + strOutText; break;
case 6: strOutText = "6" + strOutText; break;
case 7: strOutText = "7" + strOutText; break;
case 8: strOutText = "8" + strOutText; break;
case 9: strOutText = "9" + strOutText; break;
case 10: strOutText = "A" + strOutText; break;
case 11: strOutText = "B" + strOutText; break;
case 12: strOutText = "C" + strOutText; break;
case 13: strOutText = "D" + strOutText; break;
case 14: strOutText = "E" + strOutText; break;
case 15: strOutText = "F" + strOutText; break;
default: break;
}
}
if( m_nSign < 0 ){
strOutText += "-";
}
return true;
}
void CHugeInteger::Print()
{
string str;
Format(str);
printf("%s", str.c_str());
}
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -