Add unsigned numbers without using '+' or '++'

Question

I need to add 2 unsigned numbers 'a' and 'b'.

I found the following code using bit operations

unsigned int add (unsigned int a,unsigned int b) { unsigned int carry, sum; if (b == 0) { return a; } sum = a ^ b; // xor takes sum carry = a & b; // collect carry; carry = carry << 1; return ( add (sum, carry) ); } 

I can't figure out how this code adds two numbers.

Any help / referral of people.

Answer 1

Logic : the code implements a series of semi-additions and distributes the transfer from one of them to the next through recursion. Take a look at dry run for an example of how this works.

Consider these two values a=0011 and b=0101 . At base 10, they are a=3 and b=5 respectively.

Now a^b=0110 ( 1 only when one bit is 1 ), and a&b=0001 ( 1 only when both bits are equal to one, the only case where you can have a carry).

Then you need to move the transfer to the next bit, so you have the operation <<1 , creating carry=0010 .

Now you need to add 0110 and 0010 using the above algorithm. This will turn into the addition of 0100 and 0100 . This will add 0000 with 1000 , which will add 1000 with 0000 , which will end through the base register ( b == 0 ).

In tabular form:

 | a | b | a^b | a&b | carry| ------------------------------------ | 0011 | 0101 | 0110 | 0001 | 0010 | | 0110 | 0010 | 0100 | 0010 | 0100 | | 0100 | 0100 | 0000 | 0100 | 1000 | | 0000 | 1000 | 1000 | 0000 | 0000 | | 1000 | 0000 | ---- | ---- | ---- | 

The last line is the base.

Answer 2

Remember this:

Standard 2003 C ++ 5.3.1c7:

The negation of the unsigned amount is calculated by subtracting its value from 2 ^ n, where n is the number of bits in the advanced operand.

a+b = a - (-b) will work in a C ++ compiler that complies with the 2003 standard (and C ++ 11 by the way).

Of course, I will answer an answer that meets earlier standards (e.g. C ++ 99, where -unsigned is undefined).

Answer 3

The bit manipulation code in the question uses two basic principles: half adder and the fact that the addition is commutative.

One half max adds two bits without hyphenation. The result of adding one bit is one if one of the inputs is one, zero if the inputs are equal. This is represented by the bitwise xor in the code.

Even after that you need to deal with carriers. Execution from the bit position is one if both bits are equal to one, otherwise zero. This is represented by a combination of bitwise and with the following shift , to move the carry to the bit position where it should be added.

The recursive call to add applies hyphens using the fact that addition is commutative. It does not matter if bit transfers are added along with the initial addition or bulk at a later stage.

Adding to the migration may result in a new execution. This is handled by continuing recursive calls until the addition is carried forward.

The case of the recursion base, zero wrapping, must be achieved because adding zero with zero wrapping cannot lead to wrapping. If the least significant bits of k are carried over zero by one addition, at least k+1 least significant bits of the next carry should be zero.

Answer 4

To understand why a function actually adds two numbers, it is useful to look at the truth table to add two bits:

a = 0, b = 0 → a + b = 00
a = 0, b = 1 → a + b = 01
a = 1, b = 0 → a + b = 01
a = 1, b = 1 → a + b = 10

You see that the low-order bit is the XOR of both input bits, and the high-order bit is AND of the two input bits, so the final result is (a XOR b) OR ((a AND B) <1). Since this function adds 32-bit numbers, you cannot simply OR get the results anymore, because some additional carry bits may appear in higher digits when combining the results of XOR and AND operations, and why you should use this function recursively.

Btw, this is pretty much a way of adding numbers to the hardware.

Answer 5

This is how hardware complements. The results of adding per bit are exceptional or (operator ^ in C ++) bits; this is what you get with sum . But this does not take into account the transfer from the lower bit. Execution is also a bit (operator & ), which gives the initial value of carry . But executing bit n is a carryover to bit n + 1, so we shift left by moving bit n to bit n + 1 and add it.

We use recursion to add it, because if the results (per bit) before adding the transfer are 1, and the transfer is 1, it will also be performed.

This is a little more subtle why the recursion ends (and, of course, the hardware version is not recursive, but adds additional logic). This is most easily evaluated considering the initial values:

 ab carry_in sum carry_out 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 0 1 1 1 1 1 1 1 0 1 

(The column "sum" is the result of a ^ b without hyphenation.)

On the first recursive call, bit 0 from b will be 0 (because it represents the transfer of bits of the least significant bit, and there is no one or mdash or because of << , which moves the value of carry_out bit n to carry_in bit n + 1). And, of course, carry_in of bit 0 will be 0. So, for bit 0 in the first recursive call, the first two lines can occur. This means that no carry_out, and for the next recursion, only the first two lines refer to bits 0 and 1. In other words, each recursion effectively eliminates one set bit from the common hyphenation, as a result of which the propagated hyphen should ultimately be 0. And since it propagates as parameter b, parameter b must become 0.