Java Language
Bit-Manipulation

Bemerkungen

Werte als Bitfragmente packen / entpacken

Es ist üblich, dass die Speicherleistung mehrere Werte in einen einzigen Grundwert komprimiert. Dies kann nützlich sein, um verschiedene Informationen in eine einzige Variable zu übergeben.

Zum Beispiel kann man 3 Bytes - z. B. Farbcode in RGB - in ein einzelnes int packen.

Werte packen

// Raw bytes as input
byte[] b = {(byte)0x65, (byte)0xFF, (byte)0x31};

// Packed in big endian: x == 0x65FF31
int x = (b[0] & 0xFF) << 16  // Red
      | (b[1] & 0xFF) <<  8  // Green
      | (b[2] & 0xFF) <<  0; // Blue

// Packed in little endian: y == 0x31FF65
int y = (b[0] & 0xFF) <<  0
      | (b[1] & 0xFF) <<  8
      | (b[2] & 0xFF) << 16;

Werte auspacken

// Raw int32 as input
int x = 0x31FF65;

// Unpacked in big endian: {0x65, 0xFF, 0x31}
byte[] c = {
    (byte)(x >> 16),
    (byte)(x >>  8),
    (byte)(x & 0xFF)
};

// Unpacked in little endian: {0x31, 0xFF, 0x65}
byte[] d = {
    (byte)(x & 0xFF),
    (byte)(x >>  8),
    (byte)(x >> 16)
};

Einzelne Bits prüfen, einstellen, löschen und umschalten. Verwenden Sie als Bitmaske

Angenommen, wir möchten das Bit n eines Ganzzahlprimitivs ändern ( i (Byte, Kurzzeichen, Zeichen, Ganzzahl oder Langzeichen)

(i & 1 << n) != 0 // checks bit 'n'
i |= 1 << n;      // sets bit 'n' to 1
i &= ~(1 << n);   // sets bit 'n' to 0
i ^= 1 << n;      // toggles the value of bit 'n'

Long / int / short / byte als Bitmaske verwenden:

public class BitMaskExample {
    private static final long FIRST_BIT = 1L << 0;
    private static final long SECOND_BIT = 1L << 1;
    private static final long THIRD_BIT = 1L << 2;
    private static final long FOURTH_BIT = 1L << 3;
    private static final long FIFTH_BIT = 1L << 4;
    private static final long BIT_55 = 1L << 54;

    public static void main(String[] args) {
        checkBitMask(FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55);
    }

    private static void checkBitMask(long bitmask) {
        System.out.println("FIRST_BIT: " + ((bitmask & FIRST_BIT) != 0));
        System.out.println("SECOND_BIT: " + ((bitmask & SECOND_BIT) != 0));
        System.out.println("THIRD_BIT: " + ((bitmask & THIRD_BIT) != 0));
        System.out.println("FOURTh_BIT: " + ((bitmask & FOURTH_BIT) != 0));
        System.out.println("FIFTH_BIT: " + ((bitmask & FIFTH_BIT) != 0));
        System.out.println("BIT_55: " + ((bitmask & BIT_55) != 0));
    }
}

Drucke

FIRST_BIT: true
SECOND_BIT: false
THIRD_BIT: true
FOURTh_BIT: false
FIFTH_BIT: true
BIT_55: true

welche der Maske entspricht, die wir als checkBitMask Parameter übergeben haben: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Die Kraft von 2 ausdrücken

Um die Potenz von 2 (2 ^ n) von ganzen Zahlen auszudrücken, kann eine Bitverschiebungsoperation verwendet werden, die es erlaubt, das n explizit anzugeben.

Die Syntax lautet im Wesentlichen:

int pow2 = 1<<n;

Beispiele:

int twoExp4 = 1<<4; //2^4
int twoExp5 = 1<<5; //2^5
int twoExp6 = 1<<6; //2^6
...
int twoExp31 = 1<<31; //2^31

Dies ist besonders nützlich, wenn Sie konstante Werte definieren, aus denen hervorgeht, dass anstelle von hexadezimalen oder dezimalen Werten eine Potenz von 2 verwendet wird.

int twoExp4 = 0x10; //hexadecimal
int twoExp5 = 0x20; //hexadecimal
int twoExp6 = 64; //decimal
...
int twoExp31 = -2147483648; //is that a power of 2?

Eine einfache Methode zur Berechnung der int Potenz von 2 wäre

int pow2(int exp){
    return 1<<exp;
}

Überprüfen, ob eine Zahl eine Potenz von 2 ist

Wenn eine ganze Zahl x eine Potenz von 2 ist, wird nur ein Bit gesetzt, während bei x-1 alle Bits danach gesetzt sind. Zum Beispiel: 4 ist 100 und 3 ist 011 als Binärzahl, was die oben genannte Bedingung erfüllt. Null ist keine Potenz von 2 und muss explizit geprüft werden.

boolean isPowerOfTwo(int x)
{
    return (x != 0) && ((x & (x - 1)) == 0);
}

Verwendung für Left und Right Shift

Nehmen wir an, wir haben drei Arten von Berechtigungen: READ , WRITE und EXECUTE . Jede Berechtigung kann zwischen 0 und 7 liegen. (Angenommen, ein 4-Bit-Zahlensystem)

RESOURCE = READ WRITE EXECUTE (12-Bit-Nummer)

RESOURCE = 0100 0110 0101 = 4 6 5 (12-Bit-Nummer)

Wie können wir die (12-Bit-Nummer) Berechtigungen erhalten, die oben gesetzt sind (12-Bit-Nummer)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Auf diese Weise können wir die EXECUTE- Berechtigungen der Ressource erhalten . Nun, was ist, wenn wir READ- Berechtigungen der Ressource erhalten möchten?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

Recht? Vermutlich nehmen Sie das an? Berechtigungen ergeben sich jedoch in 1024. Wir möchten nur READ-Berechtigungen für die Ressource erhalten. Keine Sorge, deshalb hatten wir Schichtbetreiber. Wenn wir sehen, liegen die READ-Berechtigungen 8 Bit hinter dem tatsächlichen Ergebnis. Wenn Sie also einen Schichtoperator anwenden, der READ-Berechtigungen ganz rechts neben dem Ergebnis bringt? Was ist, wenn wir tun:

0100 0000 0000 >> 8 => 0000 0000 0100 (Da es sich um eine positive Zahl handelt, die durch 0 ersetzt wird, verwenden Sie einfach den vorzeichenlosen Rechtsverschiebungsoperator.)

Wir haben jetzt tatsächlich die Leseberechtigung , die 4 ist.

Nun erhalten wir beispielsweise die Berechtigungen READ , WRITE , EXECUTE für eine Ressource . Was können wir tun, um Berechtigungen für diese Ressource zu erstellen ?

Nehmen wir zunächst das Beispiel für binäre Berechtigungen. (Immer noch ein 4-Bit-Zahlensystem vorausgesetzt)

READ = 0001

WRITE = 0100

EXECUTE = 0110

Wenn Sie denken, dass wir einfach tun werden:

READ | WRITE | EXECUTE , Sie haben etwas recht, aber nicht genau. Was passiert, wenn wir READ | durchführen SCHREIBEN | AUSFÜHREN

0001 | 0100 | 0110 => 0111

Berechtigungen werden jedoch (in unserem Beispiel) tatsächlich als 0001 0100 0110 dargestellt

Um dies zu tun, wissen wir, dass READ 8 Bits hinter, WRITE 4 Bits hinter und PERMISSIONS an letzter Stelle platziert werden. Das Zahlensystem, das für RESOURCE- Berechtigungen verwendet wird, ist tatsächlich 12 Bit (in unserem Beispiel). Sie kann in verschiedenen Systemen unterschiedlich sein (werden).

(LESEN SIE << 8) | (SCHREIBEN SIE << 4) | (AUSFÜHREN)

0000 0000 0001 << 8 (READ)

0001 0000 0000 (Linksverschiebung um 8 Bit)

0000 0000 0100 << 4 (SCHREIBEN)

0000 0100 0000 (Linksverschiebung um 4 Bit)

0000 0000 0001 (AUSFÜHRUNG)

Wenn wir nun die Ergebnisse der obigen Verschiebung hinzufügen, wird es ungefähr so ​​sein;

0001 0000 0000 (READ)

0000 0100 0000 (SCHREIBEN)

0000 0000 0001 (AUSFÜHRUNG)

0001 0100 0001 (Berechtigungen)

java.util.BitSet-Klasse

Seit 1.7 gibt es eine java.util.BitSet- Klasse, die eine einfache und benutzerfreundliche Bit-Speicher- und Bearbeitungsschnittstelle bietet:

final BitSet bitSet = new BitSet(8); // by default all bits are unset

IntStream.range(0, 8).filter(i -> i % 2 == 0).forEach(bitSet::set); // {0, 2, 4, 6}

bitSet.set(3); // {0, 2, 3, 4, 6}

bitSet.set(3, false); // {0, 2, 4, 6}

final boolean b = bitSet.get(3); // b = false

bitSet.flip(6); // {0, 2, 4}

bitSet.set(100); // {0, 2, 4, 100} - expands automatically

BitSet implementiert Clonable und Serializable . Unter der Haube werden alle Clonable im Feld long[] words gespeichert, das automatisch erweitert wird.

Es unterstützt auch ganze Satz logische Operationen and , or , xor , andNot :

bitSet.and(new BitSet(8));
bitSet.or(new BitSet(8));
bitSet.xor(new BitSet(8));
bitSet.andNot(new BitSet(8));

Signiert gegen unsignierte Schicht

In Java sind alle Zahlenprimitive signiert. Zum Beispiel kann ein int immer Werte aus [-2 ^ 31 - 1, 2 ^ 31] darstellen, wobei das erste Bit den Wert -1 für den negativen Wert und 0 für den positiven Wert signiert.

Grundlegende Schichtoperatoren >> und << sind signierte Operatoren. Sie werden das Vorzeichen des Wertes erhalten.

Es ist jedoch üblich, dass Programmierer Zahlen verwenden, um vorzeichenlose Werte zu speichern. Für ein int bedeutet dies, den Bereich auf [0, 2 ^ 32 - 1] zu verschieben, um einen doppelt so großen Wert wie mit einem vorzeichenbehafteten int zu haben.

Für diese Power-User bedeutet das Bit für Vorzeichen keine Bedeutung. Aus diesem Grund fügte Java >>> hinzu, einen Operator für die Linksverschiebung, der dieses Vorzeichen-Bit ignorierte.

                initial value:               4 (                                100)
     signed left-shift: 4 << 1               8 (                               1000)
    signed right-shift: 4 >> 1               2 (                                 10)
 unsigned right-shift: 4 >>> 1               2 (                                 10)
                initial value:              -4 (   11111111111111111111111111111100)
    signed left-shift: -4 << 1              -8 (   11111111111111111111111111111000)
   signed right-shift: -4 >> 1              -2 (   11111111111111111111111111111110)
unsigned right-shift: -4 >>> 1      2147483646 (    1111111111111111111111111111110)

Warum gibt es kein <<< ?

Dies ergibt sich aus der beabsichtigten Definition der Rechtsverschiebung. Da es die leeren Stellen auf der linken Seite ausfüllt, gibt es keine Entscheidung, was das Zeichenzeichen angeht. Infolgedessen sind keine zwei verschiedenen Bediener erforderlich.

Siehe diese Frage für eine detailliertere Antwort.