Great whole addition without carry flag

Question

In assembly languages, there is usually an instruction that adds two operands and a carry. If you want to implement large integer additions, you simply add the smallest integers without hyphenation and the following integers with hyphenation. How can I do this efficiently in C or C ++ where I do not have access to the carry flag? It should work on several compilers and architectures, so I can't just use the built-in assembly or such.

Answer 1

You can use "nails" (a term from GMP): instead of using all 64 bits of uint64_t when representing a number, use only 63 of them with a top zero bit. This 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, specify the number as an uint32_t array (or, equivalently, divide 64-bit words into upper and lower 32-bit fragments). Then, performing arithmetic operations on these 32-bit integers, you can first advance up to 64 bits, arithmetic there, and then convert back. This allows you to detect hyphenation, and is also useful for multiplication if you do not have the multiply hello command.

As another answer indicates, you may find overflow in an unsigned append:

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

Aside, although in practice this will also work in signed arithmetic, you have two problems:

• It's harder
• Technically, integer overflow with undefined sign behavior

therefore, you are usually better off sticking with unsigned numbers.

Answer 2

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

In other words, if a + b less than a , it overflows. This is for positive values ​​of a and b , of course, but what you will almost certainly use for the bignum library.

Unfortunately, wrapping introduces an additional complication in that adding the highest possible value plus wrapping one will give you the same value you started from. Therefore, you should treat this 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 fact, you can also consider using all the bits in the elements of the array.

I have implemented libraries in the past where the maximum “digit” is less than or equal to the square root of the highest value that it can hold. Thus, for 8-bit (octet) digits, you store values ​​from 0 to 15 - thus, multiplying two digits and adding the maximum carry will always correspond to an octet, which makes overflow detection controversial, although at the cost of some memory.

Similarly, 16-bit digits will have a range from 0 to 255, so that it will not overflow on 65536.

In fact, I sometimes limited it to more than that, ensuring that the value of the artificial wrapping is ten (so that the octet will contain from 0 to 9, the 16-bit digits will be from 0 to 99, the 32-bit digits from 0 to 9999, etc. d.

It's a little more wasteful in space, but makes converting to and from text (like printing your numbers) incredibly easy.

Answer 3

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

just run the thing with carry 0.

Answer 4

If you understand correctly, you want to write your own complement for your own large 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 carry flag (inside this function), starting with carry 0, and set the result to (a + b + carry)% 10 and transfer to (a + b + carry) / 10.

this CO may be relevant: how to implement a large int in c