数学计算的模拟类题目，往往是要求实现某种计算(比如两数相除)，实现的过程中会有所限定，比如不允许乘法等等。
这类题目首先要注意计算过程中本身的特殊情况。比如求相除，则必须首先反映过来除数不能为0。
其次要记得考虑负数的情况，如果计算范围不单单是整数，还要考虑double的比较方式。
最后要注意越界情况，这个是最容易犯错的，只能具体问题具体分析。
这道题来自于剑指Offer，为了归类，我把它放到了这里。
用位运算是第一反应，a^b可以算出当前位的结果， a&b可以算出是否进位。
但是接下来怎么办呢？
我的方法是，每次从两个数取一位，然后计算，进位。直到两个数都没有位可取了(往左看都只有0)，最后做一个进位。
我的代码：
#include <stdio.h>
int Sum(int a, int b){
int finalRes = 0;
int count = 0;
int prevAcc = 0, curAcc= 0;
int p = 0, q = 0;
int bitRes = 0;
while(a | b){
p = a&1; q = b&1;
a = a >> 1; b = b >> 1;
int temp = p ^ q;
curAcc = p & q;
bitRes = temp ^ prevAcc;
prevAcc = curAcc | (temp&prevAcc);
finalRes |= (bitRes << (count++));
}
finalRes |= prevAcc << count;
return finalRes;
}
// ====================测试代码====================
void Test(int num1, int num2, int expected)
{
int result = Sum(num1, num2);
if(result == expected)
printf("%d + %d is %d. Passed\n", num1, num2, result);
else
printf("%d + %d is %d. Failed\n", num1, num2, result);
}
int main()
{
Test(1, 2, 3);
Test(111, 899, 1010);
Test(5, 2, 7);
Test(1, 100, 101);
Test(3, 0, 3);
Test(0, 5, 5);
Test(2, 8, 10);
}白板一次error free bug free，但是，写到一半就明白这个解法是不全面的。。
因为没有考虑负数。
补码表示下的负数，并不能通过每次提取一位的方法来倒腾。
这种思路对于上次facebook的面试题倒是可以用，当时的题目是：两个只含有'0' '1'的字符串，计算两个字符串相加的结果。
在这种情况下，答案的解法确实让人佩服。
书上代码：
int Add(int num1, int num2)
{
int sum, carry;
do
{
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}
while(num2 != 0);
return num1;
}整体计算，carry表示各个位上计算后的进位，将carry左移一位，再加上sum，就是要求的结果。如何算carry和sum相加的结果呢？
同样可以利用上述方法。
循环思路出现。
循环终止条件是carry为0，也就是说，不再有进位了。
引申：
顺便提一提怎样在不定义新的变量的情况下交换两个int的方法。假设要交换a和b。
四则运算法，这个比较熟悉了。
a = a + b;
b = a - b;
a = a - b;
位运算法，不常用，但是更简单：
a = a ^ b;
b = a ^ b;
a = a ^ b;
我们需要的考虑的边界情况是：
1. 底数为0，指数为负数的情况。
2. 底数为零0，指数为0的情况。
情况2就是求0的0次幂，这个算是没有意义，返回0或者1均可，但是需要告知面试官你考虑到了，最好能打印出来这个情况。
同样，求幂时，我们没有必要使用时间复杂度为O(N)的连乘方式，这里N等于exponent的绝对值。而是可以使用递归的方式。
因为当n为偶数时，a^n = a^(n/2) * a^(n/2)；
当n为奇数时，a^n = a^((n-1)/2) * a^((n-1)/2) * a。
时间复杂度为O(logN)
最后，在判断底数是否为0时，不能使用base == 0的判定方式，因为double和float类型在存储时都有误差，判断两个数是否相等，只要两者之差小于一个极小值，即可认为两者相等。
代码分为三个函数，这样更加清晰：
bool equalJudgeDouble(const double a, const double b){
if((a - b) < 0.00001 && (a - b) > -0.00001)
return true;
else
return false;
}
double PowerWithUnsignedExponent(const double base, const unsigned int exp);
if(exp == 0){
return 1;
}
double temp = 0.0;
if(exp & 1 == 0){
temp = power(base, exp >> 1);
return temp * temp;
}else{
temp = power(base, (exp-1) >> 1);
return temp * temp * base;
}
}
double Power(const double base, const int exponent){
if(equalJudgeDouble(base, 0.0)){
if(exponent < 0);
throw new std::Exception("Can not work when exponent is negative and base is 0.");
return 0;
}
if(exponent < 0){
return 1.0 / PowerWithUnsignedExponent(base, (unsigned int)(-exponent));
}else if(exponent == 0){
return 1;
}else{
return PowerWithUnsignedExponent(base, exponent);
}
}Divide two integers without using multiplication, division and mod operator.
class Solution {
public:
int divide(int dividend, int divisor) {
}
};这道题相较于前一道稍复杂些。首先考虑divisor为0的情况，再考虑负数的情况。
接着考虑解体方法，由于乘除都不能用，只能用加法，而如果直接累加自然会超时。我的思路是定义一个长32的数组path[32]，path[0] = divisor, path[i] = path[i-1] + path[i-1]。path[32]不一定全被填满，当计算出path[i] > dividend时，path[i] 就不会被记录。由于path[i] 有大于 dividend的可能，因此临时存储计算结果的数定义为long long。
然后用这个path[32] 去凑成dividend，相除结果其实就是凑得过程中 1 << i 的相加(i 是 path[] 的 index)。
第一版代码如下：
class Solution {
public:
int divide(int dividend, int divisor) {
if(divisor == 0) return 0;
if(dividend == 0) return 0;
bool minus1 = false, minus2 = false, minus = false;
if(divisor < 0){
divisor = (0 - divisor);
minus1 = true;
}
if(dividend < 0){
dividend = (0 - dividend);
minus2 = true;
}
minus = (minus1 ^ minus2); //结果的正负号, minus若为true，结果就添加负号。
if(dividend < divisor) return 0;
long long cache = divisor;
int* path = new int[32];
int ind = 0;
for(; cache <= dividend; path[ind] = (int)cache, ++ind, cache += cache); //填充path[]
cache = path[--ind]; int res = 1 << ind; //从path的最末尾开始凑dividend
while(ind >= 0){
if(cache == dividend) return minus ? (0-res) : res;
if(cache > dividend){
cache -= path[ind];
res -= 1 << ind;
}
for(--ind; ind >= 0 && cache < dividend; cache += path[ind], res += 1 << ind);
}
return minus ? (0-res) : res;
}
};这版代码在执行 sln.divide(-1010369383, -2147483648) 出现错误。
原因在于 开始的
dividend = (0 - dividend);
补码表示下，int下限绝对值比上限绝对值大1。dividend = -2147483648时，0-dividend 结果并非是2147483648。因此dividend 和 divisor的绝对值应该用unsigned int 表示。
考虑到这一点，当dividend = -2147483648 时，res 和 path 也有越过 int上限的可能，因此它们应该定义为 unisgned int。
改进后的代码，改动了一些参数的 格式，这次AC了。
class Solution {
public:
int divide(int dividend, int divisor) {
if(divisor == 0) return 0;
if(dividend == 0) return 0;
bool minus1 = false, minus2 = false, minus = false;
unsigned int divd, divr;
if(divisor < 0){
divr = (0 - divisor);
minus1 = true;
}else{
divr = divisor;
}
if(dividend < 0){
divd = (0 - dividend);
minus2 = true;
}else{
divd = dividend;
}
minus = (minus1 ^ minus2); //结果的正负号, minus若为true，结果就添加负号。
if(divd < divr) return 0;
long long cache = divr;
unsigned int* path = new unsigned int[32];
int ind = 0;
for(; cache <= divd; path[ind] = (unsigned int)cache, ++ind, cache += cache); //填充path[]
cache = path[--ind]; unsigned int res = 1 << ind; //从path的最末尾开始凑dividend
while(ind >= 0){
if(cache == divd) return minus ? (0-res) : res;
if(cache > divd){
cache -= path[ind];
res -= 1 << ind;
}
for(--ind; ind >= 0 && cache < divd; cache += path[ind], res += 1 << ind);
}
return minus ? (0-res) : res;
}
};