rotacion - ¿Puedo asignar un número específico de bits en C?

rotacion de bits en c

Question

Intento almacenar una gran cantidad de información booleana que se determina en tiempo de ejecución. Me preguntaba cuál sería el mejor método.

En este momento he estado tratando de asignar la memoria usando:

pStatus = malloc((<number of data points>/8) + 1);

pensando que esto me dará suficientes bits para trabajar. Podría entonces hacer referencia a cada valor booleano usando la notación puntero en matriz:

pStatus[element]

Lamentablemente, esto no parece funcionar muy bien. Primero, tengo dificultades para inicializar la memoria en el valor entero 0 . ¿Se puede hacer esto usando memset() ? Aún así, no creo que eso esté impactando por qué bloqueo cuando intento acceder a pStatus[element] .

Tampoco estoy del todo convencido de que este enfoque sea el mejor para usar. Lo que realmente quiero es esencialmente una máscara de bits gigante que refleje el estado de los valores booleanos. ¿Me he perdido algo?

Answer 1

Bueno, la respuesta más simple sería usar calloc en lugar de malloc.

Está definido para inicializar la memoria que asigna a cero, y a menudo puede hacerlo mediante el uso de trucos de mapeo de páginas.

Eso se ocupará de su problema de inicialización de memoria. La otra docena de publicaciones aquí parecen abordar adecuadamente el problema de indexación y el hecho de que ocasionalmente asignas un byte extra (¡oh, horror!), Así que no repetiré su contenido aquí.

Answer 2

Hazte más feliz y define un tipo y funciones para operar en ese tipo. De esta forma, si descubre que los accesos de bit son demasiado lentos, puede cambiar la unidad de memoria por booleano a byte / palabra / largo o adoptar estructuras de datos dispersas / dinámicas si la memoria es realmente un problema (es decir, si sus conjuntos son en su mayoría ceros) , podrías mantener una lista con las coordenadas de los 1.

Puede escribir su código para ser completamente inmune a los cambios en la implementación de su vector de bits.

Answer 3

Si no te importa tener que escribir wrappers, también puedes usar bit_set o bit_vector del STL de C ++, parece que (especialmente el último) tienen exactamente lo que necesitas, ya codificado, probado y empaquetado (y muchas campanas y silbatos) )

Es una verdadera lástima que nos falte una manera directa de usar el código C ++ en las aplicaciones C (no, crear un contenedor no es directo para mí, ni divertido, y significa más trabajo a largo plazo).

Answer 4

pStatus [elemento] le dará un byte completo en esa dirección.

Para establecer un elemento en particular, harías algo como:

pStatus[element >> 3] |= 1 << (element & 7);

Para restablecer un elemento:

pStatus[element >> 3] &= ~1 << (element & 7);

y para probar un elemento:

if (pStatus[element >> 3] & (1 << (element & 7)) != 0)

la asignación inicial debe ser

pstatus = malloc((<number of data points> + 7) / 8)

lo que tengas funcionará pero desperdicia un byte ocasionalmente

Answer 5

pStatus [elemento] no aborda el bit. El byte exacto que obtiene depende del tipo de pStatus, supongo que es char * o equivalente, por lo que pStatus [elemento] te proporciona el elemento byte.

Podrías establecerme a 0, sí.

Answer 6

c = malloc((N+7)/8) asignar c = malloc((N+7)/8) bytes, y puede establecer la enésima con

 c[n/8]=((c[n/8] & ~(0x80 >> (n%8))) | (0x80>>(n%8)));

claro con

 c[n/8] &= ~(0x80 >> (n%8));

y prueba con

 if(c[n/8] & (0x80 >> (n%8))) blah();

Answer 7

... pensando que esto me dará suficientes bits para trabajar. Podría entonces hacer referencia a cada valor booleano usando la notación puntero en matriz:

pStatus[element]

el elemento está abordando bytes , no bits. Quieres algo como:

pStatus[element/8] & (1 << (element % 8))

Answer 8

 pStatus = malloc((<number of data points>/8) + 1);

Esa parte está bien.

 pStatus[element]

aquí es donde tienes problemas. Eres bytes de dirección, cuando quieres direccionar bits.

 pStatus[element / 8 ]  

obtendrá el byte correcto en la matriz.

Answer 9

El booleano es "nunca" un valor separado en C. Así que una estructura podría ser para ayudarte a avanzar.

Es cierto que no inicializa el área de memoria, por lo que debe hacerlo de forma individual.

Aquí hay un ejemplo simple de cómo podría hacerlo con las estructuras y enumeraciones de los sindicatos

typedef unsigned char           BYTE;
typedef unsigned short          WORD;
typedef unsigned long int       DWORD;
typedef unsigned long long int  DDWORD;
enum STATUS
{
    status0 = 0x01,
    status1 = 0x02,
    status2 = 0x04,
    status3 = 0x08,
    status4 = 0x10,
    status5 = 0x20,
    status6 = 0x40,
    status7 = 0x80,
status_group = status0 + status1 +status4
};
#define GET_STATUS( S ) ( ((status.DDBuf&(DDWORD)S)==(DDWORD)S) ? 1 : 0  )
#define SET_STATUS( S ) (  (status.DDBuf|=  (DDWORD)S) )
#define CLR_STATUS( S ) (  (status.DDBuf&= ~(DDWORD)S) )
static union {
 BYTE   BBuf[8];
 WORD   WWBuf[4];
 DWORD  DWBuf[2];
 DDWORD DDBuf;
}status;

int main(void)
{
    // Reset status bits
    status.BBuf[0] = 0;
    printf( "%d /n", GET_STATUS( status0 ) );

    SET_STATUS( status0 );
    printf( "%d /n", GET_STATUS( status0 ) );

    CLR_STATUS(status0);
    printf( "%d /n", GET_STATUS( status0 ) );
    SET_STATUS( status_group );
    printf( "%d /n", GET_STATUS( status0 ) );
    system( "pause" );
    return 0;
}

Espero que esto ayude. Este ejemplo puede manejar hasta 64 booleanos de estado y podría extenderse fácilmente.

Este ejemplo se basa en Char = 8 bits int = 16 bits de longitud int = 32 bits y long long int = 64 bits

Ahora también he agregado soporte para grupos de estado.

Answer 10

No puedo dejar de notar que todas las respuestas en C parecen suponer que un byte es de 8 bits. Esto no es necesariamente cierto en C (aunque, por supuesto, será cierto en la mayoría de hardware convencional), por lo que hacer esta suposición en el código es bastante mala.

La forma correcta de escribir código de arquitectura neutral es

#include <limits.h>

y luego use la macro CHAR_BIT donde necesite "la cantidad de bits en un char ".

Answer 11

Punto pequeño: para obtener suficiente memoria para almacenar N bits, (N / 8) + 1 byte es impreciso (puede ser uno demasiado).

(N + 7) / 8 es siempre el número mínimo, sin embargo.

Answer 12

Si está limitado a solo unos pocos bits, en lugar de la solución eaanon01, también puede usar la función integrada de bitfield (hay muy pocas ocasiones en que podría usarlos, pero esta sería una)

Por este poco de golpear cosas que puedo recomendar: Herny Warrens "Hacker Delight"

Answer 13

¿Qué estaría mal con std::vector<bool> ?

Answer 14

Me sorprende que solo una respuesta aquí mencione CHAR_BIT. Un byte a menudo es de 8 bits, pero no siempre.

Answer 15

set_bit() código de asignación es correcto, vea las set_bit() y get_bit() dadas en esta respuesta para acceder al booleano.

Answer 16

pStatus = malloc((<number of data points>/8) + 1);

Esto asigna suficientes bytes para tus bits. Sin embargo,

pStatus[element]

Esto accede al elemento '' byte , no a bit. Entonces, cuando el elemento es más de un octavo del número total de bits, está accediendo al final de la matriz asignada.

Definiría algunas funciones auxiliares

int get_bit(int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    return ((pStatus[byte_index] & bit_mask) != 0);
}

void set_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] |= bit_mask);
}

void clear_bit (int element)
{
    uint byte_index = element/8;
    uint bit_index = element % 8;
    uint bit_mask = ( 1 << bit_index);

    pStatus[byte_index] &= ~bit_mask;
}

(error al verificar el rango del elemento omitido para mayor claridad. También podría hacer estas macros)