Code source Java Prototype d'algorithme Integer.bitCount et analyse de processus (avec code)

Algorithme : Comptez le nombre de bits dans l'expression binaire de l'entier qui valent 1 (poids de Hamming). Cela devrait être le premier algorithme qui vous vient à l'esprit. En partant du bit le plus bas, comptez le nombre de bits. un par un vaut 1, la complexité temporelle est O(n) et n est le nombre total de bits. Algorithme d'optimisation : Cet algorithme semble déroutant à première vue, mais si on y réfléchit bien, on retrouve le principe : après n-1, le bit le plus bas 1 de n est éliminé, puis on fait un AND avec n bits, n devient le plus bas bit 1 et est mis à 0 Le nouvel entier après.

L'algorithme ordinaire

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

devrait être le premier algorithme qui vient à l'esprit. En partant du bit le plus bas, en comptant s'il est 1 un par un, la complexité temporelle est O(n), n est le nombre total de bits.

Algorithme d'optimisation

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

Cet algorithme semble déroutant à première vue, mais si vous y réfléchissez bien, vous pouvez trouver le principe : n-1 Après cela, le 1 le plus bas de n est éliminé, puis Et avec n bits, n devient un nouvel entier une fois que le bit le plus bas 1 est défini sur 0, tel que :

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

Il y aura autant de 1 que possible tout au long de ce cycle, et la complexité temporelle est également O(n), mais ce n représente le nombre de bits qui valent 1, ce qui est généralement meilleur que le précédent.
Quand on pense que c'est l'algorithme optimal, ce n'est pas le cas

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

Enfin, en fait, la classe Integer de Java a fourni une méthode pour les bits statistiques (décalage à droite non signé, les nombres négatifs peuvent être comptés), à première vue, WTF
Principe : Imaginez que lorsqu'une colonne de 1 est placée devant notre cerveau humain, comment allons-nous compter ? Numéro par numéro, le principe du premier algorithme. Ou compter deux par deux ? C'est ainsi que cette méthode est mise en œuvre. Comme indiqué ci-dessous :

             二进制                       十进制
 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的位数计算过程

Chaque deux bits constituent un groupe, comptez respectivement le nombre de 1, puis stockez le résultat dans ces deux bits, par exemple : 11 a 2 1, le résultat Pour 10, 10 remplace 11 et est stocké à l'emplacement d'origine. Effectuez ensuite des calculs d’addition et additionnez tous les résultats. Pendant le processus d'addition, vous pouvez en ajouter deux par deux pour réduire le processus de calcul.

Deux bits calculent le nombre de 1 : 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b01 + 0b00 = 0b01 = 1, donc c'est clair.

L'algorithme est implémenté comme suit :

• Tout d'abord, le bit gauche de l'entier i est effacé : i & 0x55555555, puis le décalage est ajouté. (i >>> 1) & 0x55555555 signifie : déplacer le bit de gauche vers la droite, puis effacer le bit de gauche, pour pouvoir calculer le nombre de 1 sur les deux bits : 0b1011=>0b0001 + 0b0101 = 0b0110 Il y a 1 1 dans les deux bits de gauche, et il y a 2 1 dans les deux bons bits.

• A ce moment, les résultats statistiques de chaque deux chiffres sont stockés dans i, qui peuvent être ajoutés par paires et finalement additionnés.

Processus :

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

Prototype d'algorithme :

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

Complexité temporelle O(1), ok, super ! Mais lors de la rédaction d'un article, vous devez le peaufiner, sans parler de l'algorithme, et celui optimisé est l'implémentation dans Integer.
Optimisation :

• Étape 1 : Calculez le nombre de 1 avec deux bits : 0b11: 0b01 + 0b01 = 0b10 = 2, 0b10: 0b00 + 0b01 = 0b01 = 1. La recherche a révélé que : 2=0b11-0b1, 1=0b10-0b1, peut réduire le calcul une fois : i = i - ((i >>> 1) & 0x55555555)

• Étape 2 : Il n'existe actuellement aucune bonne méthode d'optimisation

• La troisième étape : calculez réellement le nombre de 1 dans chaque octet, jusqu'à 8 (0b1000), représentant 4 bits. Enfin, vous pouvez effectuer une opération ET au niveau du bit pour éliminer les bits, en réduisant une & opération. : i = (i + (i >>> 4)) & 0x0f0f0f0f

• Étape 4 et 5 : Pour la même raison que ci-dessus, vous pouvez éliminer la position à la fin. Cependant, comme int a au plus 32 (0b100000) 1, il n'est pas nécessaire d'effacer les bits dans ces deux étapes. La dernière étape consiste à effacer les bits inutiles : i & 0x3f

Insights : l'algorithme le plus simple, apparemment complexe, mais son principe de mise en œuvre est la simple logique de pensée de notre cerveau

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

Articles connexes :

Référence Java détaillée analyse du code source Code

Analyse du code source Java Explication détaillée de la méthode Arrays.asList

Vidéos associées :

Analyse complète de Annotations Java

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!