【出自WR面试题】
难度系数：★★★★☆ 被考察系数：★★★☆☆
分析与解答：
方法一：减法
主要思路是：使被除数不断减去除数，直到相减的结果小于除数为止，此时，商就为相减的次数，余数为最后相减的差。例如在计算14除以4的时候，首先计算14-4=10，由于10＞4，继续做减法运算：10-4=6，6-4=2，此时2＜4。由于总共进行了3次减法操作，最终相减的结果为2，因此，15除以4的商为3，余数为2。如果被除数比除数都小，那么商为0，余数为被除数。根据这个思路的实现代码如下：
程序的运行结果如下：
14除以4商为：3余数为2
算法性能分析：
这种方法循环的次数为m/n，因此算法的时间复杂度为O（m/n）。需要注意的是，这种方法也实现了不用%操作符实现%运算的目的。
方法二：移位法
方法一所采用的减法操作，还可以用等价的加法操作来实现。例如在计算17除以4的时候，可以尝试4*1，4*2（4+4），4*3（4+4+4）依次进行计算，直到计算的结果大于14的时候就可以很容易地求出商与余数。但是这种方法每次都递增4，效率较低。下面给出另外一种增加递增速度的方法：以2的指数进行递增（取2的指数的原因是，2的指数操作可以通过移位操作来实现，有更高的效率），计算4*1，4*2，4*4，4*8，由于4*8＞17，然后接着对17-4*4=1进入下一次循环用相同的方法进行计算。实现代码如下：
算法性能分析：
由于这种方法采用指数级的增长方式不断逼近m/n，因此算法的时间复杂度为O（log（m/n））。
引申一：如何不用加减乘除运算实现加法
分析与解答：
由于不能使用加减乘除运算，因此只能使用位运算了。首先通过分析十进制加法的规律来找出二进制加法的规律，从而把加法操作转换为二进制的操作来完成。
十进制的加法运算过程可以分为以下3个步骤：
（1）各个位相加而不考虑进位，计算相加的结果sum。
（2）只计算各个位相加时进位的值carry。
（3）将sum与carry相加就可以得到这两个数相加的结果。(www.xing528.com)
例如15+29的计算方法为sum=34（不考虑进位），carry=10（只计算进位），因此，15+29=sum+carry=34+10=44。
同理，二进制加法与十进制加法有着相似的原理，唯一不同的是，在二进制加法中，sum与carry的和可能还有进位，因此在二进制加法中会不停地执行sum+carry操作，直到没有进位为止。具体实现方法如下：
（1）二进制各个位相加而不考虑进位。由于在不考虑进位的时候加法操作可以用异或操作代替，因此，不考虑进位的加法可以用异或运算来代替。
（2）计算进位，由于只有1+1才会产生进位，因此进位的计算可以用与操作代替。进位的计算方法为：先做与运算，再把运算结果左移一位。
（3）不断对（1）、（2）两步得到的结果相加，直到进位为0的时候为止。
根据这个思路实现代码如下：
程序的运行结果为
6
引申二：如何不用加减乘除运算实现减法
分析与解答：
由于减去一个数等于加上这个数的相反数，即-n=～（n-1）=～n+1，因此，a-b=a+（-b）=a+（～b）+1，可以利用上面已经实现的加法操作来实现减法操作，实现代码如下：
引申三：如何不用加减乘除运算实现乘法
分析与解答：
以11*14为例介绍乘法运算的规律，11的二进制可以表示为1011，14的二进制可以表示为1110，二进制相乘的运算过程如下：
二进制数10011010的十进制表示为154=11*14，从这个例子可以看出，乘法运算可以转换为加法运算。计算a*b的主要思路是：（1）初始化运算结果为0，sum=0。（2）找到b对应二进制中最后一个1的位置i（位置编号从右到左依次为0，1，2，3…），并去掉这个1。（3）执行加法操作sum+=a＜i。（4）循环执行（1）、（2）和（3）步，直到b对应的二进制数中没有更多的1为止。
从6.2节中可知，对n执行n&（n-1）操作可以去掉n的二进制数表示中的最后一位1，因此n&～（n-1）的结果为只保留n的二进制数中的最后一位1。因此可以通过n&～（n-1）找出n中最后一个1的位置，然后通过n&（n-1）去掉最后一个1。在上述的第（2）步中，首先执行lastBit=n&～（n-1），得到的值lastBit只包含n对应的二进制表示中最后一位1，要想确定1的位置，需要通过对1不断进行左移操作，直到移位的结果等于lastBit时移位的次数就是位置编号。在实现的时候，为了提高程序的运行效率，可以把1向左移动的位数（0，1，2，3…31）先计算好并保存起来。实现代码如下：
引申四：另外一种除法的实现方式
分析与解答：
由于除法是乘法的逆运算，因此，可以很容易地将除法运算转换为乘法运算，实现代码如下：
免责声明：以上内容源自网络，版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。
