无符号整数的比较

本文关键字：比较 无符号整数 | 更新日期: 2023-09-27 18:11:00

我想写一个"BigInteger"实现。BigInteger是一个无符号整数数组。

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

我正在尝试执行两个BigInteger的加法。

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];
            // Perform an addition
            BigInteger_3 = BigInteger_Add (BigInteger_1, BigInteger_2);
            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 ();
        }
        public static uint[] BigInteger_Add (
            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;
        }
    }
}

当我将变量设置为:

// First BigInteger
BigInteger_1 [15] = 0xfffffffe;
// Second BigInteger
BigInteger_2 [15] = 0x00000001;

然后执行后，我得到这个输出(向右滚动):

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

看起来是对的。但是当我将变量设置为:

// First BigInteger
BigInteger_1 [15] = 0xfffffffe;
// Second BigInteger
BigInteger_2 [15] = 0x00000002;

我得到这个(再次滚动):

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

所以如果sum大于max，我就不能比较两个整数和一个最大值。在这种情况下我能(也必须)做什么?

无符号整数的比较

当两个整数相加时，如果总和大于最大可表示值，根据定义，它不能被表示和操作。当您超过最大值时，滚动到零将是预期的，并且通常被认为是错误条件。

一种低效率的方法是在BitInteger数组中保留一个额外的整数，你可以在内部保持超过Max_Size的精度。

您正在尝试检查a + b > uint.MaxValue是否在a + b溢出时不工作

方案1: bool carry = a > uint.MaxValue - b;

方案2: var result = a + b; bool carry = result < a || result < b;

相关文章：