不用四则运算做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

class Solution {
public:
    int Add(int num1, int num2)
    {
        int sum;
        int carry;
        while(num2)
        {
            sum = num1^num2;   //换了种形式而已，sum + carry = num1 + num2
            carry = (num1&num2)<<1;
            num1 = sum;  
            num2 = carry;
        }
        return num1;
    }
};

**29. Divide Two Integers **
Divide two integers without using multiplication, division and mod operator.
If it is overflow, return MAX_INT.
代码如下：

class Solution {
public:
    int divide(int dividend, int divisor) {
        long a = abs((long)dividend);
        long b = abs((long)divisor);
        long result = 0;
        while(a>=b) //减到最后的余数小于b为止
        {
            long c = b;  //一轮一轮的减
            int i = 0;
            while(a>=c)
            {
                a = a - c;
                result += 1<<i;
                i++;
                c = c<<1;
            }
        }
        if((dividend>0&&divisor<0)||(dividend<0&&divisor>0))
          result = -result;
        return (int)result;  
    }
};

**50. Pow(x, n) **
Implement pow(x, n).
代码如下：

class Solution {
public:
    double myPow(double x, int n) {
        int flag = 1;
        if(x>-0.000001&&x<0.000001)
          return 0;
        if(n==0)
          return 1;
        if(n<0)
          flag = -1;
        
        if(n%2==0)
        {   if(flag>0)
              return myPow(x,(flag*n)/2)*myPow(x,(flag*n)/2);
            else
              return 1/(myPow(x,(flag*n)/2)*myPow(x,(flag*n)/2));
        }

        else
        {
            if(flag>0)
              return x*myPow(x,((flag*n)-1)/2)*myPow(x,((flag*n)-1)/2);
            else
              return 1/(x*myPow(x,((flag*n)-1)/2)*myPow(x,((flag*n)-1)/2));
        }
    }
};

**69. Sqrt(x) **
Implement int sqrt(int x).
Compute and return the square root of x.

class Solution {
public:
    int mySqrt(int x) {
        if(x<=0)
          return 0;
        
        int start = 1;
        int end = x;
        int mid = 0;
        while(start<=end)
        {
            mid = (start + end)>>1;
            if(mid>x/mid)
              end = mid - 1;
            else if(mid<x/mid)
              start = mid + 1;
            else
              return mid;
        }
        return end;
    }
};