C# 中 BigInteger 的按位运算符
Bitwise operators on BigInteger in C#
问题
我正在尝试使用 BigInteger
值在 C# 中实现 the following Java function,以便 64 位限制不再适用。作为完整性检查,我也将使用 long
的原始函数转换为 C# 代码。然而,问题是,虽然使用 long
的版本有效,但使用 BigInteger
的版本并不总是 return 相同的结果。
实施
原始函数在 C# 中的实现。
获取下一个子集 (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;
}
获取所有子集(long
)
我没有像原始 Java 代码那样打印所有值,而是打算使用它们,所以我 return 每个值都单独显示。
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);
}
}
获取下一个子集 (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;
}
获取所有子集(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);
}
}
预期值
从 n
个对象的集合中选择 k
个对象背后的数学原理
从 combinatorics 开始,使用选择函数可以轻松验证生成的数字集合是否具有正确的值数:
Choose(n, k) = n! / (k! * (n - k)!)
示例,其中 long
版本有效,但 BigInteger
版本无效
从一副标准的 52 张扑克牌中抽两张牌的方法是 1326 种,但 BigInteger
实现只产生 190 种。
如何更正 BigInteger
实施?
问题是您在创建 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);
}
}
问题
我正在尝试使用 BigInteger
值在 C# 中实现 the following Java function,以便 64 位限制不再适用。作为完整性检查,我也将使用 long
的原始函数转换为 C# 代码。然而,问题是,虽然使用 long
的版本有效,但使用 BigInteger
的版本并不总是 return 相同的结果。
实施
原始函数在 C# 中的实现。
获取下一个子集 (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;
}
获取所有子集(long
)
我没有像原始 Java 代码那样打印所有值,而是打算使用它们,所以我 return 每个值都单独显示。
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);
}
}
获取下一个子集 (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;
}
获取所有子集(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);
}
}
预期值
从 n
个对象的集合中选择 k
个对象背后的数学原理
从 combinatorics 开始,使用选择函数可以轻松验证生成的数字集合是否具有正确的值数:
Choose(n, k) = n! / (k! * (n - k)!)
示例,其中 long
版本有效,但 BigInteger
版本无效
从一副标准的 52 张扑克牌中抽两张牌的方法是 1326 种,但 BigInteger
实现只产生 190 种。
如何更正 BigInteger
实施?
问题是您在创建 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);
}
}