我需要将给定BigInteger的所有低位设置为0,直到只剩下两个1位为止.换句话说,将最高位和第二高位置1,同时不设置所有其他位.

该数字可以是位的任何组合.甚至可能全为1或全为0.例：

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

我们可以轻松地取出一些极端情况,例如0、1,PowerOf2等.不知道如何在表示一个数字的字节数组上应用流行的位操作算法.

我已经查看了bithacks,但有以下限制. BigInteger结构仅通过ToByteArray方法公开基础数据,而该方法本身是昂贵且不必要的.由于无法解决此问题,因此我不想通过实现针对32/64位整数(大多数是32位)优化的位计数算法来进一步降低速度.

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

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

为什么需要执行此操作：我正在使用2D图形,并且对x和y的值是2的幂的坐标特别感兴趣.因此(xy)总是设置两个位,而(xy)总是设置连续的位.给定任意坐标(x,y),我需要通过获取除前两个MSB之外所有位均未设置的值来变换交点.

解决方法:

尝试以下操作(不确定它是否实际上是有效的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编译器,则性能可能会更高.

正如harold正确指出的那样,如果您对数字没有先验知识,则O(n)方法是您可以做的最好的方法.如果可以的话,应该保留两个最高非零字节的位置,这将大大减少执行转换所需的时间.