Sword finger offer 65 Add without adding, subtracting, multiplying, dividing

️ The finger of the sword  Offer 65.  Do not add, subtract, multiply or divide ️

Topic details

Write a function , Find the sum of two integers , It is required that... Should not be used in the function body  

Four operation symbols .

Example ：

Input : a = 1, b = 1
Output : 2
Input : a = 5, b = 6
Output : 11


Tips ：

• a, b  Both can be negative or  0.

• The result won't spill  32  An integer .

Their thinking

Method 1： You said you can't use the addition, subtraction, multiplication and division operator ？ I have to use , Add the two numbers directly to return .

Method 2： An operation .

Preliminary knowledge ：

• [x]  Bitwise AND  & ： Binocular operator , Take and... For each , All for 1 Then for 1, Otherwise 0.

• [x]  Bitwise XOR  ^ ： Binocular operator , Take XOR for each , If the corresponding two numbers are different, they are 1, Otherwise 0.

• [x]  Move left  << ： Binocular operator ,a << b , It means that you will a The binary bit of is shifted left b position , Rightmost complement 0.

• [x]  Characteristics of additive carry ： For binary , The condition of carry is that the binary bits corresponding to two numbers are 1.

Their thinking ：

Realization a,b The steps of complete addition of two numbers ：

• take a And b Press and and move left one bit , namely (a & b) << 1, You might as well save this result in a variable tmp, If the value is 0, It means that there is no carry of two numbers .

• take a And b Perform non carry addition , namely a ^ b, You might as well assign this result to a, Take the above tmp The value assigned to b.

• here b The value of is tmp, Judge b Is it 0, if b Not for 0, Carry required , Repeat the above steps , Carry the number b Non carry addition to the value of the previous non carry addition , if b by 0, There is no need to carry , The addition process ends , The end result is a Value .

Be careful ：C/C++ There is an overflow on the left shift of negative numbers , First the  a & b  Forced to  unsigned int  To protect the left shift overflow ！

Source code

Java:

class Solution {
 public int getSum(int a, int b) {
 // The XOR of two numbers is equivalent to adding without carry , The bitwise sum operation of two numbers can get the number that needs to be carried , Move this number to the left and add XOR , Until the number is 0, The addition is done
 while (b != 0) {
 int tmp = (a & b) << 1;
 a ^= b;
 b = tmp;
 }
 return a;
 }
}


C:

int getSum(int a, int b){
 while (b) {
 int tmp = (unsigned int)(a & b) << 1;//C/C++, In the case of negative numbers , Overflow exists for the left shift of signed number , First turn to unsigned and then move left to protect overflow
 a ^= b;
 b = tmp;
 }
 return a;
}


C++:

class Solution {
public:
 int getSum(int a, int b) {
 while (b) {
 int tmp = (unsigned int)(a & b) << 1;
 a ^= b;
 b = tmp;
 }
 return a;
 }
};


summary

Do not add, subtract, multiply or divide , The easiest way to think of is bit operation , By understanding the characteristics of various bit operations , Find out the appropriate method of analog addition . Force deduction homologous problem ：

371.  Sum of two integers

Interview questions  17.01.  Add without a plus sign

Force deduction similar questions ：

Interview questions  08.05.  Recursive multiplication

29.  Divide two numbers

50. Pow(x, n)

69. Sqrt(x)

Interview questions  16.07.  Maximum value