L'histoire originale est Hacker's Fun (titre original: Hacker's Delight).
01011000
↓
f(00001000)
f(00010000)
f(01000000)
Lorsque vous souhaitez numériser à partir de la droite et ne traiter que s'il est 1. Vous n'avez pas besoin de boucler pour la longueur du bit, vous pouvez simplement boucler un nombre.
for (int x = 0b01011000; x > 0; x &= x - 1) {
f(x & -x);
}
En répétant x & -x et x & = x -1 de cette manière, vous ne pouvez parcourir que la partie de 1.
x & -x
01011000 = x
10100111 = not(x)
10101000 = not(x)+1 = -x
En d'autres termes
00001000 = x & -x
Ensuite, ** seul le 1 le plus à droite reste. ** **
x & x-1
01011000 = x
01010111 = x-1
En d'autres termes
01010000 = x & x-1
Ensuite, ** le 1 à l'extrémité droite disparaît. ** **
00101110 10100000 11100101 11001011
↓
16
Lorsque vous voulez compter le nombre de 1 Il peut être calculé par log (nombre de bits) d'opérations sur les bits sans bouclage par le nombre de bits.
x = 0b00101110101000001110010111001011;
x = (x & 0x55555555) + ((x >>> 1) & 0x55555555)
x = (x & 0x33333333) + ((x >>> 2) & 0x33333333)
x = (x & 0x0F0F0F0F) + ((x >>> 4) & 0x0F0F0F0F)
x = (x & 0x00FF00FF) + ((x >>> 8) & 0x00FF00FF)
x = (x & 0x0000FFFF) + ((x >>> 16) & 0x0000FFFF)
Ce que nous faisons, c'est une gouvernance divisionnaire qui écrit la somme partielle dans x lui-même.
Divisez les données en 2 bits, trouvez le nombre de 1 pour chaque 2 bits et écrasez x.
00 10 11 10 10 10 00 00 11 10 01 01 11 00 10 11 = x
↓
_0 _1 _2 _1 _1 _1 _0 _0 _2 _1 _1 _1 _2 _0 _1 _2 (notation décimale)
↓
00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10 = Nouveau x
00 10 11 10 10 10 00 00 11 10 01 01 11 00 10 11 = x
_0 _0 _1 _0 _0 _0 _0 _0 _1 _0 _1 _1 _1 _0 _0 _1 = x & 0x55555555
_0 _1 _1 _1 _1 _1 _0 _0 _1 _1 _0 _0 _1 _0 _1 _1 = ((x >>> 1) & 0x55555555)
Ajouter les chiffres supérieur et inférieur en même temps lorsqu'ils sont divisés par 2 bits
00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10 = (x & 0x55555555) + ((x >>> 1) & 0x55555555)
Ce que nous faisons est une opération vectorielle à 2 bits.
Divisez les données en 4 bits, trouvez le nombre de 1 pour chaque 4 bits et écrasez x.
0001 1001 0101 0000 1001 0101 1000 0110 = x
↓
_0_1 _2_1 _1_1 _0_0 _2_1 _1_1 _2_0 _1_2 (notation décimale)
↓
___ 1 ___ 3 ___ 2 ___ 0 ___ 3 ___ 2 ___ 2 ___ 3 (notation décimale)
↓
0001 0011 0010 0000 0011 0010 0010 0011 = nouveau x
0001 1001 0101 0000 1001 0101 1000 0110 = x
__01 __01 __01 __00 __01 __01 __00 __10 = x & 0x33333333
__00 __10 __01 __00 __10 __01 __10 __01 = (x >>> 1) & 0x33333333
Ajouter les 2 bits supérieurs et les 2 bits inférieurs en même temps lorsqu'ils sont divisés par 4 bits
0001 0011 0010 0000 0011 0010 0010 0011 = (x & 0x33333333) + ((x >>> 2) & 0x33333333)
Ce que nous faisons est une opération vectorielle à 4 bits.
Divisez les données en 8 bits, trouvez le nombre de 1 pour chaque 8 bits et écrasez x.
00010011 00100000 00110010 00100011 = x
↓
___ 1 ___ 3 ___ 2 ___ 0 ___ 3 ___ 2 ___ 2 ___ 3 (notation décimale)
↓
_______ 4 _______2 _______ 5 _______ 5 (notation décimale)
↓
00000100 00000010 00000101 00000101 = nouveau x
Divisez les données en 16 bits, trouvez le nombre de 1 pour chaque 16 bits et écrasez x.
0000010000000010 0000010100000101 = x
↓
_______ 4 _______2 _______ 5 _______ 5 (notation décimale)
↓
_______________6 ______________ 10 (notation décimale)
↓
0000000000000110 0000000000001010 = nouveau x
Trouvez le nombre de 1 dans toutes les données et écrasez x.
0000000000000110 0000000000001010 = nouveau x
↓
_______________6 ______________ 10 (notation décimale)
↓
_______________________________ 16 (notation décimale)
↓
0000000000000000 0000000000010000 = nouveau x
↓
16
Il peut être implémenté dans une bibliothèque standard. Je ne connais que des exemples Java and Go, Java : Integer.bitCount()、Long.bitCount() Go: paquet de bits OnesCountXX () (Plus optimisé que le code ci-dessus).
De plus, comme il a été implémenté en tant qu'instruction d'extension de processeur (SSE4.2 POPCNT pour Intel) il y a environ 10 ans, En premier lieu, si vous voulez vraiment accélérer, vous devez utiliser un langage qui peut appeler POPCNT directement.
Concernant Java, JIT semble remplacer bitCount () par POPCNT, Et Go?
wikipedia: SSE4, poids bourdonnant https://en.wikipedia.org/wiki/SSE4 https://en.wikipedia.org/wiki/Hamming_weight
Classe longue de openjdk8 (code source) https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/lang/Long.java
Paquet Go bits (code source) https://golang.org/src/math/bits/bits.go?s=3946:3972#L103
00101110 10100000 11100101 11001011
↓
11010011 10100111 00000101 01110100
Vous pouvez également utiliser la gouvernance partagée lorsque vous souhaitez inverser les bits.
x = 0b00101110101000001110010111001011;
x = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16;
x = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >>> 8;
x = (x & 0x0F0F0F0F) << 4 | (x & 0xF0F0F0F0) >>> 4;
x = (x & 0x33333333) << 2 | (x & 0xCCCCCCCC) >>> 2;
x = (x & 0x55555555) << 1 | (x & 0xAAAAAAAA) >>> 1;
Divisez les données en 16 bits et remplacez-les.
0010111010100000 1110010111001011 = x
↓
1110010111001011 0010111010100000 = nouveau x
0010111010100000 1110010111001011 = x
1110010111001011 ________________ = (x & 0x0000FFFF) << 16
________________ 0010111010100000 = (x & 0xFFFF0000) >>> 16
1110010111001011 0010111010100000 = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16
Divisez les données en 8 bits et échangez-les les unes à côté des autres.
11100101 11001011 00101110 10100000 = x
↓
11001011 11100101 10100000 00101110 = nouveau x
11100101 11001011 00101110 10100000 = x
11001011 ________ 10100000 ________ = (x & 0x00FF00FF) << 8
________ 11100101 ________ 00101110 = (x & 0xFF00FF00) >>> 8
11001011 11100101 10100000 00101110 = (x & 0x00FF00FF) << 8 | (x & 0xFF00FF00) >>> 8
Divisez les données en 4 bits et échangez-les les unes à côté des autres.
1100 1011 1110 0101 1010 0000 0010 1110 = x
↓
1011 1100 0101 1110 0000 1010 1110 0010 = nouveau x
Divisez les données en 2 bits et échangez-les les unes à côté des autres.
10 11 11 00 01 01 11 10 00 00 10 10 11 10 00 10 = x
↓
11 10 00 11 01 01 10 11 00 00 10 10 10 11 10 00 = Nouveau x
Divisez les données en bits et échangez-les les uns à côté des autres.
1 1 1 0 0 0 1 1 0 1 0 1 1 0 1 1 0 0 0 0 1 0 1 0 1 0 1 1 1 0 0 0 = x
↓
1 1 0 1 0 0 1 1 1 0 1 0 0 1 1 1 0 0 0 0 0 1 0 1 0 1 1 1 0 1 0 0 = nouveau x
11010011101001110000010101110100 = Original x
00101110101000001110010111001011 = Nouveau x
Et c'est dans le bon ordre inverse.
Cela peut également être implémenté dans la bibliothèque standard. Java -> Integer.reverseBytes()、Long.reverseBytes() Paquet Go-> bits ReverseXX ()