Java Language
Bit Manipulation

Remarques

Emballage / Déballage des valeurs en tant que fragments de bits

Il est courant que les performances de la mémoire compressent plusieurs valeurs en une seule valeur primitive. Cela peut être utile pour transmettre diverses informations dans une seule variable.

Par exemple, on peut emballer 3 octets - tels que le code couleur en RVB - dans un seul int.

Emballer les valeurs

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

Déballer les valeurs

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

Vérification, configuration, effacement et basculement des bits individuels. Utiliser long comme masque de bits

En supposant que nous voulions modifier le bit n d'une primitive entière, i (octet, court, char, int ou 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'

Utiliser long / int / short / byte comme masque de bits:

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

Des tirages

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

qui correspond à ce masque que nous avons passé en tant checkBitMask paramètre FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 : FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Exprimer le pouvoir de 2

Pour exprimer la puissance de 2 (2 ^ n) d'entiers, on peut utiliser une opération bitshift qui permet de spécifier explicitement le n .

La syntaxe est fondamentalement:

int pow2 = 1<<n;

Exemples:

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

Ceci est particulièrement utile lors de la définition de valeurs constantes qui doivent indiquer qu'une puissance de 2 est utilisée, au lieu d'utiliser des valeurs hexadécimales ou décimales.

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

Une méthode simple pour calculer la puissance int de 2 serait

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

Vérifier si un nombre est une puissance de 2

Si un entier x est une puissance de 2, un seul bit est défini, alors que x-1 a tous les bits définis après cela. Par exemple: 4 est 100 et 3 est 011 comme nombre binaire, ce qui satisfait à la condition susmentionnée. Zéro n'est pas une puissance de 2 et doit être vérifié explicitement.

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

Utilisation pour gauche et droite

Supposons que nous ayons trois types d'autorisations, READ , WRITE et EXECUTE . Chaque autorisation peut varier de 0 à 7. (Supposons un système à 4 bits)

RESOURCE = READ WRITE EXECUTE (numéro de 12 bits)

RESSOURCE = 0100 0110 0101 = 4 6 5 (nombre de 12 bits)

Comment pouvons-nous obtenir les autorisations (nombre 12 bits) définies ci-dessus (nombre 12 bits)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Donc, voici comment nous pouvons obtenir les autorisations EXECUTE de la ressource . Maintenant, que faire si nous voulons obtenir les autorisations READ de la ressource ?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

Droite? Vous supposez probablement cela? Mais, les autorisations sont obtenues dans 1024. Nous voulons obtenir uniquement des autorisations READ pour la ressource. Ne vous inquiétez pas, c'est pourquoi nous avons eu les opérateurs de quarts. Si nous voyons, les autorisations READ sont 8 bits derrière le résultat réel, donc si vous appliquez un opérateur de décalage, ce qui apportera des autorisations READ à droite du résultat? Et si on fait:

0100 0000 0000 >> 8 => 0000 0000 0100 (Parce que c'est un nombre positif, donc remplacé par 0, si vous ne vous souciez pas du signe, utilisez simplement l'opérateur de décalage non signé)

Nous avons maintenant les permissions READ qui sont 4.

Maintenant, par exemple, on nous donne des autorisations READ , WRITE , EXECUTE pour une ressource , que pouvons-nous faire pour obtenir des autorisations pour cette ressource ?

Prenons d'abord l'exemple des autorisations binaires. (En supposant toujours un système à 4 bits)

READ = 0001

WRITE = 0100

EXECUTE = 0110

Si vous pensez que nous allons simplement faire:

READ | WRITE | EXECUTE , vous avez un peu raison mais pas exactement. Voyez, que se passera-t-il si nous effectuons READ | ECRIRE | EXÉCUTER

0001 | 0100 | 0110 => 0111

Mais les autorisations sont effectivement représentées (dans notre exemple) sous la forme 0001 0100 0110

Donc, pour ce faire, nous savons que READ est placé 8 bits derrière, WRITE est placé 4 bits derrière et PERMISSIONS est placé à la dernière place. Le système de numérotation utilisé pour les autorisations RESOURCE est en fait 12 bits (dans notre exemple). Il peut (sera) différent dans différents systèmes.

(LIRE << 8) | (ECRIRE << 4) | (EXÉCUTER)

0000 0000 0001 << 8 (READ)

0001 0000 0000 (décalage gauche de 8 bits)

0000 0000 0100 << 4 (WRITE)

0000 0100 0000 (décalage à gauche de 4 bits)

0000 0000 0001 (EXECUTE)

Maintenant, si nous ajoutons les résultats du décalage ci-dessus, ce sera quelque chose comme:

0001 0000 0000 (READ)

0000 0100 0000 (WRITE)

0000 0000 0001 (EXECUTE)

0001 0100 0001 (PERMISSIONS)

Classe java.util.BitSet

Depuis la 1.7, il y a une classe java.util.BitSet qui fournit une interface simple et conviviale de stockage et de manipulation des bits:

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 implémente Clonable et Serializable , et sous le capot, toutes les valeurs de bits sont stockées dans long[] words champ long[] words , qui se développe automatiquement.

Il prend également en charge les opérations logiques mis ensemble- and , or , xor , andNot :

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

Décalage signé ou non signé

En Java, toutes les primitives numériques sont signées. Par exemple, un int représente toujours des valeurs de [-2 ^ 31 - 1, 2 ^ 31], en gardant le premier bit pour signer la valeur - 1 pour la valeur négative, 0 pour le positif.

Les opérateurs de décalage de base >> et << sont des opérateurs signés. Ils conserveront le signe de la valeur.

Mais il est courant que les programmeurs utilisent des nombres pour stocker des valeurs non signées . Pour un int, cela signifie qu'il faut déplacer la plage sur [0, 2 ^ 32 - 1], pour avoir deux fois plus de valeur que pour un int signé.

Pour les utilisateurs de puissance, le bit pour le signe n'a aucune signification. C'est pourquoi Java a ajouté >>> , un opérateur de gauche, sans tenir compte de ce bit de signe.

                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)

Pourquoi n'y a-t-il pas <<< ?

Cela vient de la définition prévue du passage à droite. Comme il remplit les endroits vides sur la gauche, il n'y a aucune décision à prendre concernant le bit de signe. Par conséquent, 2 opérateurs différents ne sont pas nécessaires.

Voir cette question pour une réponse plus détaillée.