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.
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=a⊗b ,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.
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); }
0 意見:
張貼留言