Adding 64 bit numbers using 32 bit arithmetic

Question

How do we add two 64 bit numbers using 32 bit arithmetic??

Answer 1

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

Answer 2

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.