剑指offer-不用加减乘除做加法

Topic describes

Topic describes

Nowcoder Link

Train of thought

When we have a problem where we are not allowed to use the four operations, our first thought must to do it with bitwise operations.

this question we need two operations, 1. xor(^) 2. and(&)

what's xor

Exclusive disjunction(also called exclusive or, XOR) essentially means either one, but not both nor none. In other words, the statement is true , If and only if one is true and the other is false.

0 ^ 0 -> 0
0 ^ 1 -> 1
1 ^ 0 -> 1
1 ^ 1 -> 0

what's and

If both values ​​are all 1, the result is 1, otherwise it is 0

0 ^ 0 -> 0
0 ^ 1 -> 0
1 ^ 0 -> 0
1 ^ 1 -> 1

Let's show a example

example

Through this example, we know use xor(^) we can calculate the result but no carry, and use and(&) we can calculate the carry, so we have a solution, we can let number1 ^ number2 get the no carry result, and let number1 & number2 get the carry, and let the two result add(not real add, only repeat the above operation) until to number2 is 0(no carry)

Let's see the other example, we want to know 5 + 7 (we know the result is 12 (1100)):

1. we know 5 is 101, and 7 is 111
2. calculate 101 ^ 111 -> 010 (no carry result)
   calculate 101 & 111 << 1 -> 1010 (carry result)

 let no carry result add carry result (010 + 1010) (repeat the above action)

3. calculate 010 ^ 1010 -> 1000
   calculate 010 & 1010 << 1 = 100

 let no carry result add carry result (1000 + 100) (repeat the above action)

4. calculate 1000 ^ 100 = 1100
   calculate 1000 & 100 = 0

carry is 0, so 1100 is the last result

the result is 1100

so our code is :

public int Add(int num1, int num2) {
        while (num2 != 0) {
            int temp = num1 ^ num2;
            num2 = (num1 & num2) << 1;
            num1 = temp;
        }
        return num1;
    }