Conversion d'une plage dans un tableau de bits

Question

J'écris un morceau de temps critique de code en C # qui me demande de convertir deux entiers non signés qui définissent une plage inclusive dans un champ de bits. Ex:

uint x1 = 3;
uint x2 = 9;
  //defines the range [3-9]
  //                              98  7654 3
  //must be converted to:  0000 0011  1111 1000

Il peut aider à visualiser les bits dans l'ordre inverse

La valeur maximale de cette plage est un paramètre donné à l'exécution que nous appellerons max_val. Par conséquent, la grandeur de champ de bits doit être défini comme un réseau de UInt32 avec une taille égale à max_val/32:

UInt32 MAX_DIV_32 = max_val / 32;
UInt32[] bitArray = new UInt32[MAX_DIV_32];

Étant donné une plage définie par les variables x1 et x2, quelle est la plus rapide pour effectuer cette conversion?

Answer 1

Essayez ceci. Calculer la gamme des éléments du tableau qui doit être rempli avec tous ceux et font par itérer sur cette plage. Enfin fixer les éléments aux deux frontières.

Int32 startIndex = x1 >> 5;
Int32 endIndex = x2 >> 5;

bitArray[startIndex] = UInt32.MaxValue << (x1 & 31);

for (Int32 i = startIndex + 1; i <= endIndex; i++)
{
   bitArray[i] = UInt32.MaxValue;
}

bitArray[endIndex] &= UInt32.MaxValue >> (31 - (x2 & 31));

Peut-être le code est 100% correct, mais l'idée devrait fonctionner.

---

Juste testé et trouvé trois bugs. Le calcul à l'index de démarrage requis un mod 32 et à l'index final 32 doit être 31 et une logique et au lieu d'une affectation à traiter le cas de démarrage et l'indice final étant le même. Devrait être assez rapide.

---

Il suffit benchmarkée avec une répartition égale de x1 et x2 sur le tableau. Intel Core 2 Duo E8400 3.0 GHz, MS VirtualPC avec le serveur 2003 R2 sur l'hôte Windows XP.

Array length [bits]           320         160         64
Performance [executions/s]    33 million  43 million  54 million

---

Un plus optimazation x% x 32 == et 31, mais je ne peux pas meassure un gain de performance. En raison de seulement 10.000.000 itérations dans mon test, les fluctuations sont assez élevées. Et je courais en VirtualPC rendant la situation encore plus imprévisible.

Answer 2

Ma solution pour régler toute une gamme de bits dans une BitArray true ou false:

public static BitArray SetRange(BitArray bitArray, Int32 offset, Int32 length, Boolean value)
{

    Int32[] ints = new Int32[(bitArray.Count >> 5) + 1];

    bitArray.CopyTo(ints, 0);

    var firstInt = offset >> 5;
    var lastInt = (offset + length) >> 5;

    Int32 mask = 0;

    if (value)
    {
        // set first and last int
        mask = (-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] |= ~(-1 << ((offset + length) & 31));
        else
            mask &= ~(-1 << ((offset + length) & 31));

        ints[firstInt] |= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = -1;
    }

    else
    {
        // set first and last int
        mask = ~(-1 << (offset & 31));
        if (lastInt != firstInt)
            ints[lastInt] &= -1 << ((offset + length) & 31);
        else
            mask |= -1 << ((offset + length) & 31);

        ints[firstInt] &= mask;

        // set all ints in between
        for (Int32 i = firstInt + 1; i < lastInt; i++)
            ints[i] = 0;

    }

    return new BitArray(ints) { Length = bitArray.Length };

}

Answer 3

Vous pouvez essayer:

UInt32 x1 = 3;
UInt32 x2 = 9;
UInt32 newInteger = (UInt32)(Math.Pow(2, x2 + 1) - 1) & 
                   ~(UInt32)(Math.Pow(2, x1)-1);

Answer 4

Y at-il une raison de ne pas utiliser la classe System.Collections.BitArray au lieu d'un UInt32 []? Sinon, je vais essayer quelque chose comme ceci:

int minIndex = (int)x1/32;
int maxIndex = (int)x2/32;
// first handle the all zero regions and the all one region (if any)
for (int i = 0; i < minIndex; i++) {
    bitArray[i] = 0;
}
for (int i = minIndex + 1; i < maxIndex; i++) {
    bitArray[i] = UInt32.MaxValue; // set to all 1s
}
for (int i = maxIndex + 1; i < MAX_DIV_32; i++) {
    bitArray[i] = 0;
}

// now handle the tricky parts
uint maxBits = (2u << ((int)x2 - 32 * maxIndex)) - 1; // set to 1s up to max
uint minBits = ~((1u << ((int)x1 - 32 * minIndex)) - 1); // set to 1s after min

if (minIndex == maxIndex) {
    bitArray[minIndex] = maxBits & minBits;
}
else {
    bitArray[minIndex] = minBits;
    bitArray[maxIndex] = maxBits;
}

Answer 5

J'ai été assez ennuyé pour essayer de le faire avec un tableau de char et en utilisant Convert.ToUInt32(string, int) pour convertir en uint de base 2.

uint Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }
  return Convert.ToUInt32(new string(buffer), 2);
}

Une référence simple montre que ma méthode est d'environ 5% plus rapide que Angrey Jim (même si vous remplacez deuxième Pow avec un décalage de bits).

Il est probablement le plus facile à convertir à la production d'un tableau de uint si la limite supérieure est trop grand pour tenir dans un seul int. Il est un peu cryptique, mais je crois que cela fonctionne.

uint[] Range(int l, int h)
{
  char[] buffer = new char[h];
  for (int i = 0; i < buffer.Length; i++)
  {
    buffer[i] = i < h - l ? '1' : '0';
  }

  int bitsInUInt = sizeof(uint) * 8;
  int numNeededUInts = (int)Math.Ceiling((decimal)buffer.Length /
                                         (decimal)bitsInUInt);
  uint[] uints = new uint[numNeededUInts];
  for (int j = uints.Length - 1, s = buffer.Length - bitsInUInt;
       j >= 0 && s >= 0;
       j--, s -= bitsInUInt)
  {
    uints[j] = Convert.ToUInt32(new string(buffer, s, bitsInUInt), 2);
  }

  int remainder = buffer.Length % bitsInUInt;
  if (remainder > 0)
  {
    uints[0] = Convert.ToUInt32(new string(buffer, 0, remainder), 2);
  }

  return uints;
}

Answer 6

Essayez ceci:

uint x1 = 3;
uint x2 = 9;

int cbToShift = x2 - x1; // 6
int nResult = ((1 << cbToShift) - 1) << x1; 

/*
  (1<<6)-1 gives you 63 = 111111, then you shift it on 3 bits left
*/