Doing something you intrinsically are enthusiastic with.

2016年8月3日 星期三

Leetcode- Sum of two integer

上午10:47 Posted by Unknown No comments
Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.
Example:
Given a = 1 and b = 2, return 3.

Solution: bit-wise manipulation
Here are two integers a and b, if there is no carry occurring in the process then  a+b=ab,Here  represents the XOR. The Carry bits appears when 1+1 so the carry bits of a+b can be represented as  2×(a & b),& means AND operation, multiply 2 to shift left.

After N times of operation, the carry bit would be 0 then we can return the result;

The program can be easily written in recursive form

int getSum(int a, int b) { if(a == 0) return b; int x = a ^ b; int c = (a & b) << 1; return getSum(c, x); }


x0+c0

0 意見:

張貼留言