Kann die Anzahl der bitweisen Übergänge in einer 8-Bit-Ganzzahl bestimmt werden?

Question

Ich kann nicht scheinen, etwas Magie auf diesem zu finden, also hatte ich gehofft, dass jemand hier ein kleines Licht geben könnte, wenn das überhaupt möglich ist.

Ich versuche die Anzahl der bitweisen Übergänge in einer 8-Bit-Ganzzahl (die ganze Zahl ist eigentlich eine 32-Bit-Ganzzahl, aber ich benutze nur die ersten 8 Bits) zu bestimmen, ob die 8 Bits einheitlich sind (2 oder weniger Übergänge).

Zum Beispiel:

00100000 - two transitions - uniform 
00100001 - three transitions - not uniform 
10101010 - seven transitions - not uniform 
00000000 - no transitions - uniform 

Gibt es einen schnelleren Weg, um die Anzahl der Übergänge andere als Schleife durch jedes Bit (Schleife durch jedes Bit ist derzeit die einzige Lösung, die ich mit oben kommen kann) zu finden?

Answer 1

Sie können x-oder den Wert mit dem Wert um ein Bit verschoben und dann die Zahl 1 im Ergebnis zählen.

unsigned v = (x^(x>>1)) & 0x7F; 
unsigned count = 0; 
while (v) { 
    count++; 
    v &= (v - 1); 
} 

Beachten Sie auch, dass ein Byte nur 256 Konfigurationen aufweisen, so dass die Berechnung erfolgt einmal und in einem sehr kleinen Tisch von 256 Bytes gesetzt werden kann.

Wenn Sie wollen nur wissen, ob es 2 oder weniger ändert die Schleife entrollt werden kann:

unsigned v = (x^(x >> 1)) & 0x7F; 
v &= v - 1; 
v &= v - 1; 
uniform = (v == 0); 

Beachten Sie, dass diese Berechnung auf, wie groß ist die Zahl unabhängig ist und Sie beispielsweise direkt ein verwenden können 32-Bit-Zahl ohne Vorzeichen (das einzige, was die Maske ändert, ist die 0x7FFFFFFF wird)

Answer 2

Für Ihre Definition einheitlicher, die Zahl hat in Form 00011111 oder 11110000 sein. Betrachten Sie die vorherige (Nullen gefolgt von Einsen).

Fügen Sie einen Wert hinzu. Wenn es einheitlich ist, würde es genau ein 1 Bit haben, was eine Leistung von 2 bedeutet.

Um zu testen, ob ein Wert eine Potenz von zwei ist, verwenden Sie (x & (x - 1)) == 0. Um den Code zu verkürzen, müssen Sie im vorherigen Schritt keinen Code hinzufügen. Stattdessen überprüfen wir (x & (x + 1)) == 0

Wenden Sie dies auf den anderen Fall an, indem Sie den Anfangswert NOT-in und wiederholen Sie den obigen Vorgang.

#include <cstdio> 
bool isuniform(unsigned char x) { 
    unsigned char y = ~x; 
    return (x & (x + 1)) == 0 || (y & (y + 1)) == 0; 
} 
int main() { 
    printf("%d\n", isuniform(0)); // 00000000 
    printf("%d\n", isuniform(1)); // 00000001 
    printf("%d\n", isuniform(3)); // 00000011 
    printf("%d\n", isuniform(7)); // 00000111 
    printf("%d\n", isuniform(15)); // 00001111 
    printf("%d\n", isuniform(31)); // 00011111 
    printf("%d\n", isuniform(63)); // 00111111 
    printf("%d\n", isuniform(127)); // 01111111 
    printf("%d\n", isuniform(255)); // 11111111 
    printf("%d\n", isuniform(254)); // 11111110 
    printf("%d\n", isuniform(252)); // 11111100 
    printf("%d\n", isuniform(248)); // 11111000 
    printf("%d\n", isuniform(240)); // 11110000 
    printf("%d\n", isuniform(224)); // 11100000 
    printf("%d\n", isuniform(192)); // 11000000 
    printf("%d\n", isuniform(128)); // 10000000 
    //---------- 
    printf("%d\n", isuniform(2)); 
    printf("%d\n", isuniform(4)); 
    printf("%d\n", isuniform(50)); 
    printf("%d\n", isuniform(123)); 
    printf("%d\n", isuniform(129)); 
    printf("%d\n", isuniform(253)); 
    return 0; 
}