Les champs de bits en C #

Question

Donc, les champs de bits. Plus précisément, les grands champs de bits. Je comprends comment manipuler des valeurs individuelles dans un champ de bits, mais comment pourrais-je procéder pour le faire sur un grand ensemble, comme par exemple:

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

Le problème spécifique que je rencontre est celui des décalages gauche et droite qui se répercutent sur l’ensemble du réseau. Ainsi, par exemple, si je faisais un > > 4 sur le tableau ci-dessus, je finirais avec:

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

Maintenant, un algorithme (trop) simpliste ici pourrait ressembler à (c'est moi qui écrit le code à la volée):

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;
}

Existe-t-il un outil intégré qui pourrait faciliter l'utilisation de ce type de données?

Answer 1

Qu'est-ce qui vous fait penser que BitArray utilise des bools en interne? Il utilise des valeurs booléennes pour représenter les bits en termes d’API, mais je pense qu’il utilise un int [].

Answer 2

Je ne sais pas si c'est la meilleure façon de le faire, mais cela pourrait fonctionner (les changements contraignants se situeraient dans la plage 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: Avec ce changement, vous devriez pouvoir gérer des décalages supérieurs à 31 bits. Pourrait être repensé pour le rendre un peu moins laid, mais dans mes tests, cela fonctionne et cela ne semble pas trop mal en termes de performances (à moins que, quelque chose de réellement intégré pour gérer de gros bits, ce qui pourrait être le cas).

    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

En utilisant des méthodes d'extension, vous pouvez faire ceci:

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];
        }
    }
}

Malheureusement, je ne pouvais pas trouver un moyen de surcharger les opérateurs de postes. (Principalement parce que BitArray est scellé.)

Si vous avez l'intention de manipuler des int ou des uint , vous pouvez créer des méthodes d'extension pour insérer des bits dans / extraire des bits du BitArray . . ( BitArray a un constructeur qui prend un tableau de int , mais cela ne vous mène que jusque-là.)

Answer 4

Cela ne couvre pas spécifiquement le décalage, mais pourrait être utile pour travailler avec de grands ensembles. C'est en C, mais je pense que ça pourrait être facilement adapté au C #

Y a-t-il une limite pratique à la taille des masques de bits?