Lesen in den Speicher von PIC32MX in C und XORing großer Datensätze

Um die Bits so effizient wie möglich zu verarbeiten, sollten Sie sie, wo immer es sinnvoll ist, in 32-Bit-Wörter packen. 816 Bit sind 25,5 Wörter, was wirklich nicht schlecht ist.

Um effizient nach Einsen zu suchen, unterteilen Sie die Aufgabe in zwei Schritte: Überprüfen Sie in der äußeren Schleife ganze Wörter auf Nicht-Null und suchen Sie dann in der inneren Schleife nach einzelnen Bits in den Wörtern, die nicht alle Null sind.

Ein Trick, der verwendet werden kann, um einzelne Bits in einem Wort mit mehreren gesetzten Bits zu isolieren, besteht darin, das Wort mit seiner Negation (2er-Komplement) UND zu verknüpfen. Das Ergebnis hat nur ein einziges gesetztes Bit – die „Eins“ ganz rechts im ursprünglichen Wort. Sie können dieses Ergebnis dann verwenden, um dieses Bit zu löschen und nach der nächsten „Eins“ zu suchen.

In C:

temp = word & -word;
word &= ~temp;

Angenommen, Ihr 32-Bit-Wort enthält 0x40010080:

01000000000000010000000010000000  original word
10111111111111101111111110000000  ... negated
00000000000000000000000010000000  ... and then ANDed together

11111111111111111111111101111111  complement of previous word
01000000000000010000000000000000  ... ANDed with original word for next iteration

BEARBEITEN:

Die Effizienz dieses Algorithmus ergibt sich aus der Tatsache, dass Sie nur einmal für jede „Eins“ (drei davon in diesem Beispiel) iterieren und nicht einmal für jedes der 32 Bits im Wort. Dies ist ein großer Vorteil, wenn Sie so etwas wie das einfache Zählen der Einsen tun. Der Nachteil ist, dass Sie den Bit-Index nicht direkt erhalten, aber es gibt auch Möglichkeiten, dies zu beschleunigen. Um beispielsweise den Bitindex eines einzelnen Bitsatzes in einem Wort zu erhalten, könnten Sie einen binären Codierungsalgorithmus verwenden:

index = 0;
if (word & 0xAAAAAAAA) index += 1;
if (word & 0xCCCCCCCC) index += 2;
if (word & 0xF0F0F0F0) index += 4;
if (word & 0xFF00FF00) index += 8;
if (word & 0xFFFF0000) index += 16;

Der Gesamtvorteil der beiden obigen Algorithmen im Vergleich zu einer Brute-Force-Iteration durch die Bits hängt davon ab, wie viele Bits Sie in jedem Wort erwarten. Wenn sie selten sind (weniger als etwa 4 pro Wort), sollten diese Algorithmen schneller sein. Wenn sie häufiger vorkommen, verwenden Sie einfach die iterative Schleife:

for (index = 0, mask = 0x00000001; index < 32; ++index, mask <<= 1) {
  if (word & mask) {
    /* do your processng here */
  }
}