Bitwise operators on BigInteger in C#

user_11808605 0
Viewed 161

Question

I'm trying to implement the following Java function in C# using BigInteger values so that the 64-bit restriction no longer applies. As a sanity check, I converted the original function using long to C# code as well. The problem is, however, that while the version using long works, the version using BigInteger does not always return the same result.

Implementations

Implementations of the original function in C#.

Get next subset (long)

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;
}

Get all subsets (long)

Rather than printing all the values like in the original Java code, I intend to use them so I return each value individually.

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);
    }
}

Get next subset (BigInteger)

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;
}

Get all subsets (BigInteger)

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);
    }
}

Expected values

The math behind choosing k objects from a collection of n objects

From combinatorics, it's easy to verify if the yielded collection of numbers has the correct number of values using the choose function:

Choose(n, k) = n! / (k! * (n - k)!)

Example where long version works, but the BigInteger version does not

The number of ways to draw two cards from a standard deck of 52 playing cards is 1326, but the BigInteger implementation yields only 190.

How can I correct the BigInteger implementation?

biginteger bit-manipulation c#
1 Answers

The problem is that you're doing the bit shifts on an int before creating the BigInteger. Just change it to create a BigInteger value of 1 and then do the bit shifts. There's even a static property you can use called 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);
    }
}
user_3029180
Related