实现一个非常有效的位结构

Question

我正在为以下问题寻找伪代码或 java 或 js 的解决方案：我们需要实现一个有效的位结构来保存 N 位的数据（您也可以将这些位视为布尔值，开/关）。我们需要支持以下方法： init(n) get(index) set(index, True/False) setAll(True/false)现在我得到了一个包含 o(1) 的解决方案，除了 init 是 o(n)。这个想法是创建一个数组，其中每个索引都保存一点值。为了支持 setAll，我还将使用位 vapue 保存时间戳，以了解是从 tge 数组中获取值还是从 tge 最后一个 setAll 值中获取值。init 中的 o(n) 是因为我们需要遍历数组来将它清零，否则它会产生垃圾，可以是任何东西。现在我被要求找到一个 init 也是 o(1) 的解决方案（我们可以创建一个数组，但我们不能清除垃圾，垃圾甚至可能看起来像有效的数据，这是错误的并使解决方案变得糟糕，我们需要100% 有效的解决方案）。更新：这是一个算法问题，而不是特定于语言的问题。我在面试问题中遇到过。由于内存限制，使用整数来表示位数组也不够好。我被告知它与对数组中的垃圾数据进行某种智能处理有关，而无需在 init 中对其进行处理，使用某种机制不落下，因为如果数组中的垃圾数据（但我不是确定如何）。

Answer 1

使用 32 位值（8、16、64 个整数也适用）作为存储和辅助字段，基于 hashmap制作惰性数据结构（而 hashmap 有时可能比 o(1) 的访问时间更短）InitFlag

要清除所有内容，请制作空地图InitFlag = 0 （删除旧地图是 GC 在 Java 中的工作，不是吗？）

要设置所有，请制作空地图 InitFlag = 1

更改某个位时，检查是否bitnum/32存在对应的 int 键。如果是，只需更改bitnum&32位，如果不是，则位值不同于InitFlag- 创建具有基于InitFlag（全零或全一）的值的键并更改所需的位。

在检索某个位时，检查是否存在对应的密钥。如果是，则提取位，如果不是 - 获取InitFlag值

SetAll(0):   ifl = 0, map - {}

SetBit(35):   ifl = 0, map - {1 : 0x10}

SetBit(32):   ifl = 0, map - {1 : 0x12}

ClearBit(32):   ifl = 0, map - {1 : 0x10}

ClearBit(1):   do nothing, ifl = 0, map - {1 : 0x10}

GetBit(1):     key=0 doesn't exist,  return ifl=0

GetBit(35):     key=1 exists,  return map[1]>>3 =1

SetAll(1):      ifl = 1, map = {}

SetBit(35):     do nothing

ClearBit(35):   ifl = 1, map - {1 : 0xFFFFFFF7 = 0b...11110111}

and so on

Answer 2

如果这是大学/高中计算机科学测试或家庭作业问题 - 我怀疑他们试图让您使用BOOLEAN BIT-WISE LOGIC - 具体来说，将位保存在 int 或 long 中。我怀疑（但我不是读心者——我可能是错的！）使用“数组”正是你的老师希望你避免的。

例如 - 这句话是从谷歌的搜索结果中复制的：

长：将长的数据类型是一个64位的二的补码整数。有符号 long 的最小值为 -263，最大值为 263-1。在 Java SE 8 及更高版本中，您可以使用 long 数据类型来表示无符号的 64 位 long，其最小值为 0，最大值为 264-1

这意味着 Java 中的单个 long 变量可以存储 64 个按位值：

long storage;

// To get the first bit-value, use logical-or ('|') and get the bit.

boolean result1 = (boolean) storage | 0b00000001; // Gets the first bit in 'storage'

boolean result2 = (boolean) storage | 0b00000010; // Gets the second

boolean result3 = (boolean) storage | 0b00000100; // Gets the third

...

boolean result8 = (boolean) storage | 0b10000000; // Gets the eighth result.

我可以为您编写整个内容，但我不能 100% 确定您的实际规格 - 如果您使用 long，则只能存储 64 个单独的二进制值。如果您想要任意数量的值，则必须根据需要使用尽可能多的“长”。

这是关于二进制/布尔值的 SO 帖子： Java 中的二进制表示

这是一篇关于位移位的 SO 帖子： Java - Circular shift using bitwise operations

同样，这将是一份工作，我不会编写整个项目。但是，get(int index)和set(int index, boolean val)方法将涉及数字 1 的逐位移位。

int pos = 1;

pos = pos << 5;  // This would function as a 'pointer' to the fifth element of the binary number list.

storage | pos;  // This retrieves the value stored as position 5.