在C#中计算乘法的高位

Question

在C#中计算乘法的高位

9

我正在尝试将一个开源库从 .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位？

- Seneral

https://msdn.microsoft.com/en-us/magazine/cc163696.aspx - Hans Passant

谢谢提供链接，使用 J# 库我可能会让它工作！我现在正在尝试... - Seneral

嗯，对我没用。MDSN说它只适用于VS 5或更早版本，而我需要使用VS2010解决其他问题（默认参数）。 - Seneral

1

由于您询问的是一个众所周知的问题（乘法的高位），因此已经存在解决方案：https://dev59.com/P14b5IYBdhLWcg3wojBg。我没有找到C#的解决方案，但C代码应该可以直接使用。 - usr

@usr 谢谢，我会看一下这个的，目前正在跟随一个使用Mono源代码中System.Numeric命名空间的解决方案。答案看起来非常有前途 :) - Seneral

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Ben Voigt · Accepted Answer

您可以通过多个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;
}

受哈罗德关于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;
}