我有一个积极的C#BigInteger。它可能很大。我想对它的大小做一个非常粗略的估算。如果我的估计错了(说)千分之一,那很好。
我已经尝试过以下方法。全部都很慢(在3 ^ 1000000上大约有80k滴答声)
int est1 = myBigInt.ToByteArray().Count();
double est2 = BigInteger.Log10(myBigInt);
double est3 = BigInteger.Log(myBigInt);
编辑:“大小”是指“数值”,而不是“内存大小”。
从.NET Core 2.1开始,有一个new API: public int GetByteCount (bool isUnsigned = false);
我希望我们也能在.NET Standard的下一版本中找到它。
首先优化是这里避免LINQ,ToByteArray()
返回byte[]
,然后可以直接使用Length
属性:
int est = myBigInt.ToByteArray().Length;
但是,这仍然不是最佳选择,因为ToByteArray()
会克隆内部缓冲区。对于非常大数字,使用反射读取它甚至可能具有更好的长期性能:
var bits = typeof(BigInteger).GetField("_bits",
BindingFlags.Default | BindingFlags.NonPublic);
int size = ((uint[])bits.GetValue(myBigInt)).Length * sizeof(uint);
请注意,属性名称及其类型是实现细节,然后可能会发生变化,请添加适当的单元测试...
还请注意,ToByteArray().Length
和内部缓冲区可能不同(因为内部缓冲区是sizeof(uint)
字节的倍数,并且最后一个数组项可能为空,请参见内部Length()
方法的实现。)
所有这些都说明Oleksandr Pshenychnyy的funny comment没错,除非您要处理大量数字,并且+/- 1000X(!!!)估计就足够了,那么您可以使用16字节的恒定大小(或32或64 ...)应该足以容纳一个非常大的整数(另请参见Arbitrarily large integers in C#)...
首先,让我们仅考虑正BigInteger,因为负数需要一些附加条件才能正确计算(或可以取反并调用这些方法)。同样对于负值,根据上下文,可以将符号位视为额外位,也可以不考虑符号位...
有两种反射方法,一种是属性,另一种是字段,因此人们提到了大写问题。无论如何,两者都可以轻松完成。这是使用基于this的代码的仅反射解决方案,即使不缓存反射字段/方法,它的执行速度也毫无疑问:
static int GetBitSizeReflection(BigInteger num)
{
//uint[] bits = (uint[])typeof(BigInteger).GetField("_bits", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
uint[] bits = (uint[])typeof(BigInteger).GetProperty("_Bits", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
if (bits == null) {
//int sign = (int)typeof(BigInteger).GetField("_sign", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
int sign = (int)typeof(BigInteger).GetProperty("_Sign", System.Reflection.BindingFlags.Instance | System.Reflection.BindingFlags.NonPublic).GetValue(num);
bits = new uint[] { (uint)(sign < 0 ? sign & int.MaxValue : sign) };
}
int uintLength = (int)typeof(BigInteger).GetMethod("Length", System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic).Invoke(num, new object[] { bits });
int topbits = (int)typeof(BigInteger).GetMethod("BitLengthOfUInt", System.Reflection.BindingFlags.Static | System.Reflection.BindingFlags.NonPublic).Invoke(num, new object[] { bits[uintLength - 1] });
return (uintLength - 1) * sizeof(uint) * 8 + topbits;
对于GetByteSize
例程-只需使用GetBitSize / 8
。
如果您不想采用这种骇人听闻的解决方案,那么这里是一种重复的二进制搜索方法,该方法通常应效率更高,尽管理论上它可能需要对3位(例如1、2、3为速度比1、2、4、3快,尽管稍微优化可能可以解决这种情况。同样,它仅以这种形式对正数BigInteger有效:
static int GetBitSizeRecurseBinSearch(BigInteger num)
{ //instead of 0, 1, 2, 3, 4... use 0, 1, 3, 7, 15, etc
int s = 0, t = 1, oldt = 1;
if (t <= 0) return 0;
while (true) {
if ((BigInteger.One << (s + t)) <= num) { oldt = t; t <<= 1; }
else if (t == 1) break;
else { s += oldt; t = 1; }
}
return s + 1;
}
不幸的是,这不是很有效,但肯定会击败幼稚的方法。
static int GetBitSizeSlow(BigInteger num)
{
int s = 0;
while ((BigInteger.One << s) <= num) s++;
return s;
}
另一方面,如果您希望保留在框架中并且仍然保持快速,那么还有一个版本仅需要一些额外的字节复制,并且是反射后第二快的版本:
static int GetBitSize(BigInteger num)
{
byte[] bytes = num.ToByteArray();
int size = bytes.Length;
if (size == 0) return 0;
int v = bytes[size - 1]; // 8-bit value to find the log2 of
if (v == 0) return (size - 1) * 8;
int r; // result of log2(v) will go here
int shift;
r = (v > 0xF) ? 4 : 0; v >>= r;
shift = (v > 0x3) ? 2 : 0; v >>= shift; r |= shift;
r |= (v >> 1);
return (size - 1) * 8 + r + 1;
}
最后,如果真的更喜欢二进制搜索,那么首先必须在正常的二进制搜索之前对高值进行二进制搜索:
static int GetBitSizeHiSearch(BigInteger num) //power of 2 search high, then binary search
{
if (num.IsZero) return 0;
int lo = 0, hi = 1;
while ((BigInteger.One << hi) <= num) { lo = hi; hi <<= 1; }
return GetBitSizeBinSearch(num, lo, hi);
}
static int GetBitSizeBinSearch(BigInteger num, int lo, int hi)
{
int mid = (hi + lo) >> 1;
while (lo <= hi) {
if ((BigInteger.One << mid) <= num) lo = mid + 1;
else hi = mid - 1;
mid = (hi + lo) >> 1;
}
return mid + 1;
}
但是最快的是反射,其次是获取字节,然后是二进制搜索,然后是递归二进制搜索,最后,朴素的方法是最慢的,可以通过剖析确认,因为数字越来越大(在2 ^(2 ^ 20)肯定会很明显。)
还有一种特殊的字节优化版本,可以从其中的任何一个中得出8的倍数进行搜索。