Die ursprüngliche Geschichte ist Hacker's Fun (Originaltitel: Hacker's Delight).
01011000
↓
f(00001000)
f(00010000)
f(01000000)
Wenn Sie von rechts scannen und nur dann verarbeiten möchten, wenn es 1 ist. Sie müssen nicht für die Länge des Bits schleifen, sondern können nur eine Zahl schleifen.
for (int x = 0b01011000; x > 0; x &= x - 1) {
f(x & -x);
}
Wenn Sie auf diese Weise "x & -x" und "x & = x -1" wiederholen, können Sie nur den Teil von 1 gehen.
x & -x
01011000 = x
10100111 = not(x)
10101000 = not(x)+1 = -x
Mit anderen Worten
00001000 = x & -x
Dann bleibt ** nur die am weitesten rechts stehende 1 übrig. ** ** **
x & x-1
01011000 = x
01010111 = x-1
Mit anderen Worten
01010000 = x & x-1
Dann verschwindet ** 1 am rechten Ende. ** ** **
00101110 10100000 11100101 11001011
↓
16
Wenn Sie die Zahl 1 zählen möchten Sie kann durch Protokoll (Anzahl der Bits) von Bitoperationen berechnet werden, ohne die Anzahl der Bits zu durchlaufen.
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)
Was wir tun, ist Divisions-Governance, die die Teilsumme in x selbst schreibt.
Teilen Sie die Daten in 2 Bits, ermitteln Sie die Anzahl der Einsen für jeweils 2 Bits und überschreiben Sie 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 (Dezimalschreibweise)
↓
00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10 = Neu 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)
Fügen Sie die oberen und unteren Ziffern gleichzeitig hinzu, wenn Sie durch 2 Bits geteilt werden
00 01 10 01 01 01 00 00 10 01 01 01 10 00 01 10 = (x & 0x55555555) + ((x >>> 1) & 0x55555555)
Was wir tun, ist eine 2-Bit-Vektoroperation.
Teilen Sie die Daten in 4 Bits, ermitteln Sie die Anzahl der Einsen für jeweils 4 Bits und überschreiben Sie 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 (Dezimalschreibweise)
↓
___ 1 ___ 3 ___ 2 ___ 0 ___ 3 ___ 2 ___ 2 ___ 3 (Dezimalschreibweise)
↓
0001 0011 0010 0000 0011 0010 0010 0011 = neu 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
Addiere die oberen 2 Bits und die unteren 2 Bits gleichzeitig, wenn sie durch 4 Bits geteilt werden
0001 0011 0010 0000 0011 0010 0010 0011 = (x & 0x33333333) + ((x >>> 2) & 0x33333333)
Was wir tun, ist eine 4-Bit-Vektoroperation.
Teilen Sie die Daten in 8 Bits, ermitteln Sie die Anzahl der Einsen für jeweils 8 Bits und überschreiben Sie x.
00010011 00100000 00110010 00100011 = x
↓
___1___3 ___2___0 ___3___2 ___ 2 ___ 3 (Dezimalschreibweise)
↓
_______ 4 _______2 _______ 5 _______ 5 (Dezimalschreibweise)
↓
00000100 00000010 00000101 00000101 = neues x
Teilen Sie die Daten in 16 Bits, ermitteln Sie die Anzahl der Einsen für jeweils 16 Bits und überschreiben Sie x.
0000010000000010 0000010100000101 = x
↓
_______ 4 _______2 _______ 5 _______ 5 (Dezimalschreibweise)
↓
_______________6 ______________ 10 (Dezimalschreibweise)
↓
0000000000000110 0000000000001010 = neues x
Finden Sie die Anzahl der Einsen in den gesamten Daten und überschreiben Sie x.
0000000000000110 0000000000001010 = neues x
↓
_______________6 ______________ 10 (Dezimalschreibweise)
↓
_______________________________ 16 (Dezimalschreibweise)
↓
0000000000000000 0000000000010000 = neu x
↓
16
Es kann in einer Standardbibliothek implementiert werden. Ich kenne nur Java- und Go-Beispiele. Java : Integer.bitCount()、Long.bitCount() Go: Bits-Paket OnesCountXX () (Optimierter als der obige Code).
Da es vor etwa 10 Jahren als CPU-Erweiterungsanweisung (SSE4.2 POPCNT für Intel) implementiert wurde, Wenn Sie wirklich beschleunigen möchten, sollten Sie zunächst eine Sprache verwenden, die POPCNT direkt aufrufen kann.
In Bezug auf Java scheint JIT bitCount () durch POPCNT zu ersetzen. Was ist mit Go?
Wikipedia: SSE4, summendes Gewicht https://en.wikipedia.org/wiki/SSE4 https://en.wikipedia.org/wiki/Hamming_weight
Lange Klasse von openjdk8 (Quellcode) https://hg.openjdk.java.net/jdk8/jdk8/jdk/file/687fd7c7986d/src/share/classes/java/lang/Long.java
Go-Bits-Paket (Quellcode) https://golang.org/src/math/bits/bits.go?s=3946:3972#L103
00101110 10100000 11100101 11001011
↓
11010011 10100111 00000101 01110100
Sie können Split Governance auch verwenden, wenn Sie die Bits umkehren möchten.
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;
Teilen Sie die Daten in 16 Bit und ersetzen Sie sie.
0010111010100000 1110010111001011 = x
↓
1110010111001011 0010111010100000 = neues x
0010111010100000 1110010111001011 = x
1110010111001011 ________________ = (x & 0x0000FFFF) << 16
________________ 0010111010100000 = (x & 0xFFFF0000) >>> 16
1110010111001011 0010111010100000 = (x & 0x0000FFFF) << 16 | (x & 0xFFFF0000) >>> 16
Teilen Sie die Daten in 8 Bits und tauschen Sie sie nebeneinander aus.
11100101 11001011 00101110 10100000 = x
↓
11001011 11100101 10100000 00101110 = neues 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
Teilen Sie die Daten in 4 Bits und tauschen Sie sie nebeneinander aus.
1100 1011 1110 0101 1010 0000 0010 1110 = x
↓
1011 1100 0101 1110 0000 1010 1110 0010 = neu x
Teilen Sie die Daten in 2 Bits und tauschen Sie sie nebeneinander aus.
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 = Neu x
Teilen Sie die Daten in Bits und tauschen Sie sie nebeneinander aus.
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 = neu x
11010011101001110000010101110100 = Original x
00101110101000001110010111001011 = Neu x
Und es ist in der richtigen umgekehrten Reihenfolge.
Dies kann auch in der Standardbibliothek implementiert werden. Java -> Integer.reverseBytes()、Long.reverseBytes() Go-> Bits-Paket ReverseXX ()