algorithm - 在小内存(小于 50 MB)中存储大量二进制数的最佳方法是什么

Question

例如，我需要存储 1,000,000 个(或更多数量级)二进制数。我有不到 50 MB。 boolean类型数组如何占位？

我首先尝试使用整数数组来实现，但它需要大量内存，这在例如程序中是 Not Acceptable 。嵌入式设备。

我是否也可以使用二进制形式的整数来表示 8 位二进制数字，这样可以减少整数的数量(虽然只有 8 倍)？

Answer 1

如果你的数字受 MAX 限制，你可以在每个字节中存储 8 个 bool 值，使用 Ceil(MAX/8) 字节

Set Nth bit in array:
ByteArr[N div 8] = ByteArr[N div 8] OR (1 << (N mod 8))
Clear Nth bit in array:
ByteArr[N div 8] = ByteArr[N div 8] AND !(1 << (N mod 8))
Get Nth bit:
BoolResult = 0 <> (ByteArr[N div 8] AND (1 << (N mod 8)))