不用四则运算做加法
题目描述
写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。
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++;
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
start = mid + 1;
else
return mid;
}
return end;
}
};
