Если 32-разрядное целое число переполняется, можем ли мы использовать 40-разрядную структуру вместо 64-разрядной?
Если, скажем, 32-разрядное целое число переполняется вместо обновления int в longМожем ли мы использовать какой-нибудь 40-битный тип, если нам нужен диапазон только в пределах 240, чтобы мы сохранили 24 (64-40) бит для каждого целого числа?
Если так, то как?
Мне приходится иметь дело с миллиардами, а пространство - это большее ограничение.
14 ответов
Да, но...
Это, конечно, возможно, но обычно это бессмысленно (для любой программы, которая не использует миллиарды этих чисел):
#include <stdint.h> // don't want to rely on something like long long
struct bad_idea
{
uint64_t var : 40;
};
Вот, var будет действительно иметь ширину 40 бит за счет гораздо менее эффективного сгенерированного кода (оказывается, что "много" очень неправильно - измеренные издержки составляют всего 1-2%, см. время ниже), и обычно для безрезультатно. Если вам не нужно другое 24-битное значение (или 8- и 16-битное значение), которое вы хотите упаковать в ту же структуру, выравнивание утратит все, что вы можете получить.
В любом случае, если у вас их нет на миллиарды, эффективная разница в потреблении памяти не будет заметна (но дополнительный код, необходимый для управления битовым полем, будет заметен!).
Замечания:
Тем временем вопрос был обновлен, чтобы отразить, что действительно необходимы миллиарды чисел, так что это может быть жизнеспособным, если предположить, что вы принимаете меры, чтобы не потерять выгоды из-за выравнивания структуры и заполнения, то есть путем сохранения что-то еще в оставшихся 24 битах или путем сохранения ваших 40-битных значений в структурах по 8 или их кратных).
Стоит сэкономить три байта в миллиард раз, так как для этого потребуется заметно меньше страниц памяти, что приведет к меньшему количеству ошибок в кеше и TLB, и, в первую очередь, к сбоям страниц (одна ошибка страницы весит десятки миллионов инструкций).
Хотя в приведенном выше фрагменте не используются оставшиеся 24 бита (он просто демонстрирует часть "использовать 40 бит"), необходимо сделать что-то похожее на следующее, чтобы действительно сделать этот подход полезным в смысле сохранения памяти - предполагается, что у вас действительно есть другие "полезные" данные, которые нужно вставить в дыры:
struct using_gaps
{
uint64_t var : 40;
uint64_t useful_uint16 : 16;
uint64_t char_or_bool : 8;
};
Размер структуры и выравнивание будут равны 64-битному целому числу, поэтому ничто не будет потрачено впустую, если вы создадите, например, массив из миллиарда таких структур (даже без использования специфичных для компилятора расширений). Если вы не используете 8-битное значение, вы также можете использовать 48-битное и 16-битное значение (что дает больший запас переполнения).
В качестве альтернативы вы можете, за счет удобства использования, поместить 8 40-битных значений в структуру (наименьшее общее кратное 40 и 64 - 320 = 8*40). Конечно, тогда ваш код, который обращается к элементам в массиве структур, станет намного сложнее (хотя, возможно, можно было бы реализовать operator[] это восстанавливает функциональность линейного массива и скрывает сложность структуры).
Обновить:
Написал набор быстрых тестов, просто чтобы посмотреть, какие издержки будут иметь битовые поля (и перегрузка операторов ссылками на битовые поля). Отправленный код (из-за длины) на http://gcc.godbolt.org/, тестовый вывод с моего компьютера с Win7-64:
Running test for array size = 1048576
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 2 1 35 35 1
uint64_t 0 3 3 35 35 1
bad40_t 0 5 3 35 35 1
packed40_t 0 7 4 48 49 1
Running test for array size = 16777216
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 38 14 560 555 8
uint64_t 0 81 22 565 554 17
bad40_t 0 85 25 565 561 16
packed40_t 0 151 75 765 774 16
Running test for array size = 134217728
what alloc seq(w) seq(r) rand(w) rand(r) free
-----------------------------------------------------------
uint32_t 0 312 100 4480 4441 65
uint64_t 0 648 172 4482 4490 130
bad40_t 0 682 193 4573 4492 130
packed40_t 0 1164 552 6181 6176 130
Что можно увидеть, так это то, что дополнительные издержки битовых полей пренебрежимо малы, но перегрузка оператора ссылками на битовые поля в качестве удобства довольно радикальна (увеличение примерно в 3 раза) при линейном доступе к данным в дружественном кешированию виде. С другой стороны, при произвольном доступе это даже не имеет значения.
Эти временные интервалы предполагают, что простое использование 64-разрядных целых чисел было бы лучше, поскольку они по-прежнему быстрее в целом, чем битовые поля (несмотря на касание большего объема памяти), но, конечно, они не учитывают стоимость ошибок страниц с гораздо большими наборами данных. Это может выглядеть совсем иначе, когда у вас кончится физическая память (я этого не проверял).
Вы можете довольно эффективно упаковать 4*40-битные целые числа в 160-битную структуру следующим образом:
struct Val4 {
char hi[4];
unsigned int low[4];
}
long getLong( const Val4 &pack, int ix ) {
int hi= pack.hi[ix]; // preserve sign into 32 bit
return long( (((unsigned long)hi) << 32) + (unsigned long)pack.low[i]);
}
void setLong( Val4 &pack, int ix, long val ) {
pack.low[ix]= (unsigned)val;
pack.hi[ix]= (char)(val>>32);
}
Их снова можно использовать так:
Val4[SIZE] vals;
long getLong( int ix ) {
return getLong( vals[ix>>2], ix&0x3 )
}
void setLong( int ix, long val ) {
setLong( vals[ix>>2], ix&0x3, val )
}
Возможно, вы захотите рассмотреть кодирование переменной длины (VLE)
Предположительно, вы храните множество этих номеров где-то (в оперативной памяти, на диске, отправляете их по сети и т. Д.), А затем берете их один за другим и выполняете некоторую обработку.
Одним из подходов будет их кодирование с использованием VLE. Из документации по протоколу Google (лицензия CreativeCommons)
Варианты - это метод сериализации целых чисел с использованием одного или нескольких байтов. Меньшие числа занимают меньшее количество байтов.
Каждый байт в varint, кроме последнего байта, имеет набор старших значащих бит (мсб) - это указывает на то, что есть еще байты. Младшие 7 битов каждого байта используются для хранения двоичного представления числа в группах по 7 битов, в первую очередь наименее значимой группы.
Так, например, вот номер 1 - это один байт, поэтому msb не установлен:
0000 0001А вот 300 - это немного сложнее:
1010 1100 0000 0010Как вы поняли, что это 300? Сначала вы отбрасываете msb для каждого байта, так как это просто для того, чтобы сообщить нам, достиг ли мы конца числа (как вы можете видеть, оно задается в первом байте, поскольку в varint больше одного байта)
Pros
- Если у вас много маленьких чисел, вы, вероятно, в среднем будете использовать менее 40 байт на целое число. Возможно, намного меньше.
- Вы можете хранить большие числа (с более чем 40 битами) в будущем, без необходимости платить штраф за маленькие
Cons
- Вы платите дополнительный бит за каждые 7 значащих бит ваших чисел. Это означает, что число с 40 значащими битами будет нуждаться в 6 байтах. Если большинство ваших чисел имеют 40 значащих битов, вам лучше использовать подход с битовыми полями.
- Вы потеряете возможность легко переходить к числу с учетом его индекса (вам нужно хотя бы частично проанализировать все предыдущие элементы в массиве, чтобы получить доступ к текущему.
- Вам понадобится некоторая форма декодирования, прежде чем делать что-либо полезное с числами (хотя это верно и для других подходов, таких как битовые поля)
(Правка: во-первых, то, что вы хотите, возможно, и имеет смысл в некоторых случаях; мне приходилось делать подобные вещи, когда я пытался сделать что-то для задачи Netflix, и у меня было только 1 ГБ памяти; во-вторых, это, вероятно, лучше использование массива char для 40-битного хранилища, чтобы избежать проблем с выравниванием и необходимости возиться с прагмами структурной упаковки; в-третьих, этот дизайн предполагает, что вы в порядке с 64-битной арифметикой для промежуточных результатов, это только для больших хранилище массивов, которое вы бы использовали Int40; в-четвертых: я не получаю всех предположений о том, что это плохая идея, просто прочитайте, что люди проходят, чтобы упаковать структуры данных меша, и это выглядит как детская игра для сравнения).
То, что вам нужно, это структура, которая используется только для хранения данных в виде 40-битных целых, но неявно преобразуется в int64_t для арифметики. Единственная хитрость заключается в правильном расширении знака с 40 до 64 бит. Если у вас все в порядке с беззнаковыми типами, код может быть еще проще. Это должно быть в состоянии начать вас.
#include <cstdint>
#include <iostream>
// Only intended for storage, automatically promotes to 64-bit for evaluation
struct Int40
{
Int40(int64_t x) { set(static_cast<uint64_t>(x)); } // implicit constructor
operator int64_t() const { return get(); } // implicit conversion to 64-bit
private:
void set(uint64_t x)
{
setb<0>(x); setb<1>(x); setb<2>(x); setb<3>(x); setb<4>(x);
};
int64_t get() const
{
return static_cast<int64_t>(getb<0>() | getb<1>() | getb<2>() | getb<3>() | getb<4>() | signx());
};
uint64_t signx() const
{
return (data[4] >> 7) * (uint64_t(((1 << 25) - 1)) << 39);
};
template <int idx> uint64_t getb() const
{
return static_cast<uint64_t>(data[idx]) << (8 * idx);
}
template <int idx> void setb(uint64_t x)
{
data[idx] = (x >> (8 * idx)) & 0xFF;
}
unsigned char data[5];
};
int main()
{
Int40 a = -1;
Int40 b = -2;
Int40 c = 1 << 16;
std::cout << "sizeof(Int40) = " << sizeof(Int40) << std::endl;
std::cout << a << "+" << b << "=" << (a+b) << std::endl;
std::cout << c << "*" << c << "=" << (c*c) << std::endl;
}
Вот ссылка, чтобы попробовать его вживую: http://rextester.com/QWKQU25252
Вы можете использовать структуру битового поля, но она не сэкономит вам память:
struct my_struct
{
unsigned long long a : 40;
unsigned long long b : 24;
};
Вы можете сжать любое кратное из 8 таких 40-битных переменных в одну структуру:
struct bits_16_16_8
{
unsigned short x : 16;
unsigned short y : 16;
unsigned short z : 8;
};
struct bits_8_16_16
{
unsigned short x : 8;
unsigned short y : 16;
unsigned short z : 16;
};
struct my_struct
{
struct bits_16_16_8 a1;
struct bits_8_16_16 a2;
struct bits_16_16_8 a3;
struct bits_8_16_16 a4;
struct bits_16_16_8 a5;
struct bits_8_16_16 a6;
struct bits_16_16_8 a7;
struct bits_8_16_16 a8;
};
Это сэкономит вам немного памяти (по сравнению с использованием 8 "стандартных" 64-битных переменных), но вам придется разделить каждую операцию (и особенно арифметические) с каждой из этих переменных на несколько операций.
Таким образом, оптимизация памяти будет "обменена" на производительность во время выполнения.
Как показывают комментарии, это довольно сложная задача.
Вероятно, ненужные хлопоты, если вы не хотите экономить много оперативной памяти - тогда это имеет гораздо больше смысла. (Экономия ОЗУ будет суммой битов, сохраненных на миллионах long значения хранятся в оперативной памяти)
Я хотел бы рассмотреть использование массива 5 байт / символ (5 * 8 бит = 40 бит). Тогда вам нужно будет сдвинуть биты с вашего (переполнен int - отсюда long) значение в массив байтов для их хранения.
Чтобы использовать значения, затем сдвиньте биты обратно в long и вы можете использовать значение.
Тогда ваше ОЗУ и хранилище файлов значения будут 40 бит (5 байт), НО вы должны рассмотреть выравнивание данных, если вы планируете использовать struct держать 5 байтов. Дайте мне знать, если вам нужна детальная информация о последствиях сдвига битов и выравнивания данных.
Точно так же вы можете использовать 64 бит longи скрыть другие значения (возможно, 3 символа) в оставшихся 24 битах, которые вы не хотите использовать. Опять же - использование битового сдвига для добавления и удаления 24-битных значений.
Если вам приходится иметь дело с миллиардами целых чисел, я бы попытался инкапсулировать массивы из 40-битных чисел вместо отдельных 40-битных чисел. Таким образом, вы можете протестировать различные реализации массива (например, реализацию, которая сжимает данные на лету, или, возможно, такую, которая хранит менее используемые данные на диске) без изменения остальной части вашего кода.
Вот пример реализации ( http://rextester.com/SVITH57679):
class Int64Array
{
char* buffer;
public:
static const int BYTE_PER_ITEM = 5;
Int64Array(size_t s)
{
buffer=(char*)malloc(s*BYTE_PER_ITEM);
}
~Int64Array()
{
free(buffer);
}
class Item
{
char* dataPtr;
public:
Item(char* dataPtr) : dataPtr(dataPtr){}
inline operator int64_t()
{
int64_t value=0;
memcpy(&value, dataPtr, BYTE_PER_ITEM); // Assumes little endian byte order!
return value;
}
inline Item& operator = (int64_t value)
{
memcpy(dataPtr, &value, BYTE_PER_ITEM); // Assumes little endian byte order!
return *this;
}
};
inline Item operator[](size_t index)
{
return Item(buffer+index*BYTE_PER_ITEM);
}
};
Обратите внимание memcpy-конверсия из 40-битного в 64-битный режим - в основном неопределенное поведение, так как предполагает буквально-порядковый порядок. Это должно работать на x86-платформах.
Примечание 2: Очевидно, что это код для проверки концепции, а не готовый к использованию код. Чтобы использовать его в реальных проектах, вы должны добавить (среди прочего):
- обработка ошибок (malloc может потерпеть неудачу!)
- конструктор копирования (например, путем копирования данных, добавления подсчета ссылок или создания приватного конструктора копирования)
- переместить конструктор
- постоянные перегрузки
- STL-совместимые итераторы
- проверки границ для индексов (в отладочной сборке)
- проверка диапазона значений (в отладочной сборке)
- утверждает для неявных предположений (little-endianness)
- Как это,
Itemимеет ссылочную семантику, а не семантику значения, что необычно дляoperator[]; Возможно, вы могли бы обойти это с некоторыми хитрыми приемами преобразования типов C++
Все это должно быть просто для программиста на C++, но они сделают пример кода намного длиннее, не делая его более понятным, поэтому я решил их опустить.
Еще один вариант, который может быть полезен, - это использовать структуру:
typedef struct TRIPLE_40 {
uint32_t low[3];
uint8_t hi[3];
uint8_t padding;
};
Такая структура заняла бы 16 байтов и, если выровнен по 16 байтов, полностью поместилась бы в одной строке кэша. Хотя определение того, какая из частей структуры для использования может быть более дорогим, чем это было бы, если бы структура содержала четыре элемента вместо трех, доступ к одной строке кэша может быть намного дешевле, чем доступ к двум. Если производительность важна, следует использовать некоторые тесты, поскольку некоторые машины могут дешево выполнять операцию divmod-3 и иметь высокую стоимость за выборку строки кэша, в то время как другие могут иметь более дешевый доступ к памяти и более дорогой divmod-3.
Я предполагаю, что
- это С, и
- вам нужен один большой массив из 40-битных чисел, и
- вы находитесь на машине с прямым порядком байтов, и
- ваша машина достаточно умна, чтобы справиться с выравниванием
- Вы определили размер, который будет количеством нужных вам 40-битных чисел
unsigned char hugearray[5*size+3]; // +3 avoids overfetch of last element
__int64 get_huge(unsigned index)
{
__int64 t;
t = *(__int64 *)(&hugearray[index*5]);
if (t & 0x0000008000000000LL)
t |= 0xffffff0000000000LL;
else
t &= 0x000000ffffffffffLL;
return t;
}
void set_huge(unsigned index, __int64 value)
{
unsigned char *p = &hugearray[index*5];
*(long *)p = value;
p[4] = (value >> 32);
}
Может быть быстрее справиться с двумя сменами.
__int64 get_huge(unsigned index)
{
return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24);
}
В случае хранения нескольких миллиардов 40-разрядных целых чисел со знаком и предположения о 8-разрядных байтах можно упаковать 8 40-разрядных целых чисел со знаком в структуре (в коде ниже для этого используется массив байтов), и, поскольку эта структура обычно выравнивается, вы можете создать логический массив таких упакованных групп и обеспечить обычную последовательную индексацию этого:
#include <limits.h> // CHAR_BIT
#include <stdint.h> // int64_t
#include <stdlib.h> // div, div_t, ptrdiff_t
#include <vector> // std::vector
#define STATIC_ASSERT( e ) static_assert( e, #e )
namespace cppx {
using Byte = unsigned char;
using Index = ptrdiff_t;
using Size = Index;
// For non-negative values:
auto roundup_div( const int64_t a, const int64_t b )
-> int64_t
{ return (a + b - 1)/b; }
} // namespace cppx
namespace int40 {
using cppx::Byte;
using cppx::Index;
using cppx::Size;
using cppx::roundup_div;
using std::vector;
STATIC_ASSERT( CHAR_BIT == 8 );
STATIC_ASSERT( sizeof( int64_t ) == 8 );
const int bits_per_value = 40;
const int bytes_per_value = bits_per_value/8;
struct Packed_values
{
enum{ n = sizeof( int64_t ) };
Byte bytes[n*bytes_per_value];
auto value( const int i ) const
-> int64_t
{
int64_t result = 0;
for( int j = bytes_per_value - 1; j >= 0; --j )
{
result = (result << 8) | bytes[i*bytes_per_value + j];
}
const int64_t first_negative = int64_t( 1 ) << (bits_per_value - 1);
if( result >= first_negative )
{
result = (int64_t( -1 ) << bits_per_value) | result;
}
return result;
}
void set_value( const int i, int64_t value )
{
for( int j = 0; j < bytes_per_value; ++j )
{
bytes[i*bytes_per_value + j] = value & 0xFF;
value >>= 8;
}
}
};
STATIC_ASSERT( sizeof( Packed_values ) == bytes_per_value*Packed_values::n );
class Packed_vector
{
private:
Size size_;
vector<Packed_values> data_;
public:
auto size() const -> Size { return size_; }
auto value( const Index i ) const
-> int64_t
{
const auto where = div( i, Packed_values::n );
return data_[where.quot].value( where.rem );
}
void set_value( const Index i, const int64_t value )
{
const auto where = div( i, Packed_values::n );
data_[where.quot].set_value( where.rem, value );
}
Packed_vector( const Size size )
: size_( size )
, data_( roundup_div( size, Packed_values::n ) )
{}
};
} // namespace int40
#include <iostream>
auto main() -> int
{
using namespace std;
cout << "Size of struct is " << sizeof( int40::Packed_values ) << endl;
int40::Packed_vector values( 25 );
for( int i = 0; i < values.size(); ++i )
{
values.set_value( i, i - 10 );
}
for( int i = 0; i < values.size(); ++i )
{
cout << values.value( i ) << " ";
}
cout << endl;
}
Здесь довольно много ответов, касающихся реализации, поэтому я бы хотел поговорить об архитектуре.
Обычно мы расширяем 32-битные значения до 64-битных, чтобы избежать переполнения, потому что наши архитектуры предназначены для обработки 64-битных значений.
Большинство архитектур предназначены для работы с целыми числами, размер которых равен степени 2, потому что это значительно упрощает аппаратное обеспечение. Такие задачи, как кэширование, намного проще: существует большое количество делений и операций с модулями, которые можно заменить на битовую маскировку и сдвиги, если вы придерживаетесь степеней 2.
В качестве примера того, насколько это важно, спецификация C++11 определяет случаи многопоточности в гонках на основе "областей памяти". Расположение памяти определено в 1.7.3:
Ячейка памяти является либо объектом скалярного типа, либо максимальной последовательностью смежных битовых полей, имеющих ненулевую ширину.
Другими словами, если вы используете битовые поля C++, вы должны тщательно выполнять всю вашу многопоточность. Два смежных битовых поля должны рассматриваться как одно и то же место в памяти, даже если вы хотите, чтобы вычисления между ними могли быть распределены по нескольким потокам. Это очень необычно для C++, поэтому может вызвать разочарование разработчика, если вам придется беспокоиться об этом.
Большинство процессоров имеют архитектуру памяти, которая извлекает 32-битные или 64-битные блоки памяти одновременно. Таким образом, использование 40-битных значений будет иметь удивительное количество дополнительных обращений к памяти, что значительно повлияет на время выполнения. Рассмотрим вопросы выравнивания:
40-bit word to access: 32-bit accesses 64bit-accesses
word 0: [0,40) 2 1
word 1: [40,80) 2 2
word 2: [80,120) 2 2
word 3: [120,160) 2 2
word 4: [160,200) 2 2
word 5: [200,240) 2 2
word 6: [240,280) 2 2
word 7: [280,320) 2 1
В 64-битной архитектуре одно из каждых четырех слов будет "нормальной скоростью". Остальное потребует получить вдвое больше данных. Если вы получите много кеша, это может снизить производительность. Даже если вы получите попадания в кэш, вам придется распаковать данные и упаковать их в 64-битный регистр, чтобы использовать их (что может даже привести к затруднению предсказания ветвления).
Вполне возможно, что это стоит затрат
Есть ситуации, когда эти штрафы являются приемлемыми. Если у вас есть большой объем резидентных данных, которые хорошо проиндексированы, вы можете найти экономию памяти за счет потери производительности. Если вы выполняете большое количество вычислений для каждого значения, вы можете обнаружить, что затраты минимальны. Если это так, не стесняйтесь реализовать одно из вышеуказанных решений. Однако вот несколько рекомендаций.
- Не используйте битовые поля, если вы не готовы оплатить их стоимость. Например, если у вас есть массив битовых полей, и вы хотите разделить его для обработки по нескольким потокам, вы застряли. По правилам C++11 все битовые поля образуют одну ячейку памяти, поэтому доступ к ним может получить только один поток за раз (это связано с тем, что метод упаковки битовых полей определяется реализацией, поэтому C++11 не может помочь вам распространять их не определенным для реализации способом)
- Не используйте структуру, содержащую 32-разрядное целое число и символ для получения 40 байтов. Большинство процессоров будут выполнять выравнивание, и вы не сохраните ни одного байта.
- Используйте однородные структуры данных, такие как массив символов или массив 64-битных целых чисел. Гораздо проще получить правильное выравнивание. (И вы также сохраняете контроль над упаковкой, что означает, что вы можете разделить массив между несколькими потоками для вычисления, если вы будете осторожны)
- Разрабатывайте отдельные решения для 32-разрядных и 64-разрядных процессоров, если вам необходимо поддерживать обе платформы. Поскольку вы делаете что-то очень низкоуровневое и очень плохо поддерживаемое, вам нужно будет индивидуально адаптировать каждый алгоритм к его архитектуре памяти.
- Помните, что умножение 40-разрядных чисел отличается от умножения 64-разрядных расширений 40-разрядных чисел, уменьшенных до 40-разрядных. Как и в случае с FPU x87, вы должны помнить, что распределение ваших данных между размерами битов меняет ваш результат.
Это требует потокового сжатия в памяти без потерь. Если это для приложений с большими данными, то уловки с плотной упаковкой в лучшем случае являются тактическими решениями для того, что, по-видимому, требует довольно приличного промежуточного программного обеспечения или поддержки на уровне системы. Им нужно было провести тщательное тестирование, чтобы убедиться, что можно восстановить все биты целыми и невредимыми. А последствия для производительности весьма нетривиальны и сильно зависят от аппаратного обеспечения из-за вмешательства в архитектуру кэширования процессора (например, строки кэша или структура упаковки). Кто-то упомянул сложные структуры сетки: они часто настраиваются для взаимодействия с конкретными архитектурами кэширования.
Из требований не ясно, нужен ли OP произвольный доступ. Принимая во внимание размер данных, более вероятно, что для локального произвольного доступа потребуется только относительно небольшой фрагмент, организованный иерархически для поиска. Даже аппаратное обеспечение делает это при больших размерах памяти (NUMA). Как показывают форматы фильмов без потерь, должна быть возможность получить произвольный доступ в виде кусков ("кадров") без необходимости загрузки всего набора данных в горячую память (из сжатого резервного хранилища в памяти).
Я знаю одну быструю систему баз данных (имя kdb от KX Systems, но я знаю, что есть и другие), которая может обрабатывать очень большие наборы данных, казалось бы, отображая в памяти большие наборы данных из резервного хранилища. Он имеет возможность прозрачного сжатия и расширения данных на лету.
Да, вы можете сделать это, и это сэкономит место для большого количества чисел
Вам нужен класс, который содержит std::vector целого типа без знака.
Вам понадобятся функции-члены для хранения и извлечения целого числа. Например, если вы хотите сохранить 64 целых числа по 40 бит каждый, используйте вектор из 40 целых чисел по 64 бита каждый. Затем вам нужен метод, который хранит целое число с индексом в [0,64] и метод для получения такого целого числа.
Эти методы будут выполнять некоторые операции сдвига, а также некоторые двоичные | а также & .
Я не добавляю здесь больше подробностей, потому что ваш вопрос не очень конкретен. Вы знаете, сколько целых чисел вы хотите хранить? Вы знаете это во время компиляции? Знаете ли вы, когда программа запускается? Как должны быть организованы целые числа? Как массив? Понравилась карта? Вы должны знать все это, прежде чем пытаться сжать целые числа в меньшем объеме памяти.
Если вам действительно нужен массив из 40-битных целых чисел (чего, очевидно, у вас нет), я бы просто объединил один массив из 32-битных и один массив из 8-битных целых.
Чтобы прочитать значение x по индексу i:
uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];
Чтобы записать значение x в индекс i:
array8 [i] = x >> 32; array32 [i] = x;
Очевидно, что он хорошо инкапсулирован в класс с использованием встроенных функций для максимальной скорости.
Существует одна ситуация, когда это является неоптимальным, и это когда вы делаете действительно произвольный доступ ко многим элементам, так что каждый доступ к массиву int будет пропуском кеша - здесь вы будете получать два кеша каждый раз. Чтобы избежать этого, определите 32-байтовую структуру, содержащую массив из шести uint32_t, массив из шести uint8_t и два неиспользуемых байта (41 2/3-го бита на число); код для доступа к элементу немного сложнее, но оба компонента элемента находятся в одной строке кэша.