无符号数的上溢/下溢

Question

因此，如果无符号数的加法进位为 1，则发生溢出；如果减法的进位为 0，则发生下溢。但这在所有情况下都有效吗？

如果你打成5-0： 0101 -0000

= 0101 +(1111 + 1)

= 0101 +0000

= 0101...这里进位为零，而不是 1。如何解释这种情况？有不同的方法吗？

（使用 MIPS 架构或其他任何东西）

---编辑

感谢 Amadan。不过我理解那部分。我的问题是零似乎是一个特例。它似乎不遵循正常数字的做法：在上面的示例中，没有 1 的进位。

我目前正在使用 ALU 进行电路设计，并尝试实现溢出检测，当出现这种情况时不遵循其他人所做的事情。

我们假设通过减法，第二个操作数在进入 ALU 之前被预先反转（二进制补码）（然后添加到第一个操作数）。因此，每当减法的“invert_b”设置为 1 时，b 就会反转，我们假设我们正在检查的情况是减法，其进位应该为 1。

Answer 1

我相信 msbit 进位位本身涵盖了未签名的情况，对于有符号的情况，您可以查看 msbit 的进位和进位是否不同。

5-0 不会溢出，因为结果适合可用位数。 的 4 位系统一样

与 15-1 不会溢出有符号数5 - 0 = 0101 + 1111 + 1

    1
 0101
+1111
=====

11111
 0101
+1111
=====
 0101

，因此 5 - 0 肯定会执行 1，因为这是一个不是溢出的减法

15 - 1 = 1111 + ~1 进位设置

    1
 1111
 1110
 ====

11111
 1111
 1110
 ====
 1110

与 1 相减不是您所说的无符号溢出

同样 -1 - 1 = 1111 + ~1 进位在位集中，

11111
 1111
 1110
 ====
 1110

最后一位的进位是 1，进位是 1，它们匹配，没有符号溢出。

8 + 8 = 1000 + 1000，其中进位为清除

    0
 1000
+1000
=====

10000
 1000
+1000
=====
 0000

无符号溢出。

嗯 4 + 4

    0
 0100
+0100
=====

01000
 0100
+0100
=====
 1000

无符号加法进位为 0 这不是无符号溢出。但这是有符号溢出，因为 msbit 的进位和进位不同。 +4 + +4 = +8，在 4 位有符号系统中，您无法表示 +8，因此有符号溢出是准确的。

无论有多少位，这些奇怪的数字都是零和一个一，其余的都是零，0和8，或者对于4位系统来说是-8。

使用 2、3 或 4 位数字的所有组合制作一个图表，并手动查看所有这些数字以查看它们是否有意义。无论你发现什么，无论有多少位宽，都会缩放，100 位加法器的工作方式就像 10 位加法器......

add           C V  unsigned    signed
00 + 00 = 000 0 0  0 + 0 = 0   0 +  0 =  0
00 + 01 = 001 0 0  0 + 1 = 1   0 +  1 =  1
00 + 10 = 010 0 0  0 + 2 = 2   0 + -2 = -2
00 + 11 = 011 0 0  0 + 3 = 3   0 + -1 = -1
01 + 00 = 001 0 0  1 + 0 = 1   1 +  0 =  1
01 + 01 = 010 0 1  1 + 1 = 2   1 +  1 =  2  signed cannot represent a +2
01 + 10 = 011 0 0  1 + 2 = 3   1 + -2 = -1
01 + 11 = 100 1 0  1 + 3 = 4   1 + -1 =  0  unsigned cannot represent +4
10 + 00 = 010 0 0  2 + 0 = 2  -2 +  0 = -2 
10 + 01 = 011 0 0  2 + 1 = 3  -2 +  1 = -1
10 + 10 = 100 1 1  2 + 2 = 4  -2 + -2 = -4 neither +4 nor -4 will fit in 2 bits
10 + 11 = 101 1 1  2 + 3 = 5  -2 + -1 = -3 neither +4 nor -3 will fit in 2 bits
11 + 00 = 011 0 0  3 + 0 = 3  -1 +  0 = -1 
11 + 01 = 100 1 0  3 + 1 = 4  -1 +  1 = -2 +4 does not fit in 2 bits
11 + 10 = 101 1 1  3 + 2 = 5  -1 + -2 = -3 neither +5 nor -3 fit in 2 bits
11 + 11 = 110 1 0  3 + 3 = 6  -1 + -1 = -2 6 does not fit in 2 bits
sub
00 - 00 = 100 0 0
00 - 01 = 011 1 0  0 - 1 = -1   -1 does not fit in an unsigned result
00 - 10 = 010 1 1  0 - 2 = -2  0 - -2 = +2  
00 - 11 = 001 1 0  0 - 3 = -3
01 - 00 = 101 0 0
01 - 01 = 100 0 0
01 - 10 = 011 1 1  1 - 2 = -1  1 - -2 =  3
01 - 11 = 010 1 1  1 - 3 = -2  1 - -1 =  2
10 - 00 = 110 0 0  
10 - 01 = 101 0 1             -2 -  1 = -3
10 - 10 = 100 0 0
10 - 11 = 011 1 0  2 - 3 = -1
11 - 00 = 111 0 0
11 - 01 = 110 0 0
11 - 10 = 101 0 0
11 - 11 = 100 0 0

生成上述代码的代码

printf("add\n");
for(ra=0;ra<4;ra++)
{
    for(rb=0;rb<4;rb++)
    {
        rd=(ra&1)+(rb&1);
        rc=ra+rb;
        rd=(rd>>1)&1;
        re=(rc>>2)&1;
        if(re) c=1; else c=0;
        if(rd!=re) v=1; else v=0;

        if(ra&2) printf("1"); else printf("0");
        if(ra&1) printf("1"); else printf("0");
        printf(" + ");
        if(rb&2) printf("1"); else printf("0");
        if(rb&1) printf("1"); else printf("0");
        printf(" = ");
        if(rc&4) printf("1"); else printf("0");
        if(rc&2) printf("1"); else printf("0");
        if(rc&1) printf("1"); else printf("0");
        printf(" %u %u\n",c,v);
    }
}
printf("sub\n");
for(ra=0;ra<4;ra++)
{
    for(rb=0;rb<4;rb++)
    {
        rd=(ra&1)+((~rb)&1)+1;
        rc=ra+((~rb)&3)+1;
        rd=(rd>>1)&1;
        re=(rc>>2)&1;
        if(re) c=0; else c=1;
        if(rd!=re) v=1; else v=0;

        if(ra&2) printf("1"); else printf("0");
        if(ra&1) printf("1"); else printf("0");
        printf(" - ");
        if(rb&2) printf("1"); else printf("0");
        if(rb&1) printf("1"); else printf("0");
        printf(" = ");
        if(rc&4) printf("1"); else printf("0");
        if(rc&2) printf("1"); else printf("0");
        if(rc&1) printf("1"); else printf("0");
        printf(" %u %u\n",c,v);
    }
}

现在你的问题是在谈论无符号数，是吗？所以你可能不关心V位也不关心右半部分，即签名的一半。

这是我实现的小型 16 位处理器的一些 HDL/RTL：

case 4b0000:
{
    //0000 add rd,rs
    op_a = bundle(1b0,reg[bundle(2b0,inst[4;8])].value);
    op_b = bundle(1b0,reg[bundle(2b0,inst[4;4])].value);
    op_res = op_a + op_b;
    reg[1].value[CBIT] <= op_res[16];
    reg[1].value[NBIT] <= op_res[15];

    if(op_res[16;0] == 16h0000)
    {
        reg[1].value[ZBIT] <= 1b1;
    }
    else
    {
        reg[1].value[ZBIT] <= 1b0;
    }
    if((op_a[15] == op_b[15]) && (op_res[15] != op_b[15] ) )
    {
        reg[1].value[VBIT] <= 1b1;
    }
    else
    {
            reg[1].value[VBIT] <= 1b0;
    }
    reg[bundle(2b0,inst[4;8])].value <= op_res[16;0];
}
case 4b0001:
{
    //0001 sub rd,rs
    op_a = bundle(1b0,reg[bundle(2b0,inst[4;8])].value);
    op_b = bundle(1b0,reg[bundle(2b0,inst[4;4])].value);
    op_res = op_a - op_b;
    reg[1].value[CBIT] <= (~op_res[16]);
    reg[1].value[NBIT] <= op_res[15];

    if(op_res[16;0] == 16h0000)
    {
        reg[1].value[ZBIT] <= 1b1;
    }
    else
    {
        reg[1].value[ZBIT] <= 1b0;
    }
    if((op_a[15] != op_b[15]) && (op_res[15] == op_b[15] ) )
    {
        reg[1].value[VBIT] <= 1b1;
    }
    else
    {
        reg[1].value[VBIT] <= 1b0;
    }
    reg[bundle(2b0,inst[4;8])].value <= op_res[16;0];
}

我已经/已经在其他逻辑中看到了用于有符号溢出的 msbit 事物，并且在尝试每种可能的组合时找不到与进位与进位方法不匹配的情况在头对头分析中。

如果我的答案太过分了，我不介意在开头将其剪掉，它显示 5 - 0 有一个 1 作为 1 的进位，这对于减法来说不是溢出。答案很长，因为很难理解有符号与无符号以及加法器在逻辑上的一般工作原理。加法器不知道或不关心有符号或无符号，它确实关心加法与减法，通过减法可以反转第二个操作数，反转进位到 lsbit 以及进位出 msbit（考虑加法，带进位的加法） 、 sub 和带有进位的 sub ）。有符号与无符号的关系取决于它本身（二进制补码的美妙之处）。将上述内容简化为仅无符号的讨论，使其简单一半以上，因为有符号溢出对于不经意的观察者来说并不明显（如无符号溢出）。

我当然希望我剪切并粘贴了调试后的 HDL，如果我没有的话，将会得到很多响应/更正...我花了几天时间说服自己相信上述所有内容，并与我有权访问的其他处理器的结果进行比较，等等。希望这可以为您节省几天的时间。

Answer 2

不是专家，但整个关于减法的陈述似乎是错误的。

您可以通过两种基本方式实现减法：直接作为减法，或作为补码加法。

如果你用二进制补码加法，那么就像你说的：1的进位是下溢。

5 - 6
= 0101 - 0110
= 0101 + (1001 + 1)
= 0101 + 1010
= (0)1111, carry 0 = underflow

如果直接减法，则 1 进位下溢：

0101 - 0110:
0     to    1 is 1
1     to (1)0 is 1, carry 1
1 + 1 to (1)1 is 1, carry 1
0 + 1 to (1)0 is 1, carry 1 = underflow

Answer 3

可能还有其他等效的方法来设计加法器的溢出检测单元，但最常见的是Cin XOR Cout。例如，请参阅第 4 课的结尾 http ://cs.nyu.edu/~gottlieb/courses/2007-08-fall/arch/class-notes.html

它只是检查数字是否被添加（如果某些内容被反转） 2 的补码与否并不重要，我们稍后会查看这些值）进位到最后一位数字的计算中，但不会进位到超出支持的位大小的数字中，反之亦然。

这是有道理的，因为如果它们进位而不是输出，结果一定是负数（因为 MSB 必须是 1），但操作数必须是正数（因为如果它们是负数，就会进位）。这就是溢出的定义，因为两个正数之和不能等于负数。

这是一个签名模型，但是，我不确定这是否是您正在寻找的，因为您提到了未签名。如果是这样的话，那么你是对的，当进位为 1 时，简单加法模型就会溢出（这相当于上面的情况，如果你认为加法对于每个操作数的 MSB 有一个额外的 0，那么进位将始终为 0，并且当且仅当进位为 1 时才会发生溢出。这种情况下的进位是我们模型中的进位）。

如果值为负，减法会导致下溢。如果我们认为正操作数的附加 MSB 为 0，负操作数的附加 MSB 为 1（符号扩展），我们可以再次导出等价性。那么当结果的 MSB 为 1 时，我们就是负数。当我们原始模型中的进位（新模型中的进位）为 0 时，就会发生这种情况，因为只有这样，新模型中结果的 MSB 才会保持为 1您

的示例也不例外：0101 + 1111 + 1 = 0101，进位为 1，因此不会下溢，因为结果为正。