big integer addition without carry flag

问题:

In assembly languages, there is usually an instruction that adds two operands and a carry. If you want to implement big integer additions, you simply add the lowest integers without a carry and the next integers with a carry. How would I do that efficiently in C or C++ where I don't have access to the carry flag? It should work on several compilers and architectures, so I cannot simply use inline assembly or such.

回答1:

You can use "nails" (a term from GMP): rather than using all 64 bits of a uint64_t when representing a number, use only 63 of them, with the top bit zero. That way you can detect overflow with a simple bit-shift. You may even want less than 63.

Or, you can do half-word arithmetic. If you can do 64-bit arithmetic, represent your number as an array of uint32_ts (or equivalently, split 64-bit words into upper and lower 32-bit chunks). Then, when doing arithmetic operations on these 32-bit integers, you can first promote to 64 bits do the arithmetic there, then convert back. This lets you detect carry, and it's also good for multiplication if you don't have a "multiply hi" instruction.

As the other answer indicates, you can detect overflow in an unsigned addition by:

uint64_t sum = a + b;
uint64_t carry = sum < a;

As an aside, while in practice this will also work in signed arithmetic, you have two issues:

• It's more complex
• Technically, overflowing a signed integer is undefined behavior

so you're usually better off sticking to unsigned numbers.

回答2:

You can figure out the carry by virtue of the fact that, if you overflow by adding two numbers, the result will always be less than either of those other two values.

In other words, if a + b is less than a, it overflowed. That's for positive values of a and b of course but that's what you'd almost certainly be using for a bignum library.

Unfortunately, a carry introduces an extra complication in that adding the largest possible value plus a carry of one will give you the same value you started with. Hence, you have to handle that as a special case.

Something like:

carry = 0
for i = 7 to 0:
    if a[i] > b[i]:
        small = b[i], large = a[i]
    else:
        small = a[i], large = b[i]
    if carry is 1 and large is maxvalue:
        c[i] = small
        carry = 1
    else:
        c[i] = large + small + carry
        if c[i] < large:
            carry = 1
        else
            carry = 0

---

In reality, you may also want to consider not using all the bits in your array elements.

I've implemented libraries in the past, where the maximum "digit" is less than or equal to the square root of the highest value it can hold. So for 8-bit (octet) digits, you store values from 0 through 15 - that way, multiplying two digits and adding the maximum carry will always fit with an octet, making overflow detection moot, though at the cost of some storage.

Similarly, 16-bit digits would have the range 0 through 255 so that it won't overflow at 65536.

In fact, I've sometimes limited it to more than that, ensuring the artificial wrap value is a power of ten (so an octet would hold 0 through 9, 16-bit digits would be 0 through 99, 32-bit digits from 0 through 9999, and so on.

That's a bit more wasteful on space but makes conversion to and from text (such as printing your numbers) incredibly easy.

回答3:

u can check for carry for unsigned types by checking, is result less than an operand (any operand will do).

just start the thing with carry 0.

回答4:

If I understand you correctly, you want to write you own addition for you own big integer type.

You can do this with a simple function. No need to worry about the carry flag in the first run. Just go from right to left, add digit by digit and the carry flag (internally in that function), starting with a carry of 0, and set the result to (a+b+carry) %10 and the carry to (a+b+carry) / 10.

this SO could be relevant: how to implement big int in c