Was ist der Schnellste Weg, (s), um eine Schleife durch eine große Daten-chunk-pro-bit-basis

Question

Ich führe Sie durch einen Speicher-block von Binärdaten (byte-wise.

Momentan mache ich so etwas wie dieses:

for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    ((*byte & Masks[0]) == Masks[0]) ? Stats.FreqOf1++; // syntax incorrect but you get the point.
    ((*byte & Masks[1]) == Masks[1]) ? Stats.FreqOf1++;
    ((*byte & Masks[2]) == Masks[2]) ? Stats.FreqOf1++;
    ((*byte & Masks[3]) == Masks[3]) ? Stats.FreqOf1++;
    ((*byte & Masks[4]) == Masks[4]) ? Stats.FreqOf1++;
    ((*byte & Masks[5]) == Masks[5]) ? Stats.FreqOf1++;
    ((*byte & Masks[6]) == Masks[6]) ? Stats.FreqOf1++;
    ((*byte & Masks[7]) == Masks[7]) ? Stats.FreqOf1++;
}

Wo Masken ist:

for (i = 0; i < 8; i++)
{
    Masks[i] = 1 << i;
}

(Ich habe irgendwie nicht es tun, zu verwalten, wie schnell Sie in einer Schleife oder in einer inline-Funktion, also schrieb ich es aus.)

Hat jemand irgendwelche Vorschläge auf, wie Sie zur Verbesserung dieser ersten Schleife?Ich bin ziemlich unerfahren mit sich zu bits.

Dies mag wie eine dumme Sache zu tun.Aber ich bin in den Prozess der Implementierung eines Algorithmus zur Komprimierung.Ich will nur den bit-Zugriff auf Artikel unten rechts.

Vielen Dank!

PS:Dies ist in Visual Studio 2008 compiler.So wäre es schön, wenn die Vorschläge angewendet, die compiler.

PPS:Ich habe gerade realisiert, dass ich nicht brauchen, um Inkrement zwei zählt.Man würde genug sein.Dann berechnen Sie die Differenz der Summe der bits am Ende.Aber das wäre spezifisch für einfach zählen.Was will ich wirklich schnell gemacht ist die bit-Extraktion.

EDIT:Die lookup-table-Idee vorverlegt wurde, ist schön.Ich merke aber, dass ich die Frage gestellt, falsch, in den Titel.Denn am Ende, was ich will zu tun ist, nicht zählen die bits, aber der Zugang jedes bit so schnell wie möglich.

NOCH EIN EDIT:Ist es möglich, vorab einen Zeiger durch nur ein bit in den Daten?

NOCH EIN EDIT:Danke für alle Antworten bisher.

Was ich umsetzen will, in der nächsten Schritte ist eine nonsophisticated binary arithmetic coder, die nicht zu analysieren, die den Kontext.Also ich bin nur daran interessiert, einzelne bits für jetzt.Irgendwann wird es eine Kontext-adaptive BAC, aber ich lasse das für später.

Verarbeitung 4 bytes anstelle von 1 byte eine option sein könnte.Aber mit einer Schleife über 32 bits ist kostspielig als auch, nicht wahr?

Answer 1

Ich verstehe nicht wirklich, was Sie zu tun versuchen. Aber wenn Sie nur den Zugriff auf die Bits einer Bitmap erhalten möchten, können Sie diese (nicht getestet !!!) verwenden Funktionen:

#include <stddef.h>

_Bool isbitset(unsigned char * bitmap, size_t idx)
{
    return bitmap[idx / 8] & (1 << (idx % 8)) ? 1 : 0;
}

void setbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] |= (1 << (idx % 8));
}

void unsetbit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] &= ~(1 << (idx % 8));
}

void togglebit(unsigned char * bitmap, size_t idx)
{
    bitmap[idx / 8] ^= (1 << (idx % 8));
}

Edit: Ok, I denken Ich verstehe, was Sie tun möchten: Fast Iteration über eine Sequenz von Bits. Daher wollen wir nicht die Zufallszugriffsfunktionen von oben verwenden, aber ein ganzes Wort von Daten auf einmal lesen.

Sie können eine beliebige unsigned Integer-Typ verwenden, die Sie mögen, aber Sie sollten eine wählen, die auf das Wort Größe Ihrer Architektur entsprechen dürfte. Ich werde mit uint_fast32_t von stdint.h gehen:

uint_fast32_t * data = __data_source__;
for(; __condition__; ++data)
{
    uint_fast32_t mask = 1;
    uint_fast32_t current = *data;
    for(; mask; mask <<= 1)
    {
        if(current & mask)
        {
            // bit is set
        }
        else
        {
            // bit is not set
        }
    }
}

Von der inneren Schleife, können Sie das Bit gesetzt mit

*data |= mask;

ungesetzt das Bit mit

*data &= ~mask;

und drücken Sie dann die Bit mit

*data ^= mask;

Achtung: Der Code wird möglicherweise unerwartet auf Big-Endian-Architekturen verhalten

!

Answer 2

Der schnellste Weg ist wahrscheinlich eine Lookup-Tabelle von Byte-Werten im Vergleich zu der Anzahl der Bits in diesem Byte gesetzt zu bauen. Wenigstens war, dass die Antwort, wenn ich bei Google befragt.

Answer 3

Sehen Sie den folgenden Link für ein Dutzend Bit bezogenes: Bit Twiddling Hacks

Answer 4

Verwenden Sie eine Tabelle, die jedes Byte Wert abbildet (256) auf die Anzahl von 1en in ihm. (Die Anzahl der 0en ist nur (8 - # 1 ist)). Dann durchläuft die Bytes und eine einzelne Abfrage für jedes Byte durchführen, anstelle von mehreren Abfragen und Vergleichen. Zum Beispiel:

int onesCount = 0;
for (i = 0; i < data->Count; i++)
{   
    byte = &data->Data[i];
    onesCount += NumOnes[byte];
}
Stats.FreqOf1 += onesCount;
Stats.FreqOf0 += (data->Count * 8) - onesCount;

Answer 5

Sie könnten eine vorberechnete Verweistabelle verwenden, das heißt:

static int bitcount_lookup[256] = { ..... } ; /* or make it a global and compute the values in code */

...

for( ... ) 
   byte = ... 
   Stats.FreqOf1 += bitcount_lookup[byte];

Answer 6

Hier wird ein Verfahren, wie der 1-Bits eines 32-Bit-Integer-zählen (basierend auf Java Integer.bitCount(i)-Methode):

unsigned bitCount(unsigned i) {
    i = i - ((i >> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >> 2) & 0x33333333);
    i = (i + (i >> 4)) & 0x0f0f0f0f;
    i = i + (i >> 8);
    i = i + (i >> 16);
    return i & 0x3f;
}

So können Sie Ihre Daten werfen können in int und in 4-Byte-Schritten vorwärts zu bewegen.

Answer 7

Hier ist ein einfaches, ich peitschte nur auf einer einzigen 32-bit-Wert, aber Sie können sehen, es würde nicht schwer sein, Sie anzupassen, um eine beliebige Anzahl von bits....

int ones = 0;
int x = 0xdeadbeef;
for(int y = 0;y < 32;y++)
{
    if((x & 0x1) == 0x1) ones++;
    x = (x >> 1);
}

printf("%x contains %d ones and %d zeros.\n", x, ones, 32-ones);

Beachten Sie jedoch, dass es ändert sich der Wert in den Prozess.Wenn Sie tun dies auf Daten, die Sie behalten müssen, dann müssen Sie kopieren Sie Sie zuerst.

Dies zu tun, in __asm wäre wahrscheinlich besser, vielleicht schneller, aber es ist schwer zu sagen, wie gut der compiler optimieren kann...

Mit jeder Lösung, die Sie betrachten, jeder wird Nachteile haben.Eine lookup-Tabelle oder ein bit shifter (wie bei mir), beide haben Nachteile.

Larry

Answer 8

ttobiass - Halten Sie Ihre Inline-Funktionen sind wichtig bei Anwendungen im Auge wie Sie sprechen, aber es gibt Dinge, die man im Auge behalten muß. Sie CAN die Leistung aus dem Inline-Code erhalten, um nur ein paar Dinge erinnern.

• inline im Debug-Modus existiert nicht. (Es sei denn, Sie es erzwingen)
• wird der Compiler Funktionen inline, wie es für richtig hält. Oft, wenn Sie es sagen, eine Funktion inline, kann es nicht tun es überhaupt nicht. Auch wenn Sie __forceinline verwenden. Überprüfen Sie MSDN für weitere Informationen auf inlining.
• können nur bestimmte Funktionen sogar inlined werden. Zum Beispiel können Sie nicht eine rekursive Funktion inline.

Sie werden Ihre beste Leistung aus Ihrer Projekteinstellung für die C / C ++ Sprache erhalten und wie Sie Ihren Code konstruieren. An diesem Punkt ist es wichtig, Heap vs. Stack-Operationen zu verstehen, Aufrufkonventionen, Speicherausrichtung, etc.

Ich weiß, dass dies Ihre Frage nicht genau beantwortet, aber Sie erwähnen Leistung, und wie man die beste Leistung zu erhalten, und diese Dinge sind die Schlüssel.

Answer 9

den Link Wagen verbinden: Bits

Zählen

Answer 10

Ist dies nicht ein Fall der vorzeitigen Optimierung ist, und Sie müssen wirklich jeden letzten Femtosekunden-Squeeze-out, dann sind Sie wahrscheinlich besser dran mit einem 256-Elemente statischen Array, das Sie einmal füllen mit der Bit-Zählung jeden Byte-Wert , dann

  

Stats.FreqOf1 + = bitCountTable [Byte]

und wenn die Schleife erfolgt:

  

Stats.FreqOf0 = ((Daten-> Count * 8) - Stats.FreqOf1)

Answer 11

Es gibt ein ganzes Kapitel über die verschiedenen Techniken für diesen im Buch Schöne-Code . Sie können die (meisten) auf Google Bücher beginnen hier lesen .

Answer 12

Ein schneller Weg Bits zu extrahieren ist zu verwenden:

bitmask= data->Data[i];

while (bitmask)
{
    bit_set_as_power_of_two= bitmask & -bitmask;
    bitmask&= bitmask - 1;
}

Wenn Sie nur gesetzte Bits zählen wollen, eine LUT im Cache pro wäre schnell, aber Sie können es auch tun, in konstanter Zeit mit den verschachtelten Bit-Zählverfahren in der Link in dieser Antwort .