Java Language
Manipulación de bits

Observaciones

Empaquetar / desempaquetar valores como fragmentos de bits

Es común que el rendimiento de la memoria comprima múltiples valores en un solo valor primitivo. Esto puede ser útil para pasar información diversa a una sola variable.

Por ejemplo, uno puede empaquetar 3 bytes, como el código de color en RGB , en un solo int.

Empaquetando los valores

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

Desempaquetando los valores

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

Comprobación, configuración, borrado y conmutación de bits individuales. Utilizando mascarilla larga como bit

Suponiendo que deseamos modificar el bit n de una primitiva entera, 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 como una máscara 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));
    }
}

Huellas dactilares

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

que coincide con la máscara que nos pasa como checkBitMask parámetro: FIRST_BIT | THIRD_BIT | FIFTH_BIT | BIT_55 .

Expresando el poder de 2

Para expresar la potencia de 2 (2 ^ n) de enteros, se puede usar una operación de cambio de bits que permita especificar explícitamente la n .

La sintaxis es básicamente:

int pow2 = 1<<n;

Ejemplos:

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

Esto es especialmente útil cuando se definen valores constantes que deberían hacer evidente que se usa una potencia de 2, en lugar de usar valores hexadecimales o decimales.

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

Un método simple para calcular la potencia int de 2 sería

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

Comprobando si un número es una potencia de 2

Si un entero x es una potencia de 2, solo se establece un bit, mientras que x-1 tiene todos los bits establecidos después de eso. Por ejemplo: 4 es 100 y 3 es 011 como número binario, que satisface la condición mencionada anteriormente. El cero no es una potencia de 2 y debe comprobarse explícitamente.

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

Uso para turno izquierdo y derecho

Supongamos que tenemos tres tipos de permisos, LEER , ESCRIBIR y EJECUTAR . Cada permiso puede variar de 0 a 7. (Supongamos un sistema de números de 4 bits)

RECURSO = LEER ESCRIBIR EJECUTAR (número de 12 bits)

RECURSO = 0100 0110 0101 = 4 6 5 (número de 12 bits)

¿Cómo podemos obtener los permisos (número de 12 bits) establecidos anteriormente (número de 12 bits)?

0100 0110 0101

0000 0000 0111 (&)

0000 0000 0101 = 5

Entonces, así es como podemos obtener los permisos de EJECUTAR del RECURSO . Ahora, ¿qué pasa si queremos obtener los permisos de LEER del RECURSO ?

0100 0110 0101

0111 0000 0000 (&)

0100 0000 0000 = 1024

¿Derecha? Probablemente estás asumiendo esto? Sin embargo, los permisos se obtienen en 1024. Queremos obtener solo los permisos de LEER para el recurso. No te preocupes, por eso tuvimos los operadores de turno. Si vemos, los permisos de LECTURA están 8 bits detrás del resultado real, por lo tanto, si se aplica algún operador de cambio, ¿cuál llevará los permisos de LECTURA a la derecha del resultado? ¿Qué pasa si hacemos:

0100 0000 0000 >> 8 => 0000 0000 0100 (debido a que es un número positivo reemplazado por 0, si no te importa la señal, solo usa el operador de turno derecho sin signo)

Ahora realmente tenemos los permisos de lectura que es 4.

Ahora, por ejemplo, tenemos permisos de LEER , ESCRIBIR , EJECUTAR para un RECURSO , ¿qué podemos hacer para hacer los permisos para este RECURSO ?

Tomemos primero el ejemplo de los permisos binarios. (Todavía asumiendo sistema de número de 4 bits)

LEER = 0001

ESCRIBIR = 0100

EJECUTAR = 0110

Si estás pensando que simplemente haremos:

READ | WRITE | EXECUTE , tienes algo de razón, pero no exactamente. Mira, ¿qué pasará si vamos a realizar LEER | ESCRIBIR | EJECUTAR

0001 | 0100 | 0110 => 0111

Pero los permisos se representan en realidad (en nuestro ejemplo) como 0001 0100 0110

Entonces, para hacer esto, sabemos que LEER se coloca 8 bits atrás, WRITE se coloca 4 bits atrás y PERMISOS se coloca en el último. El sistema numérico que se usa para los permisos de RECURSOS es en realidad 12 bits (en nuestro ejemplo). Puede (será) diferente en diferentes sistemas.

(LEER << 8) | (ESCRIBIR << 4) | (EJECUTAR)

0000 0000 0001 << 8 (LEER)

0001 0000 0000 (desplazamiento a la izquierda por 8 bits)

0000 0000 0100 << 4 (ESCRIBIR)

0000 0100 0000 (desplazamiento a la izquierda por 4 bits)

0000 0000 0001 (EJECUTAR)

Ahora, si agregamos los resultados del cambio anterior, será algo así como;

0001 0000 0000 (LEER)

0000 0100 0000 (ESCRIBIR)

0000 0000 0001 (EJECUTAR)

0001 0100 0001 (PERMISOS)

clase java.util.BitSet

Desde la versión 1.7 hay una clase java.util.BitSet que proporciona una interfaz de manipulación y almacenamiento de bits simple y fácil de usar:

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 y Serializable , y bajo el capó, todos los valores de bit se almacenan en el campo de long[] words , que se expande automáticamente.

También admite operaciones lógicas de conjunto completo and , or , xor , andNot :

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

Cambio firmado / no firmado

En Java, todos los primitivos numéricos están firmados. Por ejemplo, un int siempre representa valores de [-2 ^ 31 - 1, 2 ^ 31], manteniendo el primer bit para firmar el valor: 1 para el valor negativo, 0 para el positivo.

Los operadores de turno básicos >> y << son operadores firmados. Conservarán el signo del valor.

Pero es común que los programadores utilicen números para almacenar valores sin firmar . Para un int, significa cambiar el rango a [0, 2 ^ 32 - 1], para tener el doble de valor que con un int firmado.

Para aquellos usuarios avanzados, el bit para firmar no tiene significado. Es por eso que Java agregó >>> , un operador de cambio a la izquierda, sin tener en cuenta ese bit de signo.

                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)

¿Por qué no hay <<< ?

Esto viene de la definición pretendida de cambio a la derecha. Como llena los lugares vacíos de la izquierda, no hay ninguna decisión que tomar con respecto al bit de señal. Como consecuencia, no hay necesidad de 2 operadores diferentes.

Vea esta pregunta para una respuesta más detallada.