Алгоритм Как построить N битовых переменных в C ++?
Я имею дело с очень большим списком логических значений в C ++, около 2 ^ N элементов по N логических значений каждый. Поскольку в такой ситуации память является критической, то есть экспоненциальный рост, я хотел бы создать переменную длиной N бит для хранения каждого элемента.
Для малого N, например 24, я просто использую unsigned long int, Требуется 64 МБ ((2 ^ 24) * 32/8/1024/1024). Но мне нужно подняться до 36. Единственный вариант с встроенной переменной это unsigned long long int, но это занимает 512 ГБ ((2 ^ 36) * 64/8/1024/1024/1024), что слишком много.
С 36-битной переменной это будет работать для меня, потому что размер падает до 288 ГБ ((2 ^ 36) * 36/8/1024/1024/1024), который подходит для узла моего суперкомпьютера.
Я старался std::bitset, но std::bitset< N > создает элемент не менее 8В.
Итак, список std::bitset< 1 > намного больше, чем список unsigned long int,
Это потому что std::bitset просто измените представление, а не контейнер.
Я тоже пробовал boost::dynamic_bitset<> от Boost, но результат еще хуже (не менее 32B!) по той же причине.
Я знаю, что вариант — записать все элементы в виде одной логической цепочки 2473901162496 (2 ^ 36 * 36), а затем сохранить ее в 38654705664 (2473901162496/64). unsigned long long int, что дает 288 ГБ (38654705664 * 64/8/1024/1024/1024). Тогда получить доступ к элементу — это просто игра, чтобы выяснить, в каких элементах хранятся 36 бит (может быть один или два). Но переписывание существующего кода (3000 строк) требует много усилий, потому что отображение становится невозможным, а добавление и удаление элементов во время выполнения в некоторых функциях, безусловно, будет сложным, запутанным, сложным, и результат, скорее всего, будет неэффективным.
Как построить N-битную переменную в C ++?
Решение
Как насчет структуры с 5-ю символами (и, возможно, некоторой причудливой перегрузкой операторов, необходимой для обеспечения ее совместимости с существующим кодом)? Структура с long и char, вероятно, не будет работать из-за заполнения / выравнивания …
По сути, ваш собственный мини-BitSet оптимизирован по размеру:
struct Bitset40 {
unsigned char data[5];
bool getBit(int index) {
return (data[index / 8] & (1 << (index % 8))) != 0;
}
bool setBit(int index, bool newVal) {
if (newVal) {
data[index / 8] |= (1 << (index % 8));
} else {
data[index / 8] &= ~(1 << (index % 8));
}
}
};
редактировать: Как geza также указал в своих комментариях, «хитрость» здесь заключается в том, чтобы максимально приблизиться к минимальному количеству необходимых байтов (без потери памяти путем запуска потерь на выравнивание, заполнения или косвенного обращения указателя, см. http://www.catb.org/esr/structure-packing/).
Редактировать 2Если вы чувствуете себя авантюрным, вы также можете попробовать немного (и, пожалуйста, дайте нам знать, сколько места на самом деле он потребляет):
struct Bitset36 {
unsigned long long data:36;
}
Другие решения
Я не эксперт, но это то, что я бы «попробовал». Найдите байты для наименьшего типа, поддерживаемого вашим компилятором (должен быть char). Вы можете проверить с помощью sizeof и получить 1. Это означает 1 байт, то есть 8 бит.
Так что, если вы хотите 24-битный тип … вам понадобится 3 символа. Для 36 вам понадобится массив из 5 символов, и в конце у вас будет 4 бита отступа. Это легко можно объяснить.
то есть
char typeSize[3] = {0}; // should hold 24 bits
Теперь создайте битовую маску для доступа к каждой позиции typeSize.
const unsigned char one = 0b0000'0001;
const unsigned char two = 0b0000'0010;
const unsigned char three = 0b0000'0100;
const unsigned char four = 0b0000'1000;
const unsigned char five = 0b0001'0000;
const unsigned char six = 0b0010'0000;
const unsigned char seven = 0b0100'0000;
const unsigned char eight = 0b1000'0000;
Теперь вы можете использовать побитовый или установить значения в 1, где это необходимо.
typeSize[1] |= four;
*typeSize[0] |= (four | five);
Чтобы отключить биты используйте & оператор ..
typeSize[0] &= ~four;
typeSize[2] &= ~(four| five);
Вы можете прочитать положение каждого бита с помощью & оператор.
typeSize[0] & four
Имейте в виду, у меня нет под рукой компилятора, так что, надеюсь, это полезный подход к вашей проблеме.
Удачи 😉
Вы можете использовать массив unsigned long int и хранить и извлекать необходимые цепочки битов с помощью побитовых операций. Этот подход исключает накладные расходы.
Упрощенный пример для байтового массива без знака B [] и 12-битных переменных V (представленных как ushort):
Set V[0]:
B[0] = V & 0xFF; //low byte
B[1] = B[1] & 0xF0; // clear low nibble
B[1] = B[1] | (V >> 8); //fill low nibble of the second byte with the highest nibble of V