371. Sum of two integers

Small knowledge, big challenge! This article is participating in the creation activity of “Essential Tips for Programmers”.

Given two integers A and b, without using the operators + and -, compute and return the sum of the two integers.

Thought analysis

So this is kind of an interesting problem, so you should learn a little bit more about CSAPP, and it’s intuitive to use bitwise operations.

0 + 0 = 0 0 + 1 = 1 1 + 0 = 1 1 + 1 = 0Copy the code

In general, if we don’t worry about carrying, we can just use a xor b to get the result,

However, in the case of carrying, we need to further calculate the carry on the basis of A xOR b, and add the results of the carry to the original sum.

There are:

0 + 0 = 0, 0 + 1 = 0, 1 + 0 = 0, 1 + 1 = 1Copy the code

It is obviously a&b, but the result of the round is a&b << 1.

But you have to take into account the fact that you add the carries, so you have to keep iterating until the carry is zero, and you have this code:

int getSum(int a, int b) {
    while(b ! =0) {
        int carry = (int)(a & b) << 1;
        a = a ^ b;
        b = carry;
    }
    return a;
}
Copy the code

conclusion

Say in place operation, also mentioned CSAPP, might as well borrow flower xiandao Buddha to show you the next topic readers.

1, a^b without xOR

The formula is derived from the equation.

The answer:

1.(a|b)&(~a|~b)
2.~(~a&~b)&~(a&b)
3.(a&~b)|(~a&b)
Copy the code

int bitXor(int x, int y) {
  return ~(~x&~y)&~(x&y);
}
Copy the code

371. Sum of two integers