Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

I. Problem description

Design a function to add two numbers. Do not use + or other arithmetic operators.

Addition without the plus sign.

Two, the title requirements

The sample

Input: A = 11, b = 13 Output: 24Copy the code

inspection

2. It is recommended to take 10 to 30 minutesCopy the code

Third, problem analysis

10. If you don’t know about bit operations, you can read this article in detail.

Day 45: Bit operation.

At first, I did not think of it. Later, when I looked at the solution of the problem, I found an interesting answer:

class Solution {
public:
    int add(int a, int b) {
        returna-(-b); }};Copy the code

I was shocked. There was no addition!

So without further ado, let’s get started! This problem to use in place operation inside the xor, with, shift calculation, this part of the knowledge above the article link inside have, I will simply talk about.

Take an example:

11-> Binary: 1011 13-> binary: 1101 XOR: 0110 and: 1001 The result of the pair moves to the left: 10010Copy the code

The xOR addition operation can only calculate the operation where one position is 0 and the other position is 1. If both positions are 1, then the result that should be carried will become 0 later. This defect needs to be remedied.

And in this case, for example, 101^101=101, you just have to move one carry to the left to get 1010, carry done

When there is no carry, then the xor grand method is done.

Let me write the steps in detail. A =a^b represents the operation, and b=(a&b)<<1 represents the carry:

a   0110    10100    10000    11000
b   10010   100      1000     0000
Copy the code

When b is equal to 0, the output.

Four, coding implementation

class Solution {
public:
    int add(int a, int b) {
        if(b == 0)// Carry no, output result
            return a;
        else// recursive operation
            return add(a^b, ((unsigned int)a&b)<<1); }};Copy the code

An unsigned int represents an unsigned bit. This bit must be added to an unsigned bit or a negative number will be treated with an error.

V. Test results