Adding 64 bit numbers using 32 bit arithmetic

How do we add two 开发者_开发知识库64 bit numbers using 32 bit arithmetic??

Add the least significant bytes first, keep the carry. Add the most significant bytes considering the carry from LSBs:

; x86 assembly, Intel syntax
; adds ecx:ebx to edx:eax
add eax, ebx
adc edx, ecx

Consider how you add two 2-digit numbers using 1-digit arithmetic.

 42
+39
---

First you add the right column. (The "ones" or "units"). 2+9 is 11. 11 "overflowed" your 1 digit arithmetic, so you have to "carry" the 10.

 1
 42
+39
---
  1

Now you add up the left "tens" column, including the carry. 1+4+3=8.

 1
 42
+39
---
 81

8 is less than 10, so no carry. You're done.

What just happened? When you say that a number is "42" (in base 10) you really mean

4*10+2

Or, equivalently,

4*10^1+2*10^0

(when I say "a^b", like "10^1", I mean "a raised to the b'th power": a multiplied by itself b times. 10^0 is 1. 10^1 is 10. 10^2 is 10*10=100...)

When you add "42" and "39" you are saying

4*10+2+3*10+9

Which equals

(4+3)*10+(2+9)*1
(4+3)*10+(11)*1
(4+3)*10+(1*10+1)*1

Now since "11" isn't a valid one digit number, you need to carry 10 from the ones, turning it into a 1 in the tens place.

(4+3)*10+(1)*10+(1)*1
(4+3+1)*10+(1)*1
(8)*10+(1)*1

which is 81.

So, why have I been talking about this rather than your question about 64 bit numbers and 32 bit arithmetic? Because they are actually exactly the same!

A digit ranges from 0 to 9. A "32 bit number" ranges from 0 to 2^32-1. (Assuming it is unsigned.)

So, rather than working in base 10, let's work in base 2^32. In base 2^32, we write 2^32 as 10. If you write a 64 bit number in base 2^32, it would be

(x)*10+y

where x and y are symbols for numbers between 0 and 2^32-1. Those symbols are bitstrings.

If you want to add two 64 bit numbers, break them down in base 2^32 as:

 a_1*10+a_0
+b_1*10+b_0

Now you add them in base 2^32 the exact same way you add them in base 10 -- just, rather than adding using digit arithmetic you add using 32 bit arithmetic!

How do you split a 64 bit number a into two 32 bit numbers a_1 and a_0? Divide a by 2^32. Not in floating point, but integerwise -- where you get a dividend and a remainder. The dividend is a_1, the remainder is a_0.

Unfortunately that requires 64 bit arithmetic. However, typically a_1 is the "most significant half" of a, so, in C style syntax:

a_1=(a >> 32)
a_0=(a & 0xFFFFFFFF)

where >> is a right bitshift and & is bitwise and.

Typically if you can't do 64 bit addition, a "64 bit number" will actually be the two 32 bit numbers a_1 and a_0. You won't have a uint64_t if you can't do uint64_t arithmetic!

All this assumes that you're doing unsigned arithmetic, but dealing with signs is easy from here.

The C code previously posted is unnecessarily verbose:

unsigned a1, b1, a2, b2, c1, c2;

c1 = a1 + b1;
c2 = a2 + b2;

if (c1 < a1)
    c2++;

The 'a1' in the 'if' can be replaced with 'b1' as well. On overflow, c1 will be less than both a1 and b1.

If the 64-bit numbers are (a₂,a₁) and (b₂,b₁), where x₂ is the high 32 bits taken as unsigned, and x₁ is the low 32 bits taken as unsigned, then the sum of the two numbers is given below.

c1 = a1 + b1

c2 = a2 + b2

if (c1 < a1 || c1 < b1)
   c2 += 1

it looks something like this

/* break up the 64bit number into smaller, 16bit chunks */
struct longint { 
    uint16 word0; 
    uint16 word1;
    uint16 word2;
    uint16 word3;
};

uint16 add(longint *result, longint *a, longint *b)
{
    /* use an intermediate large enough to hold the result
       of adding two 16 bit numbers together. */
    uint32 partial;

    /* add the chunks together, least significant bit first */
    partial = a->word0 + b->word0;

    /* extract thie low 16 bits of the sum and store it */
    result->word0 = partial & 0x0000FFFF;

    /* add the overflow to the next chunk of 16 */
    partial = partial >> 16 + a->word1 + b->word1;
    /* keep doing this for the remaining bits */
    result->word1 = partial & 0x0000FFFF;
    partial = partial >> 16 + a->word2 + b->word2;
    result->word2 = partial & 0x0000FFFF;
    partial = partial >> 16 + a->word3 + b->word3;
    result->word3 = partial & 0x0000FFFF;
    /* if the result overflowed, return nonzero */
    return partial >> 16;
}

Actual hardware doesn't use 32 bits to add 16 bits at a time, only one extra bit of carry is ever needed for addition, and almost all CPU's have a carry status flag for when an addition operation overflowed, so if you are using a 32 bit cpu, you can add 64 bit operands in two, 32 bit operations.

Pretty much every processor has the carry bit and add-with-carry operation, which you only care about if you're programming in assembly. If you're using a higher language, the compiler dumps out the exact same add-with-carry operations. My AVR-GCC gave me this when adding two 16-bit numbers--the AVR is 8-bit--but the same concepts would apply for higher processors.

Given the numbers are in registers R1:R2 and R3:R4:

ADD R2,R4 ; first add the two low-bytes, result stored into R2
ADC R1,R3 ; then the two high-bytes and the carry bit, into R1

The result is stored into R1:R2.