Мне нужно создать очень большой массив битов / логических значений. Как бы я сделал это в C / C ++?

Question

Можно ли вообще создать массив битов с более чем 100000000 элементов? Если это так, как бы я поступил так? Я знаю, что для массива символов я могу сделать это:

char* array;

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

Если бы я объявил массив с помощью char array[100000000], я бы получил ошибку сегментации, так как было превышено максимальное количество элементов, поэтому я использую malloc.

Есть ли что-то подобное, что я могу сделать для массива битов?

Answer 1

Если вы используете C ++, std::vector<bool> специализируется для упаковки элементов в битовую карту. Конечно, если вы используете C ++, вам нужно прекратить использовать malloc.

Answer 2

Вы можете попробовать посмотреть boost :: dynamic_bitset . Затем вы можете сделать что-то вроде следующего (взято со страницы примера Boost):

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

Битовый набор будет использовать один бит для каждого элемента, поэтому вы можете хранить 32 элемента в пространстве 4 байта, значительно уменьшая объем требуемой памяти.

Answer 3

В C и C ++, char - самый маленький тип. Вы не можете напрямую объявить массив битов. Однако, поскольку массив любого базового типа в основном состоит из битов, вы можете эмулировать их, что-то вроде этого (код не проверен):

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

Заметная ошибка сегментации связана с нехваткой места в стеке. Конечно, вы не можете объявить локальную переменную размером 12,5 МБ (100 миллионов бит), не говоря уже о 100 МБ (100 миллионов байтов) в потоке со стеком ~ 4 МБ. Должна работать как глобальная переменная, хотя в этом случае вы можете получить исполняемый файл размером 12 или 100 МБ, но это не очень хорошая идея. Динамическое распределение - определенно правильная вещь для таких больших буферов.

Answer 5

Если разрешено использовать STL, то я бы использовал std::bitset.

(Для 100 000 000 битов будет использоваться 100000000/32 unsigned int внизу, каждый из которых хранит 32 бита.)

std::vector<bool>, как уже упоминалось, является еще одним хорошим решением.

Answer 6

Существует несколько подходов к созданию растрового изображения в C ++.

Если вы уже знаете размер растрового изображения во время компиляции, вы можете использовать шаблон STL, std::bitset.

Вот как бы вы сделали это с помощью bitset std::bitset<100000000> array

В противном случае, если размер растрового изображения динамически изменяется во время выполнения, вы можете использовать std::vector<bool> или boost::dynamic_bitset, как рекомендуется здесь http://en.cppreference.com/w/cpp/utility/bitset (см. Примечание внизу)

Answer 7

Мне нравится bitarray, который находится в fxt библиотеке с открытым исходным кодом по адресу http://www.jjj.de/fxt/. Это просто, эффективно и содержится в нескольких заголовках, поэтому его легко добавить в ваш проект. Кроме того, есть много дополнительных функций, которые можно использовать с bitarray (см. http://www.jjj.de/bitwizardry/bitwizardrypage.html).

Answer 8

Другое решение:

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

Да, но это будет немного сложнее!

Лучший способ хранить биты - использовать биты в самом символе!

Таким образом, вы можете хранить 8 бит в символе!

Что будет "только" потребует 12'500'000 октетов!

Вот некоторая документация по двоичным файлам: http://www.somacon.com/p125.php

Вы должны посмотреть на Google:)