Java Language
Manipolazione bit

Osservazioni

Imballaggio / spacchettamento dei valori come frammenti di bit

È normale che le prestazioni della memoria comprimano più valori in un singolo valore primitivo. Questo può essere utile per passare varie informazioni in una singola variabile.

Ad esempio, uno può imballare 3 byte - come il codice colore in RGB - in un singolo int.

Imballaggio dei valori

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

Disimballaggio dei valori

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

Controllo, impostazione, cancellazione e commutazione di singoli bit. Utilizzo lungo come bit mask

Supponendo di voler modificare il bit n di un intero primitivo, i (byte, short, char, int o long):

(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'

Usando long / int / short / byte come bit mask:

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

stampe

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

che corrisponde a quello maschera abbiamo passato come checkBitMask parametro: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Esprimendo la potenza di 2

Per esprimere la potenza di 2 (2 ^ n) di numeri interi, si può usare un'operazione bitshift che consente di specificare esplicitamente il n .

La sintassi è fondamentalmente:

int pow2 = 1<<n;

Esempi:

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

Ciò è particolarmente utile quando si definiscono valori costanti che dovrebbero renderlo evidente, che viene utilizzata una potenza di 2, invece di utilizzare valori esadecimali o decimali.

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

Un semplice metodo per calcolare la potenza int di 2 sarebbe

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

Controllare se un numero è una potenza di 2

Se un numero intero x è una potenza di 2, viene impostato solo un bit, mentre dopo x-1 tutti i bit vengono impostati. Ad esempio: 4 è 100 e 3 è 011 come numero binario, che soddisfa la condizione summenzionata. Zero non è una potenza di 2 e deve essere controllato esplicitamente.

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

Utilizzo per spostamento a sinistra e a destra

Supponiamo di avere tre tipi di permessi, READ , WRITE ed EXECUTE . Ogni permesso può variare da 0 a 7. (Supponiamo che il sistema di numeri a 4 bit)

RESOURCE = READ WRITE EXECUTE (numero di 12 bit)

RESOURCE = 0100 0110 0101 = 4 6 5 (numero di 12 bit)

Come possiamo ottenere le autorizzazioni (12 bit), impostate sopra (numero di 12 bit)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Quindi, questo è il modo in cui possiamo ottenere le autorizzazioni EXECUTE di RESOURCE . Ora, cosa succede se vogliamo ottenere i permessi di LETTURA della RISORSA ?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

Destra? Probabilmente stai assumendo questo? Ma, le autorizzazioni sono risultate in 1024. Vogliamo ottenere solo i permessi di LETTURA per la risorsa. Non preoccuparti, è per questo che abbiamo avuto gli operatori di turno. Se vediamo, i permessi di lettura sono 8 bit dietro il risultato effettivo, quindi se si applica un operatore di shift, che porterà i permessi di lettura all'estrema destra del risultato? Cosa succede se facciamo:

0100 0000 0000 >> 8 => 0000 0000 0100 (Perché è un numero positivo sostituito quindi da 0, se non ti interessa il segno, usa l'operatore di spostamento a destra senza segno)

Ora abbiamo i permessi di LETTURA che sono 4.

Ora, per esempio, ci sono le autorizzazioni READ , WRITE , EXECUTE per una RISORSA , cosa possiamo fare per ottenere i permessi per questa RISORSA ?

Prendiamo innanzitutto l'esempio delle autorizzazioni binarie. (Sempre ipotizzando un sistema a 4 bit)

LEGGI = 0001

WRITE = 0100

ESEGUI = 0110

Se stai pensando che faremo semplicemente:

READ | WRITE | EXECUTE , hai ragione, ma non esattamente. Vedi, cosa succederà se eseguiremo READ | SCRIVI | ESEGUIRE

0001 | 0100 | 0110 => 0111

Ma le autorizzazioni vengono effettivamente rappresentate (nel nostro esempio) come 0001 0100 0110

Quindi, per fare ciò, sappiamo che READ è posizionato 8 bit dietro, WRITE è posizionato 4 bit dietro e PERMISSIONS è posizionato all'ultimo. Il sistema numerico utilizzato per le autorizzazioni RESOURCE è in realtà 12 bit (nel nostro esempio). Può (sarà) diverso nei diversi sistemi.

(LEGGI << 8) | (SCRIVIA << 4) | (ESEGUIRE)

0000 0000 0001 << 8 (LEGGI)

0001 0000 0000 (spostamento a sinistra di 8 bit)

0000 0000 0100 << 4 (WRITE)

0000 0100 0000 (spostamento a sinistra di 4 bit)

0000 0000 0001 (ESEGUI)

Ora se aggiungiamo i risultati di uno spostamento sopra, sarà qualcosa di simile;

0001 0000 0000 (LEGGI)

0000 0100 0000 (WRITE)

0000 0000 0001 (ESEGUI)

0001 0100 0001 (AUTORIZZAZIONI)

classe java.util.BitSet

Dalla versione 1.7 esiste una classe java.util.BitSet che fornisce un'interfaccia di manipolazione e archiviazione di bit semplice e intuitiva:

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 implementa Clonable e Serializable , e sotto la cappa tutti i valori di bit sono memorizzati nel campo long[] words , che si espande automaticamente.

Supporta anche operazioni logiche con set completo and , or , xor e andNot :

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

Mai firmato e non firmato

In Java, tutti i numeri primitivi sono firmati. Ad esempio, un int rappresenta sempre i valori da [-2 ^ 31 - 1, 2 ^ 31], mantenendo il primo bit per firmare il valore - 1 per il valore negativo, 0 per il positivo.

Gli operatori di spostamento di base >> e << sono operatori firmati. Conserveranno il segno del valore.

Ma è comune per i programmatori usare i numeri per memorizzare valori non firmati . Per un int, significa spostare l'intervallo su [0, 2 ^ 32 - 1], per avere il doppio del valore di un int firmato.

Per quegli utenti esperti, il bit per il segno non ha significato. Ecco perché Java ha aggiunto >>> , un operatore di spostamento a sinistra, ignorando quel bit di segno.

                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)

Perché non c'è <<< ?

Questo deriva dalla definizione del giusto turno. Mentre riempie i posti svuotati a sinistra, non ci sono decisioni da prendere riguardo al bit del segno. Di conseguenza, non sono necessari 2 operatori diversi.

Vedi questa domanda per una risposta più dettagliata.