Posso atribuir um número específico de bits em C?

Question

Eu estou tentando armazenar uma grande quantidade de informações booleano que é determinada pelo tempo de execução. Eu queria saber qual o melhor método pode ser.

Eu tenho atualmente tentando alocar a memória usando:

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

pensar que isso vai me dar bits suficientes para trabalhar. I pode, em seguida, fazer referência a cada valor booleano usando o ponteiro em notação de matriz:

pStatus[element]

Infelizmente, este não parece estar funcionando muito bem. Primeiro, eu estou tendo dificuldade inicializando a memória para o valor inteiro 0. isso pode ser feito usando memset()? Ainda assim, eu não acho que isso está impactando porque eu falhar ao tentar acessar pStatus[element].

Estou também não inteiramente convencido que esta abordagem é a melhor para estar usando. O que eu realmente quero é essencialmente uma máscara de bits gigante que reflete o status dos valores booleanos. Eu perdi alguma coisa?

Answer 1

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

Isto não alocar suficiente bytes para seus bits. No entanto,

pStatus[element]

Este acessa o element'th byte , e não pouco. Então, quando o elemento é mais do que um oitavo do número total de bits, você está acessando fora da extremidade da matriz alocada.

Eu definiria algumas funções 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;
}

(verificação de erros na gama de elemento deixado de fora para maior clareza. Você poderia fazer este macros, também)

Answer 2

... pensando que isso vai me dar bits suficientes para trabalhar. I pode, em seguida, fazer referência a cada valor booleano usando o ponteiro em notação de matriz:

pStatus[element]

elemento é abordar bytes , e não pedaços. Você quer algo como:

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

Answer 3

pequeno ponto: para obter memória suficiente para armazenar N bits, (N / 8) + 1 bytes é imprecisa (pode ser um demasiados)

.

(N + 7) / 8 é sempre o número mínimo, embora.

Answer 4

Bem, a resposta mais simples seria usar calloc em vez de malloc.

é definido É para inicializar a memória que ele aloca para zero, e muitas vezes podem fazê-lo usando truques de mapeamento página.

Isso vai cuidar do seu problema de inicialização da memória. Os outros dúzia de mensagens aqui parecem enfrentar adequadamente o problema de indexação e o fato de que você ocasionalmente alocar um byte extra (oh o horror!), Por isso não vou repetir o seu conteúdo aqui.

Answer 5

pStatus [elemento] lhe dará uma byte inteiro nesse endereço.

Para definir um elemento particular que você faria algo assim:

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

Para redefinir um elemento:

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

e testar um elemento:

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

a verba inicial deve ser

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

o que você tinha vai funcionar, mas desperdiça um byte ocasionalmente

Answer 6

Eu não posso deixar de notar que todas as respostas em C aqui parecem assumir que um byte é 8 bits. Isso não é necessariamente verdade em C (embora, naturalmente, ser verdade na maioria hardware convencional), de modo a fazer essa suposição em código é bastante má forma.

A maneira correta de código de arquitetura neutra gravação é

#include <limits.h>

e, em seguida, usar a macro CHAR_BIT onde quer que você precisa "o número de bits em um char".

Answer 7

Faça-se mais feliz e definir um tipo e funções para operar nesse tipo. Dessa forma, se você descobrir que acessos bits são muito lento, você pode alterar a unidade de memória por booleano para um byte / word / long ou adotar esparsas / estruturas de dados dinâmicas se a memória não é realmente um problema (ou seja, se os seus sets são principalmente zeros , você poderia simplesmente manter uma lista com as coordenadas dos 1s.

Você pode escrever seu código para ser completamente imune a alterações na implementação do seu pouco vetor.

Answer 8

pStatus [element] não aborda a pouco. O byte exato que recebe é dependente do tipo de pStatus - Presumo char * ou equivalente -. Modo pStatus [elemento] você recebe o byte element'th

Você poderia memset para set a 0, sim.

Answer 9

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

Belas Essa parte.

 pStatus[element]

aqui é onde você tem problemas. Você está bytes de endereço, quando você quer bits de endereço.

 pStatus[element / 8 ]  

você irá obter o byte direita na matriz.

Answer 10

Você precisa alocar bytes c = malloc((N+7)/8), e você pode definir o enésimo com

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

claro com

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

e teste com

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

Answer 11

Se você não se importa ter de invólucros de gravação, você também pode usar bit_set ou bit_vector de STL do C ++, parece que eles (especialmente o último) têm exatamente o que você precisa, já codificados, testados e embalados (e muito sinos e assobios).

É uma verdadeira vergonha, falta-nos uma maneira para a frente para usar o código C ++ em aplicações C (não, criando um invólucro não é tão simples para mim, nem divertido, e significa mais trabalho a longo prazo).

Answer 12

O que seria errado com std::vector<bool>?

Answer 13

Espanta-me que apenas uma resposta aqui menciona CHAR_BIT. Um byte é muitas vezes 8 bits, mas nem sempre.

Answer 14

código de alocação Você está correta, consulte as funções set_bit() e get_bit() dadas em esta resposta para acessar o boolean.

Answer 15

Se você está limitado a apenas alguns bits que você pode, em vez de eaanon01 solução também usar o c builtin facilidade de bitfield (há muito poucos ocasião onde você pode usá-los, mas isso seria um)

Para este material batendo pouco posso recommendate: Herny Warrens "Hacker Delight"

Answer 16

O boolean é "nunca" um valor separado em C. Assim, um struct poderia estar em ordem para você ir.

É verdade que você não inicializar a área de mem então você precisa fazer isso individualmente.

Aqui está um exemplo simples de como você poderia fazê-lo com os sindicatos estruturas e enumerações

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 isso ajude. Este exemplo pode lidar com até 64 booleans status e poderia ser fácil estendida.

Este exapmle baseia-se Char = 8 bits int = 16 bits de comprimento int = 32 bits e de longa longo int = 64 bits

Eu agora também adicionou suporte para grupos de status.