C#中BigInteger的位运算符

Question

我试图使用biginteger值在C#中实现以下Java函数，以便不再适用64位限制。作为一项健全性检查，我将使用long的原始函数也转换为C#代码。然而，问题是，使用long的版本工作时，使用biginteger的版本并不总是返回相同的结果。

C#中原始函数的实现。

public static long GetNextSubset(long subset)
{
    long smallest = subset& -subset;
    long ripple = subset + smallest;
    long ones = subset ^ ripple;
    ones = (ones >> 2) / smallest;
    subset = ripple | ones;
    return subset;
}

而不是像原始的Java代码那样打印所有的值，我打算使用它们，这样我就可以单独返回每个值。

public static IEnumerable<long> GetAllSubsets(int n, int k)
{
    long max = 1L << n;
    long subset = (1L << k) - 1L;
    while ((max & subset) == 0)
    {
        yield return subset;
        subset = GetNextSubset(subset);
    }
}

public static BigInteger GetNextSubsetsBigInt(BigInteger subset)
{
    var smallest = subset& -subset;
    var ripple = subset + smallest;
    var ones = subset ^ ripple;
    ones = (ones >> 2) / smallest;
    subset = ripple | ones;
    return subset;
}

public static IEnumerable<BigInteger> GetAllSubsetsBigInt(int n, int k)
{
    var max = new BigInteger(1 << n);
    var subset = new BigInteger((1 << k) - 1);
    while ((max & subset) == 0)
    {
        yield return subset;
        subset = GetNextSubsetsBigInt(subset);
    }
}

在组合学中,使用choose函数可以很容易地验证生成的数字集合是否具有正确的值数：

选择(n，k)=n！/（k！*(n-k)！）

从52张扑克牌的标准副牌中抽取两张牌的方法数是1326，但biginteger实现只产生190张。

如何更正biginteger实现？

Answer 1

问题是，在创建bigInteger之前，要对int进行位移位。只需更改它，创建一个biginteger值1，然后进行位移位。甚至还有一个静态属性可以使用，称为BigInteger.One。

public static IEnumerable<BigInteger> GetAllSubsetsBigInt(int n, int k)
{
    var max = BigInteger.One << n;
    var subset = (BigInteger.One << k) - 1;
    while ((max & subset) == 0)
    {
        yield return subset;
        subset = GetNextSubsetsBigInt(subset);
    }
}