java - paquetes - r repository

Bool de un byte. ¿Por qué?

Question

En C ++, ¿por qué un bool requiere un byte para almacenar verdadero o falso donde solo un bit es suficiente para eso, como 0 para falso y 1 para verdadero? (¿Por qué Java también requiere un byte?)

En segundo lugar, ¿cuánto más seguro es usar lo siguiente?

struct Bool {
    bool trueOrFalse : 1;
};

En tercer lugar, incluso si es seguro, ¿la técnica de campo anterior realmente ayudará? Desde que escuché que ahorramos espacio allí, pero el código generado por el compilador para acceder a ellos es más grande y más lento que el código generado para acceder a los primitivos.

Answer 1

¿Por qué un bool necesita un byte para almacenar verdadero o falso donde solo un bit es suficiente?

Debido a que cada objeto en C ++ debe ser direccionable individualmente ^* (es decir, debe tener un puntero). No puede direccionar un bit individual (al menos no en hardware convencional).

¿Cuánto más seguro es usar lo siguiente?

Es "seguro", pero no logra mucho.

¿La técnica de campo anterior realmente va a ayudar?

No, por las mismas razones que arriba;)

pero aún así, el código generado por el compilador para acceder a ellos es más grande y más lento que el código generado para acceder a los primitivos.

Sí, es cierto. En la mayoría de las plataformas, esto requiere acceder al byte que contiene (o int o lo que sea), y luego realizar desplazamientos de bits y operaciones de máscara de bits para acceder al bit relevante.

Si está realmente preocupado por el uso de la memoria, puede usar un std::bitset en C ++ o un BitSet en Java, que BitSet los bits.

_{* Con algunas excepciones.}

Answer 2

¿Por qué no guardas el estado en un byte? Realmente no he probado el siguiente, pero debería darle una idea. Incluso puede utilizar un corto o un int para 16 o 32 estados. Creo que también tengo un ejemplo de trabajo de Java. Voy a publicar esto cuando lo encuentre.

__int8 state = 0x0;

bool getState(int bit)
{
  return (state & (1 << bit)) != 0x0;
}

void setAllOnline(bool online)
{
  state = -online;
}

void reverseState(int bit)
{
   state ^= (1 << bit);
}

Muy bien aquí está la versión de Java. Lo he almacenado en un valor Int desde. Si recuerdo correctamente, incluso utilizando un byte utilizaría 4 bytes de todos modos. Y esto obviamente no se puede utilizar como una matriz.

public class State
{
    private int STATE;

    public State() { 
        STATE = 0x0;
    }

    public State(int previous) { 
        STATE = previous;
    }


   /*
    * @Usage - Used along side the #setMultiple(int, boolean);
    * @Returns the value of a single bit.
    */
    public static int valueOf(int bit)
    {
        return 1 << bit;
    }


   /*
    * @Usage - Used along side the #setMultiple(int, boolean);
    * @Returns the value of an array of bits.
    */
    public static int valueOf(int... bits)
    {
        int value = 0x0;
        for (int bit : bits)
            value |= (1 << bit);
        return value;
    }


   /*
    * @Returns the value currently stored or the values of all 32 bits.
    */
    public int getValue() 
    {
        return STATE;
    }

   /*
    * @Usage - Turns all bits online or offline.
    * @Return - <TRUE> if all states are online. Otherwise <FALSE>.
    */
    public boolean setAll(boolean online)
    {
        STATE = online ? -1 : 0;
        return online;
    }


   /*
    * @Usage - sets multiple bits at once to a specific state.
    * @Warning - DO NOT SET BITS TO THIS! Use setMultiple(State.valueOf(#), boolean);
    * @Return - <TRUE> if states were set to online. Otherwise <FALSE>.
    */
    public boolean setMultiple(int value, boolean online)
    {
        STATE |= value;
        if (!online)
            STATE ^= value;
        return online;
    }


   /*
    * @Usage - sets a single bit to a specific state.
    * @Return - <TRUE> if this bit was set to online. Otherwise <FALSE>.
    */
    public boolean set(int bit, boolean online)
    {
        STATE |= (1 << bit);
        if(!online)
            STATE ^= (1 << bit);
        return online;
    }


   /*
    * @return = the new current state of this bit.
    * @Usage = Good for situations that are reversed.
    */
    public boolean reverse(int bit)
    {
        return (STATE ^= (1 << bit)) == (1 << bit);
    }


   /*
    * @return = <TRUE> if this bit is online. Otherwise <FALSE>.
    */
    public boolean online(int bit)
    {
        int value = 1 << bit;
        return (STATE & value) == value;        
    }


   /*
    * @return = a String contains full debug information.
    */
    @Override
    public String toString()
    {
        StringBuilder sb = new StringBuilder();
        sb.append("TOTAL VALUE: ");
        sb.append(STATE);
        for (int i = 0; i < 0x20; i++)
        {
            sb.append("/nState(");
            sb.append(i);
            sb.append("): ");
            sb.append(online(i));
            sb.append(", ValueOf: ");
            sb.append(State.valueOf(i));
        }
        return sb.toString();
    }
}

También debo señalar que realmente no debería utilizar una clase especial para esto, sino simplemente tener la variable almacenada dentro de la clase que será más probable que la utilice. Si planea tener 100 o incluso 1000 valores booleanos, considere una matriz de bytes.

Por ejemplo, el siguiente ejemplo.

boolean[] states = new boolean[4096];

Se puede convertir en el siguiente.

int[] states = new int[128];

Probablemente ahora se esté preguntando cómo accederá al índice 4095 desde una matriz de 128. Entonces, lo que esto está haciendo es si lo simplificamos. El 4095 se puede desplazar 5 bits a la derecha, lo que técnicamente es lo mismo que dividir por 32. Entonces 4095/32 = redondeado hacia abajo (127). Así que estamos en el índice 127 de la matriz. Luego realizamos 4095 y 31 que lo convertirán en un valor entre 0 y 31. Esto solo funcionará con potencias de dos menos 1. Por ejemplo, 0,1,3,7,15,31,63,127,255,511,1023, etc.

Así que ahora podemos acceder al bit en esa posición. Como puede ver, esto es muy compacto y supera los 4096 booleanos en un archivo :) Esto también proporcionará una lectura / escritura mucho más rápida en un archivo binario. No tengo idea de lo que es este material de BitSet, pero parece basura completa y, dado que byte, short, int, long ya están técnicamente en sus bits, puede usarlos como están. Luego creando una clase compleja para acceder a los bits individuales de la memoria, que es lo que pude captar al leer algunas publicaciones.

boolean getState(int index)
{
    return (states[index >> 5] & 1 << (index & 0x1F)) != 0x0;
}

Más información...

Básicamente, si lo anterior fue un poco confuso, aquí hay una versión simplificada de lo que está sucediendo.

Los tipos " byte ", " short ", " int ", " long " son todos tipos de datos que tienen diferentes rangos.

Puede ver este enlace: http://msdn.microsoft.com/en-us/library/s3f49ktz(v=vs.80).aspx

Para ver los rangos de datos de cada uno.

Así que un byte es igual a 8 bits. Así que un int que es de 4 bytes será de 32 bits.

Ahora no hay ninguna manera fácil de realizar algún valor a la potencia N. Sin embargo, gracias al cambio de bits podemos simularlo un poco. Al realizar 1 << N, esto equivale a 1 * 2 ^ N. Así que si hiciéramos 2 << 2 ^ N estaríamos haciendo 2 * 2 ^ N. Así que para realizar potencias de dos siempre haz "1 << N".

Ahora sabemos que un int tendrá 32 bits, por lo que podemos usar cada uno de los bits para que podamos simplemente indexarlos.

Para mantener las cosas simples, piense en el operador "&" como una forma de verificar si un valor contiene los bits de otro valor. Así que digamos que teníamos un valor que era 31. Para llegar a 31. debemos agregar los siguientes bits 0 a 4. Que son 1,2,4,8 y 16. Todos estos suman hasta 31. Ahora, cuando estamos realizando 31 y 16 esto devolverá 16 porque el bit 4, que es 2 ^ 4 = 16. Se encuentra en este valor. Ahora digamos que realizamos 31 y 20, que está verificando si los bits 2 y 4 están ubicados en este valor. Esto devolverá 20 ya que los bits 2 y 4 se encuentran aquí 2 ^ 2 = 4 + 2 ^ 4 = 16 = 20. Ahora digamos que hicimos 31 y 48. Esto está verificando los bits 4 y 5. Bueno, no lo hacemos tiene el bit 5 en 31. Por lo tanto, esto solo devolverá 16. No devolverá 0. Entonces, al realizar varias comprobaciones, debe verificar que físicamente es igual a ese valor. En lugar de comprobar si es igual a 0.

Lo siguiente verificará si un bit individual está en 0 o 1. 0 es falso y 1 es verdadero.

bool getState(int bit)
{
    return (state & (1 << bit)) != 0x0;
}

El siguiente ejemplo es el de verificar dos valores si contienen esos bits. Piense en ello como cada bit se representa como 2 ^ BIT así que cuando lo hacemos

Repasaré rápidamente algunos de los operadores. Acabamos de explicar ligeramente el operador "&". Ahora para el "|" operador.

Al realizar lo siguiente

int value = 31;
value |= 16;
value |= 16;
value |= 16;
value |= 16;

El valor seguirá siendo 31. Esto se debe a que el bit 4 o 2 ^ 4 = 16 ya está activado o configurado en 1. Por lo tanto, al ejecutar "|" devuelve ese valor con ese bit activado. Si ya está encendido no se hacen cambios. Utilizamos "| =" para establecer realmente la variable a ese valor devuelto.

En lugar de hacer -> "valor = valor | 16;". Simplemente hacemos "valor | = 16;".

Ahora veamos un poco más a fondo cómo se pueden utilizar " & " y " | ".

/*
 * This contains bits 0,1,2,3,4,8,9 turned on.
 */
const int CHECK = 1 | 2 | 4 | 8 | 16 | 256 | 512;

/*
 * This is some value were we add bits 0 through 9, but we skip 0 and 8.
 */
int value = 2 | 4 | 8 | 16 | 32 | 64 | 128 | 512;

Así que cuando realizamos el siguiente código.

int return_code = value & CHECK;

El código de retorno será 2 + 4 + 8 + 16 + 512 = 542

Así que comprobamos 799, pero recibimos 542 Esto se debe a que los bits o y 8 están fuera de línea, somos iguales a 256 + 1 = 257 y 799 - 257 = 542.

Lo anterior es excelente. Es una excelente manera de comprobar si estamos haciendo un videojuego y queremos comprobar si se presionaron los botones si se presionó alguno de ellos. Podríamos simplemente revisar cada uno de esos bits con un solo cheque y sería mucho más eficiente que realizar un chequeo booleano en cada estado.

Ahora digamos que tenemos un valor booleano que siempre se invierte.

Normalmente harías algo como

bool state = false;

state = !state;

Bueno, esto se puede hacer con bits y utilizando el operador " ^ ".

Así como ejecutamos "1 << N" para elegir el valor total de ese bit. Podemos hacer lo mismo con lo contrario. Así que al igual que mostramos cómo "| =" almacena el rendimiento, haremos lo mismo con "^ =". Entonces, lo que esto hace es que si ese bit está activado, lo desactivamos. Si está apagado lo encendemos.

void reverseState(int bit)
{
   state ^= (1 << bit);
}

Incluso puede tener que devolver el estado actual. Si desea que vuelva al estado anterior, simplemente cambie "! =" A "==". Entonces, lo que esto hace es realizar la reversión y luego verifica el estado actual.

bool reverseAndGet(int bit)
{
    return ((state ^= (1 << bit)) & (1 << bit)) != 0x0;
}

También se puede almacenar múltiples valores bools no únicos conocidos en un int. Digamos que normalmente escribimos nuestra posición de coordenadas como la siguiente.

int posX = 0;
int posY = 0;
int posZ = 0;

Ahora digamos que nunca pasaron 1023. Entonces, de 0 a 1023 fue la distancia máxima en todos estos. Elijo 1023 para otros fines, como se mencionó anteriormente, puede manipular la variable "&" como una forma de forzar un valor entre 0 y 2 ^ N - 1 valores. Así que digamos que su rango fue de 0 a 1023. Podemos realizar "valor & 1023" y siempre será un valor entre 0 y 1023 sin ninguna verificación de parámetros de índice. Tenga en cuenta que como se mencionó anteriormente, esto solo funciona con potencias de dos menos uno. 2 ^ 10 = 1024 - 1 = 1023.

Por ejemplo, no más si (valor> = 0 & & valor <= 1023).

Entonces 2 ^ 10 = 1024, que requiere 10 bits para mantener un número entre 0 y 1023.

Entonces 10x3 = 30, que aún es menor o igual a 32. Es suficiente para mantener todos estos valores en un int.

Así podemos realizar lo siguiente. Así que para ver cuántos bits utilizamos. Hacemos 0 + 10 + 20. La razón por la que pongo el 0 es para mostrarte visualmente que 2 ^ 0 = 1, así que # * 1 = #. La razón por la que necesitamos y << 10 es porque x usa hasta 10 bits, que es de 0 a 1023. Por lo tanto, necesitamos multiplicar y por 1024 para tener valores únicos para cada uno. Entonces Z necesita ser multiplicado por 2 ^ 20 que es 1,048,576.

int position = (x << 0) | (y << 10) | (z << 20);

Esto hace que las comparaciones sean rápidas.

Ahora podemos hacer

return this.position == position;

apegado a

return this.x == x && this.y == y && this.z == z;

Ahora, ¿y si quisiéramos las posiciones reales de cada uno?

Para la x simplemente hacemos lo siguiente.

int getX()
{ 
   return position & 1023;
}

Luego para la y necesitamos realizar un cambio de bit a la izquierda y luego Y.

int getY()
{ 
   return (position >> 10) & 1023;
}

Como puedes imaginar, la Z es la misma que la Y, pero en lugar de 10 usamos 20.

int getZ()
{ 
   return (position >> 20) & 1023;
}

Espero que quienquiera que vea esto valga la pena la información :).

Answer 3

El uso de un solo bit es mucho más lento y mucho más complicado de asignar. En C / C ++ no hay forma de obtener la dirección de un bit, por lo que no sería capaz de hacer &trueOrFalse como un bit.

Java tiene un BitSet y un EnumSet que usan mapas de bits. Si tienes un número muy pequeño puede que no haga mucha diferencia. por ejemplo, los objetos deben estar alineados al menos por bytes y en HotSpot están alineados por 8 bytes (en C ++, un new Objeto puede estar alineado por 8 a 16 bytes) Esto significa que guardar algunos bits puede no ahorrar espacio.

Al menos en Java, los Bits no son más rápidos a menos que encajen mejor en el caché.

public static void main(String... ignored) {
    BitSet bits = new BitSet(4000);
    byte[] bytes = new byte[4000];
    short[] shorts = new short[4000];
    int[] ints = new int[4000];

    for (int i = 0; i < 100; i++) {
        long bitTime = timeFlip(bits) + timeFlip(bits);
        long bytesTime = timeFlip(bytes) + timeFlip(bytes);
        long shortsTime = timeFlip(shorts) + timeFlip(shorts);
        long intsTime = timeFlip(ints) + timeFlip(ints);
        System.out.printf("Flip time bits %.1f ns, bytes %.1f, shorts %.1f, ints %.1f%n",
                bitTime / 2.0 / bits.size(), bytesTime / 2.0 / bytes.length,
                shortsTime / 2.0 / shorts.length, intsTime / 2.0 / ints.length);
    }
}

private static long timeFlip(BitSet bits) {
    long start = System.nanoTime();
    for (int i = 0, len = bits.size(); i < len; i++)
        bits.flip(i);
    return System.nanoTime() - start;
}

private static long timeFlip(short[] shorts) {
    long start = System.nanoTime();
    for (int i = 0, len = shorts.length; i < len; i++)
        shorts[i] ^= 1;
    return System.nanoTime() - start;
}

private static long timeFlip(byte[] bytes) {
    long start = System.nanoTime();
    for (int i = 0, len = bytes.length; i < len; i++)
        bytes[i] ^= 1;
    return System.nanoTime() - start;
}

private static long timeFlip(int[] ints) {
    long start = System.nanoTime();
    for (int i = 0, len = ints.length; i < len; i++)
        ints[i] ^= 1;
    return System.nanoTime() - start;
}

huellas dactilares

Flip time bits 5.0 ns, bytes 0.6, shorts 0.6, ints 0.6

Para tamaños de 40000 y 400K.

Flip time bits 6.2 ns, bytes 0.7, shorts 0.8, ints 1.1

para 4M

Flip time bits 4.1 ns, bytes 0.5, shorts 1.0, ints 2.3

y 40M

Flip time bits 6.2 ns, bytes 0.7, shorts 1.1, ints 2.4

Answer 4

Si desea almacenar solo un bit de información, no hay nada más compacto que un char , que es la unidad de memoria direccionable más pequeña en C / C ++. (Dependiendo de la implementación, un bool puede tener el mismo tamaño que un char pero se permite que sea más grande ).

El estándar C garantiza que el char es char para al menos 8 bits, sin embargo, también puede contener más. El número exacto está disponible a través de la macro CHAR_BIT definida en limits.h (en C) o climits (C ++). Hoy en día, es más común que CHAR_BIT == 8 pero no puede confiar en él (consulte here ). Sin embargo, se garantiza que será 8 en los sistemas compatibles con POSIX y en Windows .

Aunque no es posible reducir la huella de memoria para una sola bandera, por supuesto es posible combinar varias banderas. Además de hacer todas las operaciones de bit manualmente , hay algunas alternativas:

• Si conoces el número de bits en tiempo de compilación
  1. bitfields (como en su pregunta). Pero tenga cuidado, el orden de los campos no está garantizado, lo que puede resultar en problemas de portabilidad.
  2. std::bitset
• Si conoces el tamaño solo en tiempo de ejecución.
  1. boost::dynamic_bitset
  2. Si tiene que lidiar con grandes vectores de bits, eche un vistazo a la biblioteca de BitMagic . Es compatible con la compresión y está muy sintonizado.

Como otros ya han señalado, guardar algunos bits no siempre es una buena idea. Los posibles inconvenientes son:

1. Código menos legible
2. Velocidad de ejecución reducida debido al código extra de extracción.
3. Por el mismo motivo, los aumentos en el tamaño del código, que pueden superar los ahorros en el consumo de datos.
4. Problemas ocultos de sincronización en programas multihilo. Por ejemplo, voltear dos bits diferentes por dos hilos diferentes puede resultar en una condición de carrera. En contraste, siempre es seguro que dos subprocesos modifiquen dos objetos diferentes de tipos primitivos (por ejemplo, char ).

Por lo general, tiene sentido cuando se trata de grandes datos, porque entonces se beneficiará de una menor presión sobre la memoria y la memoria caché.

Answer 5

Si realmente desea usar 1 bit, puede usar un char para almacenar 8 booleanos, y bitshift para obtener el valor del que desea. Dudo que sea más rápido, y probablemente te dará muchos dolores de cabeza de esa manera, pero técnicamente es posible.

En una nota al margen, un intento como este podría ser útil para los sistemas que no tienen mucha memoria disponible para las variables, pero tienen más capacidad de procesamiento que lo que necesita. Aunque dudo mucho que alguna vez lo necesites.