Paolo's Garden🪴

Bit Fragging

7 minuti

Il BitFragging è una tecnica di ottimizzazione della memoria che sfrutta l’uso efficiente dei bit per memorizzare più informazioni in una singola unità di memoria. Questo approccio è particolarmente utile quando si gestiscono grandi quantità di dati con campi che occupano pochi bit ciascuno, come in applicazioni di programmazione di giochi, compressione dati, e trasmissione di segnali. Invece di utilizzare un'intera unità di memoria (come un byte o un intero) per ogni singola informazione, il BitFragging suddivide queste unità in bit più piccoli e impacchetta più informazioni insieme. Questo consente di risparmiare memoria e, in alcuni casi, può anche migliorare le prestazioni.

Operazioni base

Il bit fragging è una tecnica utilizzata in programmazione per manipolare direttamente i singoli bit di un numero. Le operazioni comuni usate nel bit fragging includono:

  1. AND Bitwise (&)
  2. OR Bitwise (|)
  3. XOR Bitwise (^)
  4. NOT Bitwise (~)
  5. Shift Left (<<)
  6. Shift Right (>>)

AND Bitwise (&)

Questa operazione confronta ogni bit dei due operandi e restituisce 1 se entrambi i bit sono 1, altrimenti restituisce 0.

Esempio:

Operando A:  10101010
Operando B:  11001100
Risultato :  10001000
Byte76543210
A10101010
B11001100
Risultato10001000

OR Bitwise (|)

Questa operazione confronta ogni bit dei due operandi e restituisce 1 se almeno uno dei bit è 1, altrimenti restituisce 0.

Esempio:

Operando A:  10101010
Operando B:  11001100
Risultato :  11101110
Byte76543210
A10101010
B11001100
Risultato11101110

XOR Bitwise (^)

Questa operazione confronta ogni bit dei due operandi e restituisce 1 se i bit sono diversi, altrimenti restituisce 0.

Esempio:

Operando A:  10101010
Operando B:  11001100
Risultato :  01100110
Byte76543210
A10101010
B11001100
Risultato01100110

NOT Bitwise (~)

Questa operazione inverte ogni bit del singolo operando.

Esempio:

Operando A:  10101010
Risultato :  01010101
Byte76543210
A10101010
Risultato01010101

Shift Left (<<)

Questa operazione sposta tutti i bit a sinistra di un numero specificato di posizioni. I bit vuoti a destra vengono riempiti con 0.

Esempio (2 posizioni):

Operando A:  10101010
Risultato :  10101000
Byte76543210
A10101010
Risultato10101000

Shift Right (>>)

Questa operazione sposta tutti i bit a destra di un numero specificato di posizioni. I bit vuoti a sinistra vengono riempiti con 0.

Esempio (2 posizioni):

Operando A:  10101010
Risultato :  00101010
Byte76543210
A10101010
Risultato00101010

Queste operazioni sono fondamentali per la manipolazione di dati a basso livello, permettendo di gestire singoli bit e di ottimizzare l’uso delle risorse.

Operazioni comuni

Le operazioni bitwise sono spesso utilizzate per manipolare singoli bit all’interno di una variabile. Qui di seguito sono riportati alcuni utilizzi comuni di queste operazioni con esempi dettagliati.

Verificare il valore del bit i-esimo

Per verificare se il bit i-esimo è impostato a 1, si può utilizzare l’operazione AND con una maschera che ha solo l’i-esimo bit impostato a 1.

Esempio: Verificare se il 3° bit (indice 2) è 1

byte valore = 0b10101010; // 170 in decimale
int i = 2;
bool isBitSet = (valore & (1 << i)) != 0;
Valore:    10101010
Maschera:  00000100 (1 << 2)
Risultato: 00000000 (valore & maschera)
Byte76543210
Valore10101010
Maschera00000100
Risultato00000000

Settare il bit i-esimo a 1

Per settare il bit i-esimo a 1, si può utilizzare l’operazione OR con una maschera che ha solo l’i-esimo bit impostato a 1. Infatti il valore 0 con l’OR è l’operatore neutro: sia 0 che 1 in OR con 0 ritorna il valore originale, quindi 0 e 1.

Esempio: Settare il 3° bit (indice 2) a 1

byte valore = 0b10100010; // 162 in decimale
int i = 2;
valore |= (1 << i);
Valore:    10100010
Maschera:  00000100 (1 << 2)
Risultato: 10100110 (valore | maschera)
Byte76543210
Valore10100010
Maschera00000100
Risultato10100110

Resettare il bit i-esimo a 0

Per resettare il bit i-esimo a 0, si può utilizzare l’operazione AND con una maschera che ha solo l’i-esimo bit impostato a 0 e tutti gli altri a 1. Infatti il valore 1 con l’AND è l’operatore neutro: sia 0 che 1 in AND con 1 ritorna il valore originale, quindi 0 e 1.

Esempio: Resettare il 3° bit (indice 2) a 0

byte valore = 0b10101110; // 174 in decimale
int i = 2;
valore &= ~(1 << i);
Valore:    10101110
Maschera:  11111011 (~(1 << 2))
Risultato: 10101010 (valore & maschera)
Byte76543210
Valore10101110
Maschera11111011
Risultato10101010

Toggle del bit i-esimo

Per invertire il bit i-esimo, si può utilizzare l’operazione XOR con una maschera che ha solo l’i-esimo bit impostato a 1.

Esempio: Invertire il 3° bit (indice 2)

byte valore = 0b10101110; // 174 in decimale
int i = 2;
valore ^= (1 << i);
Valore:    10101110
Maschera:  00000100 (1 << 2)
Risultato: 10101010 (valore ^ maschera)
Byte76543210
Valore10101110
Maschera00000100
Risultato10101010

Esempio

Consideriamo un esempio in cui dobbiamo memorizzare le informazioni di stato per una serie di oggetti di gioco. Supponiamo che ogni oggetto abbia i seguenti stati:

  1. isAlive (1 bit) - Indica se l’oggetto è vivo o morto.
  2. hasPowerUp (1 bit) - Indica se l’oggetto ha un power-up.
  3. direction (2 bit) - Indica la direzione dell’oggetto (0=Nord, 1=Est, 2=Sud, 3=Ovest).

Usando un’intera unità di memoria per ciascun campo risulterebbe inefficiente. Possiamo invece utilizzare il BitFragging per impacchettare queste informazioni in un unico byte.

Implementazione in C#

using System;
 
public class GameObject
{
    private byte status;
 
    public bool IsAlive
    {
        get => (status & 0b00000001) != 0;
        set
        {
            if (value)
                status |= 0b00000001;
            else
                status &= 0b11111110;
        }
    }
 
    public bool HasPowerUp
    {
        get => (status & 0b00000010) != 0;
        set
        {
            if (value)
                status |= 0b00000010;
            else
                status &= 0b11111101;
        }
    }
 
    public byte Direction
    {
        get => (byte)((status & 0b00001100) >> 2);
        set
        {
        // Quando si imposta una nuova direzione, è necessario prima resettare i bit esistenti della direzione per evitare che i valori precedenti interferiscano con il nuovo valore. Senza resettare questi bit, la nuova direzione potrebbe mescolarsi con i bit esistenti, portando a valori errati.
            status &= 0b11110011; // Clear existing direction bits
            status |= (byte)((value & 0b00000011) << 2); // Set new direction bits
        }
    }
}
 
class Program
{
    static void Main()
    {
        GameObject obj = new GameObject();
 
        // Imposta i valori
        obj.IsAlive = true;
        obj.HasPowerUp = false;
        obj.Direction = 1;
 
        // Stampa i valori
        Console.WriteLine($"IsAlive: {obj.IsAlive}");
        Console.WriteLine($"HasPowerUp: {obj.HasPowerUp}");
        Console.WriteLine($"Direction: {obj.Direction}");
 
        // Cambia i valori
        obj.IsAlive = false;
        obj.HasPowerUp = true;
        obj.Direction = 3;
 
        // Stampa i nuovi valori
        Console.WriteLine($"IsAlive: {obj.IsAlive}");
        Console.WriteLine($"HasPowerUp: {obj.HasPowerUp}");
        Console.WriteLine($"Direction: {obj.Direction}");
    }
}

Spiegazione

  1. IsAlive: Utilizza il bit meno significativo (LSB) del byte status. L’operazione status & 0b00000001 verifica se il bit LSB è impostato. Per impostare o cancellare questo bit, usiamo rispettivamente status |= 0b00000001 e status &= 0b11111110.
  2. HasPowerUp: Utilizza il secondo bit meno significativo. L’operazione status & 0b00000010 verifica se questo bit è impostato. Per impostare o cancellare questo bit, usiamo rispettivamente status |= 0b00000010 e status &= 0b11111101.
  3. Direction: Utilizza i terzo e quarto bit del byte status. L’operazione (status & 0b00001100) >> 2 estrae questi bit e li sposta verso destra per ottenere il valore della direzione. Per impostare questi bit, cancelliamo prima i bit esistenti con status &= 0b11110011 e poi impostiamo i nuovi bit con status |= (byte)((value & 0b00000011) << 2).

Vantaggi del BitFragging

  • Efficienza di Memoria: Consente di memorizzare più informazioni in meno spazio, riducendo l’uso complessivo della memoria.
  • Prestazioni: Può migliorare le prestazioni del cache della CPU e ridurre il traffico di memoria.

Svantaggi del BitFragging

  • Complessità: Può aumentare la complessità del codice e rendere più difficile la manutenzione e la leggibilità.
  • Portabilità: Le operazioni bitwise possono comportarsi diversamente su architetture diverse, il che può portare a problemi di portabilità.

Vista grafico

Link entranti