Bitfields em C #

Question

Assim, bitfields. Especificamente, grandes campos de bits. Eu entendo como manipular valores individuais em um campo de bits, mas como eu iria sobre como fazer isso em um grande conjunto, como por exemplo:

uint[] bitfield = new uint[4] { 0x0080000, 0x00FA3020, 0x00C8000, 0x0FF00D0 };

O problema específico que eu estou tendo está fazendo mudanças certas que deixou e realizar com êxito em toda a matriz. Assim, por exemplo, se eu fiz um >> 4 na matriz acima, eu ia acabar com:

uint[4] { 0x0008000, 0x000FA302, 0x000C800, 0x00FF00D };

Agora, um (excessivamente) algoritmo simplista aqui poderia ser algo como (este código está me escrevendo em tempo real):

int shift = 4;
for (int i = 0; i <= shift; i++) {
    for (int j = bitfield.GetUpperBound(0); j > 0; j--) {
        bitfield[j] = bitfield[j] >> 1;
        bitfield[j] = bitfield[j] + ((bitfield[j-1] & 1) << (sizeof(uint)*8));
    }
    bitfield[0] = bitfield[0] >> 1;
}

Há algo construído em que pode facilitar o trabalho com este tipo de dados?

Answer 1

O que faz você pensar que BitArray usa bools internamente? Ele usa valores booleanos para representar os bits em termos da API, mas sob o capô Eu acredito que usa um int [].

Answer 2

Eu não tenho certeza se é a melhor maneira de fazê-lo, mas isso poderia funcionar (restringindo turnos para estar na faixa de 0-31.

    public static void ShiftLeft(uint[] bitfield, int shift) {

        if(shift < 0 || shift > 31) {
            // handle error here
            return;
        }

        int len = bitfield.Length;
        int i = len - 1;
        uint prev = 0;

        while(i >= 0) {
            uint tmp        = bitfield[i];
            bitfield[i] = bitfield[i] << shift;
            if(i < len - 1) {
                bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
            }
            prev = tmp;

            i--;
        }

    }

    public static void ShiftRight(uint[] bitfield, int shift) {

        if(shift < 0 || shift > 31) {
            // handle error here
            return;
        }
        int len = bitfield.Length;
        int i = 0;
        uint prev = 0;

        while(i < len) {
            uint tmp        = bitfield[i];
            bitfield[i] = bitfield[i] >> shift;
            if(i > 0) {
                bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
            }
            prev = tmp;

            i++;
        }

    }

PD: Com esta mudança, você deve ser capaz de lidar com mudanças maiores que 31 bits. Poderia ser reformulado para torná-la um pouco menos feio, mas em meus testes, ele funciona e não parece muito ruim em termos de performance (a menos que, há realmente algo construído em lidar com grandes bitsets, o que poderia ser o caso).

    public static void ShiftLeft(uint[] bitfield, int shift) {

        if(shift < 0) {
            // error
            return;
        } 

        int intsShift = shift >> 5;

        if(intsShift > 0) {
            if(intsShift > bitfield.Length) {
                // error
                return;
            }

            for(int j=0;j < bitfield.Length;j++) {
                if(j > intsShift + 1) {     
                    bitfield[j] = 0;
                } else {
                    bitfield[j] = bitfield[j+intsShift];
                }
            }

            BitSetUtils.ShiftLeft(bitfield,shift - intsShift * 32);
            return;
        }

        int len = bitfield.Length;
        int i = len - 1;
        uint prev = 0;

        while(i >= 0) {
            uint tmp    = bitfield[i];
            bitfield[i] = bitfield[i] << shift;
            if(i < len - 1) {
                bitfield[i] |= (uint)(prev & (1 >> shift) - 1 ) >> (32 - shift);
            }
            prev = tmp;

            i--;
        }

    }

    public static void ShiftRight(uint[] bitfield, int shift) {

        if(shift < 0) {
            // error
            return;
        } 

        int intsShift = shift >> 5;

        if(intsShift > 0) {
            if(intsShift > bitfield.Length) {
                // error
                return;
            }

            for(int j=bitfield.Length-1;j >= 0;j--) {
                if(j >= intsShift) {        
                    bitfield[j] = bitfield[j-intsShift];
                } else {
                    bitfield[j] = 0;
                }
            }

            BitSetUtils.ShiftRight(bitfield,shift - intsShift * 32);
            return;
        }


        int len = bitfield.Length;
        int i = 0;
        uint prev = 0;

        while(i < len) {
            uint tmp    = bitfield[i];
            bitfield[i] = bitfield[i] >> shift;
            if(i > 0) {
                bitfield[i] |= (uint)(prev & (1 << shift) - 1 ) << (32 - shift);
            }
            prev = tmp;

            i++;
        }

    }

Answer 3

Usando métodos de extensão, você poderia fazer isso:

public static class BitArrayExtensions
{
    public static void DownShift(this BitArray bitArray, int places)
    {
        for (var i = 0; i < bitArray.Length; i++)
        {
            bitArray[i] = i + places < bitArray.Length && bitArray[i + places];
        }
    }

    public static void UpShift(this BitArray bitArray, int places)
    {
        for (var i = bitArray.Length - 1; i >= 0; i--)
        {
            bitArray[i] = i - places >= 0 && bitArray[i - places];
        }
    }
}

Infelizmente, eu não poderia vir acima com uma maneira de sobrecarregar os operadores de deslocamento. (Principalmente porque BitArray está selado.)

Se você pretende manipular ints ou uints, você pode criar métodos de extensão para a inserção de bits em / extrair bits da BitArray. (BitArray tem um construtor que leva uma série de ints, mas isso só leva você até lá.)

Answer 4

Esta não cobre especificamente mudando, mas poderia ser útil para trabalhar com grandes conjuntos. É em C, mas eu acho que poderia ser facilmente adaptado para C #

Existe um limite prático ao tamanho de máscaras de bits?