Comparison of unsigned integers

0

I'm trying to write an "BigInteger" implementation. BigInteger is an array of unsigned integers.

``````BigInteger_1 [0] ... BigInteger_1 [15];
``````

I'm trying to perform addition of two BigInteger's.

``````using System;

namespace BigInt {

class MainClass {

static int MAX_SIZE = 16;

public static void Main () {

// First BigInteger

uint[] BigInteger_1 = new uint[MAX_SIZE];

BigInteger_1 [15] = 0xfffffffe;

// Second BigInteger

uint[] BigInteger_2 = new uint[MAX_SIZE];

BigInteger_2 [15] = 0x00000002;

// Third BigInteger

uint[] BigInteger_3 = new uint[MAX_SIZE];

int i;

// Print BigInteger_1

for (i = 1; i < MAX_SIZE; i ++) {

Console.Write ("{0:x8}", BigInteger_1 [i]);

}

Console.WriteLine ();

// Print BigInteger_2

for (i = 1; i < MAX_SIZE; i ++) {

Console.Write ("{0:x8}", BigInteger_2 [i]);

}

Console.WriteLine ();

// Print BigInteger_3

for (i = 1; i < MAX_SIZE; i ++) {

Console.Write ("{0:x8}", BigInteger_3 [i]);

}

Console.WriteLine ();

}

uint[] BigInteger_1,

uint[] BigInteger_2

) {

uint[] BigInteger_3 = new uint[MAX_SIZE];

uint BigInteger_Carry = 0x00000000;

uint BigInteger_Limit = 0xffffffff;

int i;

// Loop through all integers

for (i = 1; i < MAX_SIZE; i ++) {

if (BigInteger_1 [i] + BigInteger_2 [i] >= BigInteger_Limit) {

Console.WriteLine ("Check {0} >= {1}", BigInteger_1 [i] + BigInteger_2 [i], BigInteger_Limit);

BigInteger_Carry = (BigInteger_1 [i] + BigInteger_2 [i]) - BigInteger_Limit;

BigInteger_3 [i] = BigInteger_Limit;

} else {

Console.WriteLine ("Check {0} < {1}", BigInteger_1 [i] + BigInteger_2 [i], BigInteger_Limit);

BigInteger_3 [i] = BigInteger_1 [i] + BigInteger_2 [i];

BigInteger_Carry = 0x00000000;

}

}

if (BigInteger_Carry != 0x00000000) {

BigInteger_3 [i] = BigInteger_Carry;

}

return BigInteger_3;

}

}

}
``````

When I set up variables to:

``````// First BigInteger
BigInteger_1 [15] = 0xfffffffe;

// Second BigInteger
BigInteger_2 [15] = 0x00000001;
``````

Then after executing I get this output (scroll to right):

``````Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 4294967295 >= 4294967295
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000fffffffe
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000001
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000ffffffff
``````

Which looks right. But when I set up variables to:

``````// First BigInteger
BigInteger_1 [15] = 0xfffffffe;

// Second BigInteger
BigInteger_2 [15] = 0x00000002;
``````

I get this (scroll again):

``````Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
Check 0 < 4294967295
0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000fffffffe
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000002
000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
``````

So I can not make a comparison of a sum of two integers and a max value if sum is greater than max value. What I can (and must) do in this situation?

c#
asked on Stack Overflow Sep 3, 2015 by Kechup

1

When you add two integers, if the sum is larger than the max representable value, it cannot be represented and operated on, by definition. Rolling over to zero when you exceed the max would be expected and is generally considered an error condition.

One inefficient way to accomplish what you're trying to would be to keep an extra integer in your BitInteger arrays you can internally maintain more than Max_Size precision.

answered on Stack Overflow Sep 3, 2015 by xpda
1

You are trying to check if `a + b > uint.MaxValue` which doesn't work when `a + b` overflow.

Solution 1: `bool carry = a > uint.MaxValue - b;`

Solution 2: `var result = a + b; bool carry = result < a || result < b;`

answered on Stack Overflow Sep 3, 2015 by Ivan Stoev

User contributions licensed under CC BY-SA 3.0