C++之竹

无论是太阳下,还是风雨中,都要成长!

常用链接

统计

最新评论

不使用 +-×÷ 运算符来实现 加减乘除 四项运算

最近,在看《剑指Offer——名企面试官精讲典型编程题》一书,当看到“面试题47:不用加减乘除做加法”时,经过一分钟左右思考后,得出了思路,跟书上一对照,基本一致,呵呵O(∩_∩)O~。于是,随即又开始思考:加法是实现了,那么减法、乘法还有除法又该怎么实现呢?一番思考与分析后,得出算法,写出代码,测试通过,Happy!!\(^o^)/~

 接下来,就将我的算法与代码展示如下,还请有更好算法的牛人不吝赐教!!

 

【1. 加法】

 因本人的算法与《剑指Offer——名企面试官精讲典型编程题》中一致,就不做赘述,而只贴出代码。

代码1.1 加法:计算a+b

int Add(int a, int b)
{
    
int sum = a ^ b;
    
int carry = a & b;
    
while (carry != 0{
        a 
= sum;
        b 
= carry << 1;
        sum 
= a ^ b;
        carry 
= a & b;
    }


    
return sum;
}

【2. 减法】

方案一:通过Add函数的实现

按常规思路,根据加减运算的互反性(即,减去一个数等于加上这个数的相反数),然后利用前面已实现的Add函数来进行实现。

按这个思路,我们首先要做到对一个整数取相反数,不能使用运算符“-”,那么就只能根据C++上两个互为相反数的int型数据的二进制结构关系——整数的相反数等于该数按位取反再加1,来设计如下的函数了。

代码2.1 取整数n的相反数

int OppositeNumber(int n)
{
    
return Add(~n, 1);
}

然后就可以通过Add函数来实现减法了。

代码2.2 减法一:计算a-b

int Subtract(int a, int b)
{
    
return Add(a, OppositeNumber(b));
}

毕竟是作为对思维开放的一个锻炼,所以对于直接的减法算法的思考还是值得的。于是就有了下面的方案二。

方案二:直接通过位操作实现减法

算法是得通过二进制位计算来实现的,所以在分析减法时从二进制减法计算的角度去考虑将更合适。那么,两个二进制形式整数的减法操作又是怎样进行的呢?

  1. 首先,如果减数为0,则被减数即为减法的结果,运算结束。
    但如果减数不为0,我们可以先把被减数和减数上同为1的位从两个数上去除。至于如何分离出值同为1的位,则可以通过求位与操作来做到;而把这些1分别中被减数和减数中去除,则可以通过按位异或来的操作来实现。
  2. 经步骤1处理后,被减数和减数在对应的位上,将或者通为0,或者分别为0和1,却不会同为1。此时:
    如果对应位被减数=1,而减数=0,则所得结果对应位也为1;
    如果对应位被减数=0,而减数=1,则所得结果对应位还是1,但此时须向前一位借1;
    即,通过被减数与减数作位异或的操作得到临时结果,和通过对减数左移一位得到需从临时结果中减去的借数。
  3. 于是,经过步骤2后,原来的减法变成了要求:临时结果 - 借数
    很明显,只要以临时结果为被减数,借数为减数,重复步骤1~3即可。

上述步骤中,如果被减数或减数为负数,由负数的二进制位结构,可以保证上述步骤的处理仍适用,证明过程就请恕我在这里略去了。具体的实现代码如下。

代码2.3 减法二:计算a-b

int Subtract(int a, int b)
{
    
while (b != 0
    
{
        
int sameBits = a & b;
        a 
^= sameBits;
        b 
^= sameBits;
        a 
|= b;
        b 
<<= 1;
    }


    
return a;
}

※注:上述加法和减法中,按代码安全性,其实还应考虑计算后数据溢出的情况,这里我偷了下懒,省去了。不过下面的乘除法,我会提供包含了异常处理的代码。异常处理的方式,我采用了throw抛出的方式。

 【3. 乘法】

为了方便对数据溢出的统一处理,在进行计算前,我先保存了被乘数与乘数的符号信息,并当被乘数或乘数为负时,利用上面的OppositeNumber函数,统一的转换为正整数(或0),然后再来进行乘法的运算。为了能同时适应32位和64位的整形数,在取符号信息与设置溢出判断位时,使用了以下的辅助宏和函数。

代码3.1 辅助宏与辅助函数

#define BITS_OF_ONE_BYTE     8
#define SIGN_BIT_FLAG_FOR_BYTE   0x80     // for signed byte/char

int SignBitFlagOfInt()
{
    
static int signBitFlag = 0;

    
static bool bIs1stCalled = true;
    
if (bIs1stCalled)
    
{
        
int temp = SIGN_BIT_FLAG_FOR_BYTE;
        
while (temp != 0
        
{
            signBitFlag 
= temp;
            temp 
<<= BITS_OF_ONE_BYTE;
        }

        bIs1stCalled 
= false;
    }


    
return signBitFlag;
}

乘法的算法。考虑到:

  1. 整数n乘以2k == n << k
  2. C++中的任何一个非负int型数据都可以表示为如下的形式:
    k0×20+k1×21+...+km×2m
    的形式。(其中:ki∈{0, 1}, i∈{0, 1, ... , m}, 32位int型m = 30, 64位int型m = 62)

于是,就可以利用乘法分配率,通过循环累加,进行乘法的运算了。参考代码3.2。

代码3.2 乘法:计算a×b

int Multiply(int a, int b)
{
    
int signStatA = a & SignBitFlagOfInt();
    
if (signStatA != 0)
    
{
        a 
= OppositeNumber(a);
    }


    
int signStatB = b & SignBitFlagOfInt();
    
if (signStatB != 0)
    
{
        b 
= OppositeNumber(b);
    }


    
int overFlowFlag = SignBitFlagOfInt(); // used for checking if the signed int data overflowed.
    int product = 0// the result of |a| * |b|
    for (int curBitPos = 1; curBitPos != 0; curBitPos <<= 1)
    
{
        
if ((b & curBitPos) != 0)
        
{
            product 
= Add(product, a);
            
if (((a & overFlowFlag) != 0
                
|| ((product & overFlowFlag) != 0))
            
{
                
throw std::exception("The result data war overflowed.");
            }

        }

        a 
<<= 1;
    }


    
return ((signStatA ^ signStatB) == 0? product : OppositeNumber(product);
}

【4. 除法】

整数的除法,不同于乘法,除法所得的商的绝对值必然不大于被除数的绝对值,而所得余数的绝对值则必然小于除数的绝对值。所以,在设计除法函数的时候,无需考虑数据溢出的问题。但对于除法,却也有它自己的禁忌——除数不能为“0”。

为了处理的方便,准备工作同乘法一样,记录下被除数与除数的符号状态(比便在计算出结果后进行符号的调整),并当被除数或除数为负时,通过函数OppositeNumber将其转换为相反数。于是,接下来,我就只需考虑“非负整数(>=0)÷正整数(>0)”的情况了。对这种情况,计算过程如下:

  1. 预备工作:置商为0;
  2. 判断“被除数>=除数 ”是否成立:
    成立,继续步骤3;
    不成立,被除数的值赋给余数,计算结束。
  3. 备份除数,并设置商分子(一个临时变量,最终需加到商上面,故暂且如此命名)为1;
    对商分子和除数同步向左移位,直到继续移位将大于被除数时为止;
  4. 从被除数上减去除数,并将商加上商分子。
  5. 通过备份的除数值还原除数,跳转到步骤2继续执行。

对应的代码参加代码4.1。

代码4.1 除法:计算a÷b 

int Divide(int a, int b, int * pRem /*= NULL*/)
{
    
if (b == 0)
    
{
        
throw std::exception("Invalid divisor!! (The divisor can't be 0!)");
    }


    
int signStatA = a & SignBitFlagOfInt();
    
if (signStatA != 0)
    
{
        a 
= OppositeNumber(a);
    }


    
int signStatB = b & SignBitFlagOfInt();
    
if (signStatB != 0)
    
{
        b 
= OppositeNumber(b);
    }


    
int quotient = 0;
    
int backupB = b;
    
while (a >= b) 
    
{
        
int tempB = b << 1;
        
int tempQ = 1;
        
while ((tempB <= a) && ((tempB & SignBitFlagOfInt()) == 0))
        
{
            b 
= tempB;
            tempQ 
<<= 1;
            tempB 
<<= 1;
        }


        a 
= Subtract(a, b);
        quotient 
|= tempQ;
        b 
= backupB;
    }


    
if (pRem != NULL)
    
{
        
*pRem = a;
    }


    
if ((signStatA != 0&& (a != 0))
    
{
        quotient 
= Add(quotient, 1);
        
if (pRem != NULL)
        
{
            
*pRem = Subtract(b, *pRem);
        }

    }


    
return ((signStatA ^ signStatB) == 0? quotient : OppositeNumber(quotient);
}

※注:函数的返回值即为所求的商;
       参数pRem为余数的传出参数,其默认值NULL,表示当前无需关注余数。

 

posted on 2012-03-30 01:30 青碧竹 阅读(4916) 评论(7)  编辑 收藏 引用 所属分类: 算法相关

评论

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-03-30 13:02 远行

搜了下那本书,发现好像没出版,lz有那本书的文档能不能发一份啊,
爱好书之情难自抑啊。。。  回复  更多评论   

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-03-30 14:40 FiO

@远行
http://book.douban.com/subject/6966465/  回复  更多评论   

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-03-30 18:26 远行

没钱买书,只看电子版。。。@FiO
  回复  更多评论   

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-03-30 19:24 flyinghearts


严格的讲,这些方法只能用于无符号数。对有符号数这样的做法是不通用的。 google 一补数。

  回复  更多评论   

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-03-30 19:49 青碧竹

@flyinghearts
在目前计算机内负整数通过对其绝对值进行求反+1来存储的前提下,这些算法完全适用于有符号整数。  回复  更多评论   

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-03-31 13:15 SwordLance

这类问题,只要知道CPU的运算器是怎么做的,用程序模拟即可。  回复  更多评论   

# re: 不使用 +-×÷ 运算符来实现 加减乘除 四项运算 2012-04-01 00:13 青碧竹

@SwordLance
是的。  回复  更多评论   


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理