Prototyp und Prozessanalyse des Java-Quellcodes Integer.bitCount-Algorithmus (mit Code)

Algorithmus: Zählen Sie die Anzahl der Bits im Binärausdruck der Ganzzahl, die 1 sind (Gewöhnlicher Algorithmus): Dies sollte der erste Algorithmus sein, der Ihnen in den Sinn kommt. Zählen Sie die Anzahl der Bits eins nach dem anderen ist 1, die Zeitkomplexität ist O(n) und n ist die Gesamtzahl der Bits. Optimierungsalgorithmus: Dieser Algorithmus erscheint auf den ersten Blick verwirrend, aber wenn Sie sorgfältig darüber nachdenken, können Sie das Prinzip finden: Nach n-1 wird das niedrigste Bit 1 von n eliminiert und dann mit n Bits UND-verknüpft, wird n zum niedrigsten Bit 1 und wird auf 0 gesetzt. Die neue Ganzzahl danach.

Gewöhnlicher Algorithmus

public int bitCount(int num) {
    int count = 0;
    do {
        if ((num & 1) == 1) {
            count++;
        }
        num>>=1;
    } while (num > 0);
    return count;
}

sollte der erste Algorithmus sein, der mir in den Sinn kommt, ausgehend vom niedrigsten Bit, wenn man zählt, ob es eins nach dem anderen ist, ist die Zeitkomplexität O(n), n die Gesamtzahl der Bits.

Optimierungsalgorithmus

public int countBit2(int num) {
    int count = 0;
    while (num > 0) {
        num = num & (num - 1);
        count++;
    }
    return count;
}

Dieser Algorithmus scheint zunächst verwirrend, aber wenn man genau darüber nachdenkt, findet man auch das Prinzip: n-1Danach wird die niedrigste 1 von n eliminiert , und dann mit n Bit AND wird n zu einer neuen Ganzzahl, nachdem das niedrigste Bit 1 auf 0 gesetzt wurde, wie zum Beispiel:

0b101100  减一  0b101011 最低位的1消除，0b101100 & 0b101011 = 0b101000

Es wird in diesem Zyklus so oft wie möglich Einsen geben, und die Die zeitliche Komplexität ist ebenfalls O(n), aber dieses n stellt das Bit dar. Die Zahl 1 ist im Allgemeinen besser als die vorherige.
Wenn wir denken, dass dies der optimale Algorithmus ist, ist das nicht der Fall

Integer.bitCount

public static int bitCount(int i) {
    // HD, Figure 5-2
    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;
}

Schließlich hat die Integer-Klasse von Java tatsächlich eine Methode zum Zählen von Bits bereitgestellt Bit ( Vorzeichenlose Rechtsverschiebung, negative Zahlen können gezählt werden), auf den ersten Blick WTF?
Prinzip: Stellen Sie sich vor, wenn eine Spalte mit 1 vor unserem menschlichen Gehirn platziert wird, wie werden wir dann zählen? Zahl für Zahl, das Prinzip des ersten Algorithmus. Oder zwei mal zwei zählen? So wird diese Methode umgesetzt. Wie im Bild unten gezeigt:

             二进制                       十进制
 1  0   1  1   1  1   1  1   1  1     10 11 11 11 11
  01     10     10     10     10       1 2  2  2  2
          \     /       \     /           \/    \/
  01       0100           0100         1   4    4
                \       /                   \  /
  01               1000                1      8
      \          /                       \   /
          1001                             9
          
              767的二进制中的1的位数计算过程

Alle zwei Bits sind eine Gruppe, zählen jeweils die Anzahl der Einsen und speichern dann das Ergebnis in diesen beiden Bits, zum Beispiel: 11 hat 2 Einsen, das Ergebnis ist 10, 10 ersetzt 11 und wird am ursprünglichen Speicherort gespeichert. Führen Sie dann Additionsrechnungen durch und addieren Sie alle Ergebnisse. Während des Additionsprozesses können Sie jeweils zwei addieren, um den Berechnungsprozess zu verkürzen.

Zwei Bits berechnen die Anzahl der Einsen: 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1, also ist es klar.

Der Algorithmus wird wie folgt implementiert:

• Zuerst wird das linke Bit der Ganzzahl i gelöscht: i & 0x55555555, und dann wird der Offset hinzugefügt. (i >>> 1) & 0x55555555 bedeutet: Verschieben Sie das linke Bit nach rechts und löschen Sie dann das linke Bit, sodass Sie die Anzahl der Einsen auf den beiden Bits berechnen können: 0b1011=>0b0001 + 0b0101 = 0b0110 In den linken beiden Bits steht 1 1, und das gibt es 2 Einsen in den rechten beiden Bits.

• Zu diesem Zeitpunkt werden die statistischen Ergebnisse von jeweils zwei Ziffern in i gespeichert, die paarweise addiert und schließlich summiert werden können.

Prozess:

0x55555555  ‭0b01010101010101010101010101010101‬
0x33333333  ‭0b00110011001100110011001100110011‬
0x0f0f0f0f  ‭0b00001111000011110000111100001111‬
0x00ff00ff  0b00000000111111110000000011111111
0x0000ffff  ‭0b00000000000000001111111111111111‬
0x3f        ‭0b00111111‬

0b11 11 11 11 11    (i & 0x55555555) + ((i >>> 1) & 0x55555555)  = 0b0101010101‬ + 0b0101010101 = 0b1010101010
0b10 10 10 10 10    (i & 0x33333333) + ((i >>> 2) & 0x33333333) = 0b1000100010 + 0b00100010 = 0b1001000100
0b10 01 00 01 00    (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f) = 0b1000000100 + 0b0100 = 0b1000001000
0b10 00 00 10 00    (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff) = 0b1000 + 0b10 = 0b1010
0b00 00 00 10 10    (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff) = 0b1010 + 0 = 0b1010
dec           10

Algorithmus-Prototyp:

public static int bitCount(int i) {
    i = (i & 0x55555555) + ((i >>> 1) & 0x55555555);
    i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
    i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f);
    i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff);
    i = (i & 0x0000ffff) + ((i >>> 16) & 0x0000ffff);
    return i;
}

Zeitkomplexität O(1), ok, großartig! Aber wenn Sie einen Artikel schreiben, müssen Sie ihn aufpolieren, ganz zu schweigen vom Algorithmus, und dann ist die Optimierung die Implementierung in Integer.
Optimierung:

• Schritt 1: Berechnen Sie die Anzahl der Einsen mit zwei Bits: 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1. Die Untersuchung ergab, dass: 2=0b11-0b1, 1=0b10-0b1 die Berechnung einmal reduzieren kann: i = i - ((i >>> 1) & 0x55555555)

• Schritt 2: Derzeit gibt es keine gute Optimierungsmethode

• Der dritte Schritt: Berechnen Sie tatsächlich die Anzahl der Einsen in jedem Byte, bis zu 8 (0b1000), was 4 Bits entspricht. Sie können schließlich eine bitweise UND-Verknüpfung durchführen, um Bits zu eliminieren und so eine & Operation zu reduzieren: i = (i + (i >>> 4)) & 0x0f0f0f0f

• Schritt 4 und 5: Aus dem gleichen Grund wie oben, Sie können die Position am Ende eliminieren. Da int jedoch höchstens 32 (0b100000) 1s hat, besteht in diesen beiden Schritten keine Notwendigkeit, Bits zu löschen. Der letzte Schritt besteht darin, die unnötigen Bits zu löschen: i & 0x3f

Einblicke: Der einfachste, scheinbar komplexe Algorithmus, aber sein Implementierungsprinzip ist die einfache Denklogik unseres Gehirns

7    0b111
i = 7 - ((7>>>1) & 0x55555555) = 6 = 0b110
i = (6 & 0x33333333) + ((6 >>> 2) & 0x33333333) = 2 + 1 = 3 = 0b11
i = (3 + (i >>> 4)) & 0x0f0f0f0f = 3 & 0x0f0f0f0f = 3 = 0b11
i = 3 + (3 >>> 8) = 3 = 0b11
i = 3 + (3 >>> 16) = 3 = 0b11
i = 3 & 0x3f = 3

Verwandte Artikel:

Detaillierte Erklärung der Java-Referenzquelle Code-Analysecode

Java-Quellcode-Analyse Arrays.asList-Methode, detaillierte Erklärung

Ähnliche Videos:

Umfassende Analyse von Java Anmerkungen

Das obige ist der detaillierte Inhalt vonPrototyp und Prozessanalyse des Java-Quellcodes Integer.bitCount-Algorithmus (mit Code). Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!