Konvertieren eines Bereichs in ein Bit-Array

Question

Ich schreibe ein zeitkritisches Stück Code in C#, das erfordert, dass ich zwei vorzeichenlose Ganzzahlen konvertieren, die einen inklusiven Bereich in ein Bitfeld definieren. Ex:

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

Es kann helfen, die Bits in umgekehrter Reihenfolge

Der Maximalwert für diesen Bereich sichtbar zu machen ist ein Parameter zur Laufzeit gegeben, die wir max_val nennen wollen. Daher sollte das Bitfeld Variable als UInt32 Array mit einer Größe gleich max_val/32 definiert werden:

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

Bei einer Reihe von Variablen definiert x1 und x2, was ist der schnellste Weg, um diese Umwandlung durchzuführen?

Answer 1

Versuchen Sie es. Berechnen Sie den Bereich der Array-Elemente, die mit allen Einsen gefüllt werden müssen, indem Sie über diesen Bereich iterieren. Schließlich legen Sie die Elemente an beiden Grenzen fest.

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

Möglicherweise ist der Code nicht 100% korrekt, aber die Idee sollte funktionieren.

---

Nur getestet und gefunden drei Bugs. Die Berechnung beim Startindex erforderte eine Mod 32 und bei Endindex muss die 32 31 sein und eine logische und anstelle einer Zuweisung, um den Fall von Start- und Endindex zu behandeln, der derselbe ist. Sollte ziemlich schnell sein.

---

Gerade Benchmark es mit der gleichen Verteilung von x1 und x2 über das Array. Intel Core 2 Duo E8400 3,0 GHz, MS VirtualPC mit Server 2003 R2 auf Windows XP-Host.

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

---

Eine weitere optimazation x% 32 == x & 31, aber ich bin nicht in der Lage einen Leistungsgewinn meassure. Aufgrund von nur 10.000.000 Iterationen in meinem Test sind die Schwankungen ziemlich hoch. Und ich renne in VirtualPC, was die Situation noch unberechenbarer macht.

Answer 2

Sie könnten versuchen:

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

Answer 3

Gibt es einen Grund, nicht die System.Collections.BitArray Klasse anstelle eines UInt32 [] zu benutzen? Sonst würde ich so etwas versuchen:

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 4

ich langweilig war genug, um es zu tun mit einem char Array zu versuchen und Convert.ToUInt32(string, int) mit auf ein uint von der Basis 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); 
} 

Ein einfacher Benchmark zu konvertieren zeigt, dass meine Methode ist etwa 5% schneller als Angrey Jims (Auch wenn Sie das zweite Pow durch eine Bitverschiebung ersetzen.)

Es ist wahrscheinlich am einfachsten zu einem uint Array zu konvertieren, wenn die obere Grenze zu groß ist, um in eine einzige int zu passen. Es ist ein wenig kryptisch, aber ich glaube, es funktioniert.

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 5

Try this:

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 
*/ 

Answer 6

Meine Lösung eine ganze Reihe von Bits in einem BitArray zu wahr oder falsch für die Einstellung:

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

}