Preciso criar uma variedade muito grande de bits/valores booleanos. Como eu faria isso em C/C ++?

Question

É possível criar uma variedade de bits com mais de 100000000 elementos? Se for, como eu iria fazer isso? Eu sei disso para uma matriz de char, posso fazer isso:

char* array;

array = (char*)malloc(100000000 * sizeof(char));

Se eu fosse declarar a matriz por char array[100000000] Então eu receberia uma falha de segmentação, pois o número máximo de elementos foi excedido, e é por isso que eu uso malloc.

Existe algo semelhante que eu possa fazer para uma variedade de bits?

Answer 1

Se você estiver usando C ++, std::vector<bool> é especializado para embalar elementos em um mapa de bits. Claro, se você estiver usando C ++, precisa parar de usar malloc.

Answer 2

Você poderia tentar olhar para Boost :: Dynamic_bitset. Então você pode fazer algo como o seguinte (retirado da página de exemplo do Boost):

boost::dynamic_bitset<> x(100000000); // all 0's by default
x[0] = 1;
x[1] = 1;
x[4] = 1;

O bitset usará um único bit para cada elemento para que você possa armazenar 32 itens no espaço de 4 bytes, diminuindo consideravelmente a quantidade de memória necessária.

Answer 3

Em C e C ++, char é o menor tipo. Você não pode declarar diretamente uma variedade de bits. No entanto, como uma variedade de qualquer tipo básico é fundamentalmente feita de bits, você pode imitá -los, algo assim (código não testado):

unsigned *array;
array = (unsigned *) malloc(100000000 / sizeof(unsigned) + 1);

/* Retrieves the value in bit i */
#define GET_BIT(array, i) (array[i / sizeof(unsigned)] & (1 << (i % sizeof(unsigned))))

/* Sets bit i to true*/
#define SET_BIT(array, i) (array[i / sizeof(unsigned)] |= (1 << (i % sizeof(unsigned))))

/* Sets bit i to false */
#define CLEAR_BIT(array, i) (array[i / sizeof(unsigned)] &= ~(1 << (i % sizeof(unsigned))))

Answer 4

A falha de segmentação que você notou é devido à saída do espaço da pilha. É claro que você não pode declarar uma variável local com 12,5 Mb de tamanho (100 milhões de bits), muito menos 100 MB de tamanho (100 milhões de bytes) em um tópico com uma pilha de ~ 4 MB. Deve funcionar como uma variável global, embora você possa acabar com um arquivo executável de 12 ou 100 MB - ainda não é uma boa ideia. A alocação dinâmica é definitivamente a coisa certa a fazer para grandes buffers como esse.

Answer 5

Se puder usar o STL, eu usaria std::bitset.

(Para 100.000.000 bits, ele usaria 100000000 /32 unsigned int por baixo, cada um armazenando 32 bits.)

std::vector<bool>, já mencionado, é outra boa solução.

Answer 6

Existem algumas abordagens para criar um bitmap no C ++.

Se você já sabe o tamanho do bitmap em tempo de compilação, pode usar o STL, std::bitset modelo.

É assim que você faria com bitsetstd::bitset<100000000> array

Caso contrário, se o tamanho do bitmap mudar dinamicamente durante o tempo de execução, você poderá usar std::vector<bool> ou boost::dynamic_bitset conforme recomendado aqui http://en.cppreference.com/w/cpp/utility/bitset (Veja a nota na parte inferior)

Answer 7

Sim, mas vai ser um pouco mais complicado!

A melhor maneira de armazenar pedaços é usar os bits no próprio char!

Então você pode armazenar 8 bits em um char!

O que vai "só" requer 12'500 '000 octetos!

Aqui está alguma documentação sobre binários: http://www.somacon.com/p125.php

Você deve olhar no google :)

Answer 8

Outra solução:

unsigned char * array;
array = (unsigned char *) malloc ( 100000000 / sizeof(unsigned char) + 1);

bool MapBit ( unsigned char arraybit[], DWORD position, bool set)
{
    //work for 0 at 4294967295 bit position
    //calc bit position
    DWORD bytepos = ( position / 8 );
    //
    unsigned char bitpos =  ( position % 8);

    unsigned char bit = 0x01;

    //get bit
    if ( bitpos )
    {
        bit = bit << bitpos;
    }

    if ( set )
    {
        arraybit [ bytepos ] |= bit;
    }
    else
    {
        //get
        if ( arraybit [ bytepos ] & bit )
            return true;
    }

    return false;
}

Answer 9

Gosto do BitArray que está na biblioteca FXT de código aberto em http://www.jjj.de/fxt/. É simples, eficiente e contido em alguns cabeçalhos, por isso é fácil adicionar ao seu projeto. Além disso, existem muitas funções complementares para usar com o BITARRAY (veja http://www.jjj.de/bitwizardry/bitwizardrypage.html).