3

我需要将给定 BigInteger 的所有低位设置为 0，直到只剩下两个 1 位。换句话说，保留最高位和次高位设置，同时取消设置所有其他位。

该数字可以是位的任意组合。它甚至可能全为 1 或全为 0。例子：

MSB    0000 0000
       1101 1010
       0010 0111
       ...
       ...
       ...
LSB    0100 1010

我们可以轻松解决诸如 0、1、PowerOf2 等极端情况。不知道如何在表示一个数字的字节数组上应用流行的位操作算法。

我已经看过bithacks但有以下限制。BigInteger 结构仅通过 ToByteArray 方法公开底层数据，这本身是昂贵且不必要的。由于没有办法解决这个问题，我不想通过实现针对 32/64 位整数（大多数都是）优化的位计数算法来进一步减慢速度。

简而言之，我有一个字节 [] 代表一个任意大的数字。速度是这里的关键因素。

注意：如果有帮助，我正在处理的数字大约有 5,000,000 位。它们随着算法的每次迭代而不断减少，因此我可能会随着数量的减少而切换技术。

为什么我需要这样做：我正在使用 2D 图形，并且对 x 和 y 值是 2 的幂的坐标特别感兴趣。因此 (x+y) 将始终设置两个位，并且 (xy) 将始终具有连续的位设置。给定一个任意坐标 (x, y)，我需要通过获取除前两个 MSB 之外的所有位未设置的值来转换交集。

4

2 回答 2

2

尝试以下操作（不确定它是否实际上是有效的 C#，但它应该足够接近）：

// find the next non-zero byte (I'm assuming little endian) or return -1
int find_next_byte(byte[] data, int i) {
    while (data[i] == 0) --i;
    return i;
}

// find a bit mask of the next non-zero bit or return 0
int find_next_bit(int value, int b) {
    while (b > 0 && ((value & b) == 0)) b >>= 1;
    return b;
}

byte[] data;

int i = find_next_byte(data, data.Length - 1);
// find the first 1 bit
int b = find_next_bit(data[i], 1 << 7);
// try to find the second 1 bit
b = find_next_bit(data[i], b >> 1);
if (b > 0) {
    // found 2 bits, removing the rest
    if (b > 1) data[i] &= ~(b - 1);
} else {
    // we only found 1 bit, find the next non-zero byte
    i = find_next_byte(data, i - 1);
    b = find_next_bit(data[i], 1 << 7);
    if (b > 1) data[i] &= ~(b - 1);
}

// remove the rest (a memcpy would be even better here,
// but that would probably require unmanaged code)
for (--i; i >= 0; --i) data[i] = 0;

未经测试。

如果编译为非托管代码，甚至使用 C 或 C++ 编译器，这可能会更高效。

正如哈罗德正确指出的那样，如果您对自己的号码没有先验知识，那么这种O(n)方法是您能做的最好的。如果可以，您应该保留最高两个非零字节的位置，这将大大减少执行转换所需的时间。

于 2012-08-19T21:25:27.670 回答
1

我不确定这是否得到优化，但这段代码似乎比 ToByteArray 快 16 倍。它还避免了内存复制，这意味着您以 uint 而不是 byte 形式获得结果，因此您应该在那里进行进一步的改进。

//create delegate to get private _bit field
var par = Expression.Parameter(typeof(BigInteger));
var bits = Expression.Field(par, "_bits");
var lambda = Expression.Lambda(bits, par);
var func = (Func<BigInteger, uint[]>)lambda.Compile();

//test call our delegate
var bigint = BigInteger.Parse("3498574578238348969856895698745697868975687978");
int time = Environment.TickCount;
for (int y = 0; y < 10000000; y++)
{
    var x = func(bigint);
}
Console.WriteLine(Environment.TickCount - time);

//compare time to ToByteArray
time = Environment.TickCount;
for (int y = 0; y < 10000000; y++)
{
    var x = bigint.ToByteArray();
}
Console.WriteLine(Environment.TickCount - time);

从那里找到前 2 位应该很容易。第一位将在我假设的第一个 int 中，然后只需搜索第二个最高位即可。如果它在同一个整数中，则只需将第一位设置为零并找到最高位，否则搜索下一个非零 int 并找到最高位。

编辑：为了简单起见，只需将此类复制/粘贴到您的项目中即可。这会创建扩展方法，这意味着您只需调用 mybigint.GetUnderlyingBitsArray()。我还添加了一个获取 Sign 的方法，并且为了使其更通用，创建了一个函数，该函数将允许访问任何对象的任何私有字段。我发现这比调试模式下的原始代码慢，但在发布模式下速度相同。我建议您自己进行性能测试。

static class BigIntegerEx
{
    private static Func<BigInteger, uint[]> getUnderlyingBitsArray;
    private static Func<BigInteger, int> getUnderlyingSign;

    static BigIntegerEx()
    {
        getUnderlyingBitsArray = CompileFuncToGetPrivateField<BigInteger, uint[]>("_bits");
        getUnderlyingSign = CompileFuncToGetPrivateField<BigInteger, int>("_sign");
    }

    private static Func<TObject, TField> CompileFuncToGetPrivateField<TObject, TField>(string fieldName)
    {
        var par = Expression.Parameter(typeof(TObject));
        var field = Expression.Field(par, fieldName);
        var lambda = Expression.Lambda(field, par);
        return (Func<TObject, TField>)lambda.Compile();
    }

    public static uint[] GetUnderlyingBitsArray(this BigInteger source)
    {
        return getUnderlyingBitsArray(source);
    }

    public static int GetUnderlyingSign(this BigInteger source)
    {
        return getUnderlyingSign(source);
    }
}
于 2012-08-19T23:16:29.460 回答