如果32位整数溢出，我们可以使用40位结构而不是64位长结构吗？
如果一个32位的整数溢出，而不是将int升级为long ，那么如果我们只需要一个范围在2 40内，就可以使用一些40位的types，这样我们就可以节约24（64-40）位为每个整数？
如果是这样，怎么样？
我必须处理数十亿的空间是一个更大的约束。
对，但是…
这当然是可能的 ，但它通常是荒谬的（对于任何不使用数十亿这些数字的程序）：
#include <stdint.h> // don't want to rely on something like long long struct bad_idea { uint64_t var : 40; };
在这里， var确实会有40位的宽度，代价是生成的代码效率低得多 （事实certificate“很多”是非常错误的 – 测量的开销只有1-2％，见下面的时间表），通常无济于事。 除非你需要另外一个24位的数值（或8位和16位的数值），你可以将它们打包到同一个结构中，否则alignment将会失去你可能获得的任何东西。
在任何情况下，除非有数十亿个这样的内存消耗，否则内存消耗的有效差异将不明显（但是需要额外的代码来pipe理位域）。
注意：
同时这个问题已经被更新，以反映出确实需要数十亿的数字，所以这可能是一个可行的事情，假定你采取措施不要因为结构调整和填充而损失收益，即通过存储剩下的24位还有其他的东西，或者通过将你的40位值存储在8位或8位的结构中）。
节省三个字节十亿次是值得的，因为它将需要显着较less的内存页面，从而导致更less的高速caching和TLB未命中，尤其是页面错误（单页错误加权数千万条指令）。
虽然上面的代码片段没有使用其余的24位（它只是演示了“使用40位”的部分），但是类似于以下的内容将是真正使得该方法在保存内存的意义上是有用的 – 推测你确实有其他“有用”的数据来填补空白：
struct using_gaps { uint64_t var : 40; uint64_t useful_uint16 : 16; uint64_t char_or_bool : 8; };
结构大小和alignment将等于一个64位的整数，所以如果你制作了一个十亿个这样的结构的数组（甚至不使用编译器特定的扩展），没有什么是浪费的。 如果您没有使用8位值，则也可以使用48位和16位值（提供更大的溢出裕度）。
或者，你可以牺牲可用性，把8个40位值放入一个结构中（40和64的最小公倍数是320 = 8 * 40）。 当然，访问结构数组中的元素的代码将变得复杂得多（尽pipe可能会实现一个operator[]来恢复线性数组的function并隐藏结构的复杂性）。
更新：
写了一个快速testing套件，只是为了看看位域（和位域refs操作符重载）会有什么开销。 在gcc.godbolt.org发布的代码（由于长度），从我的Win7-64机器testing输出是：
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
我们可以看到，位域的额外开销是可忽略的，但是当以caching容易的方式线性访问数据时，使用位域引用的操作符重载作为一个方便的事情是相当激烈的（大约增加3倍）。 另一方面，随机访问几乎没有关系。
这些时间表明，简单地使用64位整数会更好，因为它们总体上比位域更快（尽pipe触及更多的内存），但是当然，它们没有考虑具有更大数据集的页面错误代价。 一旦你用完物理内存，它可能会看起来非常不同（我没有testing过）。
我猜你可以相当有效地包装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）
据推测，你已经存储了很多这些数字（在RAM中，在磁盘上，通过networking发送他们等），然后一个接一个地做一些处理。
一种方法是使用VLE 对它们进行编码 。 从Google的protobuf 文档 （CreativeCommons许可证）
Varints是一个使用一个或多个字节序列化整数的方法。 较小的数字需要较less的字节数。
varint中的每个字节（除了最后一个字节）都设置了最高有效位（msb） – 这表示还有更多的字节可用。 每个字节的低7位用于以7位组的forms存储数字的二进制补码表示，最低有效组首位。
所以，例如，这里是数字1 – 这是一个单字节，所以没有设置msb：
0000 0001这里是300 – 这有点复杂：
1010 1100 0000 0010你怎么知道这是300？ 首先从每个字节中删除msb，因为这只是告诉我们是否已经达到了数字的末尾（因为varint中有多个字节，所以它被设置在第一个字节中）
优点
- 如果你有很多小数字，平均每个整数可能less于40个字节。 可能less得多。
- 您将来可以存储更多的数据（超过40位），而不必为小数据支付罚款
缺点
- 您为数字中的每7个有效位额外支付一点。 这意味着一个有40个有效位的数字将需要6个字节。 如果你的大部分数字有40个有效位，你最好用一个位域方法。
- 您将失去轻松跳转到索引号的能力（您必须至less部分parsing数组中的所有元素才能访问当前的元素。
- 在对数字进行任何有用的操作之前，您将需要某种forms的解码（尽pipe其他方法也是如此，比如位域）
（编辑：首先 – 你想要什么是可能的，在某些情况下是有意义的;当我试图为Netflix挑战做一些事情时，我不得不做类似的事情，只有1GB的内存;其次 – 这可能是最好的为40位存储使用char数组来避免任何alignment问题，并且需要混乱使用struct packing pragmas;第三，这种devise假定你可以使用64位算术获得中间结果，但这只适用于大型数组存储，你可以使用Int40;第四：我没有得到所有的build议，这是一个坏主意，只是看看人们通过什么来打包网格数据结构，这看起来像孩子的比赛）。
你想要的是一个结构，只用于存储数据为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位variables的任何倍数压缩成一个结构：
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位variables相比），但是您必须将每个variables的每个操作（特别是算术操作）分成几个操作。
所以内存优化将被“交易”，以实现运行时性能。
正如评论所言，这是一项相当艰巨的任务。
除非你想节省大量的RAM， 否则可能是一个不必要的麻烦 – 那么它就更有意义了。 （RAM存储将是存储在RAM中的数百万long值中保存的位的总和）
我会考虑使用一个5字节/字符的数组（5 * 8位= 40位）。 那么你将需要将你的（溢出int – 因此很long ）值的位移到字节数组来存储它们。
要使用这些值，然后将这些位移回一long ，然后可以使用该值。
然后你的RAM和文件存储的值将是40位（5字节），但是你必须考虑数据alignment，如果你打算使用一个struct来保存5个字节。 如果您需要详细阐述这种位移和数据alignment的问题，请告诉我。
同样，你可以使用64位long ，并隐藏其他值（3字符也许）在你不想使用的剩余24位。 再次 – 使用位移添加和删除24位值。
我会假设的
- 这是C，和
- 你需要一个单一的40位数的大数组
- 你在一台小端机器上
- 你的机器足够聪明来处理alignment
- 您已将大小定义为您需要的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); }
两class倒可能会更快。
__int64 get_huge(unsigned index) { return (((*(__int64 *)(&hugearray[index*5])) << 24) >> 24); }
另一个可能有用的变化是使用一个结构：
typedef struct TRIPLE_40 { uint32_t low[3]; uint8_t hi[3]; uint8_t padding; };
这样的结构将占用16个字节，并且如果16字节alignment，则完全适合于单个高速caching行内。 虽然识别结构的哪一部分使用可能比如果结构保持四个元件而不是三个要更昂贵，但访问一个caching线可能比访问两个要便宜得多。 如果性能很重要，那么应该使用一些基准testing，因为有些机器可以低成本地执行一次divmod-3操作，并且每次获取高速caching的成本很高，而另外一些则可能有更便宜的内存访问和更昂贵的divmod-3。
对于存储数十亿个40位有符号整数的情况，假设8位字节，可以将8个40位有符号整数打包到一个结构体中（在下面的代码中使用一个字节数组来执行此操作）因为这个结构通常是alignment的，你可以创build一个这样的压缩组的逻辑数组，并提供普通的顺序索引：
#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; }
如果你必须处理数十亿整数，我会尝试填充40位数字而不是单个 40位数字的数组。 这样，您可以testing不同的数组实现（例如，即时压缩数据的实现，也可能是将less量使用的数据存储到磁盘的实现），而无需更改代码的其余部分。
以下是一个示例实现（ 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); } };
注意：从40位到64位的memcpy转换基本上是未定义的行为，因为它假设为litian-endianness。 不过，它应该在x86平台上工作。
注2：显然，这是概念certificate代码，而不是生产就绪代码。 要在真实项目中使用它，您必须添加（除其他外）：
- error handling（malloc可能失败！）
- 复制构造函数（例如通过复制数据，添加引用计数或使复制构造函数保持私有状态）
- 移动构造函数
- const重载
- STL兼容的迭代器
- 边界检查索引（在debugging版本中）
- 范围检查值（在debugging版本中）
- 主张隐含的假设（小端）
- 实际上，
Item具有引用语义，而不是值语义，这对operator[]是不寻常的。 你可以用一些聪明的C ++types转换技巧来解决这个问题
所有这些对于一个C ++程序员来说都应该是简单的，但是他们会让示例代码更长，而不是更清楚，所以我决定省略它们。
是的，你可以做到这一点，这将为大量的数字节省一些空间
您需要一个包含无符号整数types的std :: vector的类。
您将需要成员函数来存储和检索一个整数。 例如，如果要存储每个40位的64个整数，则使用每个64位的整数40个向量。 然后你需要一个方法来存储一个索引在[0,64]的整数和一个方法来检索这样一个整数。
这些方法将执行一些移位操作，还有一些二进制| 和＆。
我不在这里添加更多的细节，因为你的问题不是很具体。 你知道你想存储多less个整数吗？ 你在编译期间知道吗？ 程序启动时你知道吗？ 整数应该如何组织？ 像一个数组？ 像地图一样？ 在尝试将整数减less到更less的存储之前，你应该知道所有这些。
如果你真正想要的是一个40位整数（显然你不能），我只是将一个32位数组和一个8位整数数组合在一起。
要读取索引i处的值x：
uint64_t x = (((uint64_t) array8 [i]) << 32) + array32 [i];
要写一个x来索引i：
array8 [i] = x >> 32; array32 [i] = x;
显然很好地封装到一个类，使用内联函数来获得最大的速度。
有一种情况，这是不理想的，那就是当你真正的随机访问多个项目时，每次访问一个int数组都将是一个caching未命中 – 在这里你每次都会得到两个caching未命中。 为了避免这种情况，定义一个32字节的结构，其中包含一个由6个uint32_t组成的数组，一个由6个uint8_t组成的数组，以及两个未使用的字节（每个数字为41 2/3比特）。 访问项目的代码稍微复杂一些，但是项目的两个组件都在同一个caching行中。
这里有很多关于实现的答案，所以我想谈谈架构。
我们通常将32位值扩展为64位值，以避免溢出，因为我们的架构旨在处理64位值。
大多数体系结构被devise为使用大小为2的整数，因为这使得硬件变得非常简单。 如caching这样的任务是这样简单得多：有大量的分割和模数操作，如果你坚持2的幂，可以用位掩码和位移来代替。
作为一个例子，C ++ 11规范定义了基于“内存位置”的multithreading竞争情况。 内存位置在1.7.3中定义：
存储器位置是标量types的对象或者具有非零宽度的相邻位域的最大序列。
换句话说，如果你使用C ++的位域，你必须仔细地完成你所有的multithreading。 两个相邻的位域必须被视为相同的存储位置，即使你希望跨越它们的计算可以分布在多个线程中。 对于C ++来说，这是非常不寻常的，所以如果你不必担心的话，可能会使开发人员感到沮丧。
大多数处理器具有一次获取32位或64位内存块的存储器架构。 因此，使用40位值将会产生令人惊讶的额外内存访问次数，极大地影响运行时间。 考虑alignment问题：
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位架构中，每四个字中就有一个是“正常速度”。 其余的将需要获取两倍的数据。 如果你得到很多的caching未命中，这可能会破坏性能。 即使你得到caching命中，你也必须解压缩数据并将其重新打包到一个64位的寄存器中去使用它（这甚至可能涉及一个难以预料的分支）。
这是完全可能的，这是值得的成本
有些情况下这些处罚是可以接受的。 如果你有大量的内存驻留数据被很好地索引，你可能会发现内存节省值得的性能损失。 如果您对每个值进行大量计算，则可能会发现成本很低。 如果是这样，请随时实施上述解决scheme之一。 但是，这里有一些build议。
- 除非您准备好支付成本，否则不要使用位域。 例如，如果你有一个位域的数组，并且希望把它分成多个线程进行处理，那么你就卡住了。 按照C ++ 11的规则，位域都构成一个内存位置，所以一次只能被一个线程访问（这是因为封装位域的方法是实现定义的，所以C ++ 11不能help you distribute them in a non-implementation defined manner)
- Do not use a structure containing a 32-bit integer and a char to make 40 bytes. Most processors will enforce alignment and you wont save a single byte.
- Do use homogenous data structures, such as an array of chars or array of 64-bit integers. It is far easier to get the alignment correct. (And you also retain control of the packing, which means you can divide an array up amongst several threads for computation if you are careful)
- Do design separate solutions for 32-bit and 64-bit processors, if you have to support both platforms. Because you are doing something very low level and very ill-supported, you'll need to custom tailor each algorithm to its memory architecture.
- Do remember that multiplication of 40-bit numbers is different from multiplication of 64-bit expansions of 40-bit numbers reduced back to 40-bits. Just like when dealing with the x87 FPU, you have to remember that marshalling your data between bit-sizes changes your result.
This begs for streaming in-memory lossless compression. If this is for a Big Data application, dense packing tricks are tactical solutions at best for what seems to require fairly decent middleware or system-level support. They'd need thorough testing to make sure one is able to recover all the bits unharmed. And the performance implications are highly non-trivial and very hardware-dependent because of interference with the CPU caching architecture (eg cache lines vs packing structure). Someone mentioned complex meshing structures : these are often fine-tuned to cooperate with particular caching architectures.
It's not clear from the requirements whether the OP needs random access. Given the size of the data it's more likely one would only need local random access on relatively small chunks, organised hierarchically for retrieval. Even the hardware does this at large memory sizes (NUMA). Like lossless movie formats show, it should be possible to get random access in chunks ('frames') without having to load the whole dataset into hot memory (from the compressed in-memory backing store).
I know of one fast database system (kdb from KX Systems to name one but I know there are others) that can handle extremely large datasets by seemlessly memory-mapping large datasets from backing store. It has the option to transparently compress and expand the data on-the-fly.
