在 C# 中计算乘法的高位

Question

我正在尝试将开源库从 .Net 4.0 转换为 3.5，但无法轻松转换以下长乘法代码：

    /// <summary>
    /// Calculate the most significant 64 bits of the 128-bit
        product x * y, where x and y are 64-bit integers.
    /// </summary>
    /// <returns>Returns the most significant 64 bits of the product x * y.</returns>
    public static long mul64hi(long x, long y)
    {
 #if !NET35
        BigInteger product = BigInteger.Multiply(x, y);
        product = product >> 64;
        long l = (long)product;
        return l;
 #else
        throw new NotSupportedException(); //TODO!
 #endif
    }

如您所见，作者没有找到执行此操作的方法。 BigInteger .NET 3.5 中不存在。

如何在 .NET 3.5 上计算 64*64 乘法的高位 64 位？

Answer 1

您可以从多个 N 位乘法器构建一个 2N 位乘法器。

public static ulong mul64hi(ulong x, ulong y)
{
    ulong accum = ((ulong)(uint)x) * ((ulong)(uint)y);
    accum >>= 32;
    ulong term1 = (x >> 32) * ((ulong)(uint)y);
    ulong term2 = (y >> 32) * ((ulong)(uint)x);
    accum += (uint)term1;
    accum += (uint)term2;
    accum >>= 32;
    accum += (term1 >> 32) + (term2 >> 32);
    accum += (x >> 32) * (y >> 32);
    return accum;
}

就是小学长乘法，真的。

对于带符号的数字，这有点困难，因为如果中间结果进入符号位，一切都会出错。如果不发生这种情况，long 将无法保存 32 位乘以 32 位的结果，因此我们必须以较小的块进行：

public static long mul64hi(long x, long y)
{
    const long thirtybitmask = 0x3FFFFFFF;
    const long fourbitmask = 0x0F;
    long accum = (x & thirtybitmask) * (y & thirtybitmask);
    accum >>= 30;
    accum += ((x >> 30) & thirtybitmask) * (y & thirtybitmask);
    accum += ((y >> 30) & thirtybitmask) * (x & thirtybitmask);
    accum >>= 30;
    accum += ((x >> 30) & thirtybitmask) * ((y >> 30) & thirtybitmask);
    accum += (x >> 60) * (y & fourbitmask);
    accum += (y >> 60) * (x & fourbitmask);
    accum >>= 4;
    accum += (x >> 60) * (y >> 4);
    accum += (y >> 60) * (x >> 4);
    return accum;
}

受 harold 关于 Hacker's Delight 的评论的启发，通过仔细控制中间结果是否签名，可以使签名版本与其他版本一样高效：

public static long mul64hi(long x, long y)
{
    ulong u = ((ulong)(uint)x) * ((ulong)(uint)y);
    long s = u >> 32;
    s += (x >> 32) * ((long)(uint)y);
    s += (y >> 32) * ((long)(uint)x);
    s >>= 32;
    s += (x >> 32) * (y >> 32);
    return s;
}

在 C# 中计算乘法的高位

Computing the high bits of a multiplication in C#

.net

c#

biginteger

multiplication