我一直在研究Karatsuba's algorithm on Wikipedia，我在这一段停下来让我感到困惑。为什么这个算法有溢出，我不明白他为解决这个问题所采取的步骤。我的问题截图
以免仅为首发考虑正数。让我们有8位数字/数字x0,x1,y0,y1。
当我们应用8位乘法时：
x0*y0 -> 8bit * 8bit -> 16 bit
它将产生高达16位的结果。最高值是：
FFh*FFh = FE01h
255*255 = 65025
现在，如果我们回到Karatsuba让
X = x0 + x1<<8
Y = y0 + y1<<8
Z = X*Y = z0 + z1<<8 + z2<<16
现在让我们看看zi的位宽
z2 = x1*y1 -> 16 bit
z1 = x1*y0 + x0*y1 -> 17 bit
z0 = x0*y0 -> 16 bit
请注意，z1的最高值为17位
65025+65025 = 130050
因此每个zi溢出8位。要处理这个问题，你只需要最低8位，其余的则加上更高的数字（比如Carry的传播）。所以：
z1 += z0>>8; z0 &= 255;
z2 += z1>>8; z1 &= 255;
z3 = z2>>8;
Z = z0 + z1<<8 + z2<<16 + z3<<24
但通常，乘法的HW实现会自行处理，并将结果作为两个单词而不是一个单词。见Cant make value propagate through carry
因此16位乘法的结果是32位。请注意，为了添加8位子结果，您需要至少10位，因为我们将3个数字加在一起，或者以9位（或8位+ 1个进位）逐个添加和传播它们。
如果您为此添加有符号值，则需要另外一位用于符号。为了避免它记住操作数的符号并使用abs值...并根据原始符号设置结果的符号。
有关详细信息，请参阅：