Hi all, Simple enough question for the more brainy of you - how do you apply arithmetic to 64-bit values represented as a 32-bit pair without using platform specific types, such as long long/__int64? I can''t get my head around how you would treat a number once its value exceeds 2^32 since the value is split between the two 32-bit words. Anyone make sense of what I''m on about? Tom L

In assembler there are special versions of ADD (and the other arithmetical operations) that let you include the carry flag in the addition. Thus you add first the 32 low-order bits, then add the high-order bits plus the carry flag. This is basically what C/C++ or any other language does when using 64 bit integers.

Using assembler it is thus quite easy to write your own 64 bit arithmetic routines, on intel and intel compatible processors anyway.

In a high-level language such as C/C++ you can do something similar using smaller types. For example store your number in an array of bytes. To add two numbers of this representation you start with the lowest byte, add them into a larger datatype so that you can get the bits that are larger than the byte. For the second byte you include what didn''t fit in the first byte as well as the two second lowest bytes of the numbers. Do I make sense?

Of course, for multiplication and division it is more difficult, but can be done. Take a look at how you did multiplication and division on paper when you first learnt it in school. Using the same technique but with a base 256 instead of 10 you have a pretty solid way of doing mathematics with huge numbers.



www.AngelCode.com

Say you had a decimal machine and you could only add two digit numbers directly. So you want to add 1234+5678. Well 4+8=12, 3+7+1=11, 2+6+1=9, and 1+5+0=6 giving 6912 as your answer. The main thing to note is that 34+78=12, not 112 since you overflowed a two digit number. It doesn''t really matter if it is decimal or binary, two decimal digits or 32 binary digits, i.e. you can do the same thing breaking a 64 bit binary word into four 16 bit binary words.

Just an idea to try:

struct u64 {
u32 lower,upper;
};

result.lower = a.lower + b.lower;
result.upper = a.upper + b.upper + (result.lower < a.lower)

Yes, but I think you would need to do:

result.upper = a.upper + b.upper + (result.lower < a.lower || result.lower < b.lower);

quote:

---

Yes, but I think you would need to do:

result.upper = a.upper + b.upper + (result.lower < a.lower || result.lower < b.lower);

---

Can you give me an example where I need that? (You can use base 10 in your example instead of 2^32 if you want).

The comparision evaluates to zero or one depending upon whether the addition overflowed or not, i.e. if the result is smaller than either of the values being added together then you overflowed. So 34+68=12, (12<34 || 12<68) is true and you have a carry of one. It runs a good bit faster since on a Pentium I assume because you can stay with 32 operations. The most you ever carry in addition of two numbers is one, i.e. x^n-1+x^n-1=2*(x^n-1)<2*x^(n+1) for all x>=0 and n>=0.

I still don''t get it. Why do you think that you have to test if the result is less than any of the two? It will be less than one of them if and only if it''s less than the other. So you may as well check only one of them, as I proposed.

You are correct, but it wasn''t obvious that was true.