问题标签 [bitarray]

我已经使用新手手册中的位数组做了一个示例。我想知道它们可以用来做什么以及它们有哪些常见的数据结构（假设“数组”是相当松散的术语。）

谢谢。

我正在使用 Dipperstein 的 bitarray.cpp 类来处理双层（黑白）图像，其中图像数据本身存储为一个像素一位。

我需要遍历每一位，每张图像大约 4--9 兆像素，超过数百张图像，使用 for 循环，例如：

性能是可用的，但并不惊人。我通过 gprof 运行程序，发现有大量时间和数百万次调用std::vector迭代器和开始等方法。这是顶部采样的函数：

我对 C++ 的 STL 不是很熟悉，但是谁能解释为什么 std::vector::begin() 被调用了几百万次？而且，当然，我是否可以做些什么来加快速度？

编辑：我只是放弃并优化了搜索功能（循环）。

我的 c 代码中有几个 uint8_t 数组，我想比较一个任意序列位。例如，我有 bitarray_1 和 bitarray_2，我想将 bitarray_1 的第 13-47 位与 bitarray_2 的第 5-39 位进行比较。最有效的方法是什么？

目前这是我程序中的一个巨大瓶颈，因为我只有一个简单的实现，它将位复制到一个新的临时数组的开头，然后在它们上使用 memcmp。

我正在寻找一种在 Java 中存储密集可变长度位数组的非常紧凑的方法。现在，我正在使用，但对于大小为nBitSet的位向量，它似乎平均使用1.5*n 位的存储空间。通常，这不是问题，但在这种情况下，存储的位数组是应用程序内存占用的重要部分。所以，让它们变小一点真的很有帮助。

BitSet 所需的空间似乎是由于用于支持数据结构的 long 数组在每次扩展以容纳更多位时往往会翻倍：

我可以编写自己的 BitSet 替代实现，更保守地扩展后端数据结构。但是，如果我不需要的话，我真的很讨厌复制标准类库中已经存在的功能。

在我目前正在处理的一项作业中，我们需要使用位向量，但我非常不确定如何在 Python 中执行此操作。它们应该能够从 4 位到 20 位。我以前从未使用过位向量，但我想有人会创建您使用通常的 AND/OR/XOR 操作操作的无符号字节数组。

这里的重要限制是：除了标准 Python 提供的库之外，我不能依赖任何库。

我想我知道如何在 C 中使用 8 位无符号字节的数组来执行此操作：例如，要将零数组的第 18 位变为 1，我会执行类似 my_bit_array[3] &= 1<<2

但是由于 Python 是动态类型的并且没有内置的数组类型，我将如何以 Python 的方式执行此操作？

是否有可能（如何？）表达一个大小为 20 的位向量？我正在考虑制作一个 24 位/3 字节向量并忽略 4 位。

我需要的东西比System.Collections.BitArray我的应用程序中的类多一点。具体来说，我需要位数组：

• 不可变
• 使用值语义实现相等

我创建了自己的struct，很大程度上复制了BitArray实现的内部结构。（谢谢，.Net 反射器！）

我不是每天都处理按位运算，所以我对我的等式实现没有最高程度的信心。（它通过了我要进行的单元测试，但我可能会遗漏边缘情况。）我提出的解决方案如下所示。对于可能更正确或更有效的事情，我将不胜感激其他人的反馈和答案。

就像 CLR 一样BitArray，length字段是指结构中的位数，array字段（或Array属性）是指表示位的 32 位整数数组。

[澄清]我选择在我的构造函数和其他方法中采用简单的方法，这样我就不能依赖不必要的位为零。例如，

• Not()~由整数数组元素的按位否定 ( ) 实现。
• 可以使用一个构造函数，它需要一个长度和布尔值来初始化所有位。如果初始化值为真，我将 int 数组的所有元素设置为 -1（在二进制补码中，由全 1 表示）
• 等等。

因此，我需要在比较中处理（或者更确切地说，忽略）它们。一个好的解决方案也是始终将这些位保持为零，但在我的情况下，这将导致更多的工作（对于计算机和我来说！）

我有一个需要序列化为 xml 的业务类。它有一个 BitArray 属性。

我用它装饰了它，[XmlAttribute]但序列化失败了

要实现 XML 可序列化，从 ICollection 继承的类型必须在其继承层次结构的所有级别上都有 Add(System.Boolean) 的实现。System.Collections.BitArray 没有实现 Add(System.Boolean)。

我不确定是否可以序列化为 xml？

如果不是什么将是序列化 BitArray 的有效方法

感谢您的关注

我想创建一个非常大的数组，在上面写 '0' 和 '1'。我正在尝试模拟一种称为随机顺序吸附的物理过程，其中长度为 2 的单位（二聚体）被沉积在随机位置的 n 维晶格上，而不会相互重叠。当晶格上没有更多空间用于沉积更多二聚体（晶格被堵塞）时，该过程停止。

最初，我从零格开始，二聚体由一对“1”表示。随着每个二聚体的沉积，二聚体左侧的位点被阻塞，因为二聚体不能重叠。所以我通过在格子上放置三个'1'来模拟这个过程。我需要多次重复整个模拟，然后计算出平均覆盖率。

我已经使用 1D 和 2D 晶格的字符数组完成了这项工作。目前，在处理 3D 问题和更复杂的概括之前，我正在尝试使代码尽可能高效。

这基本上是代码在一维中的样子，简化：

对于我正在做的实际项目，它不仅涉及二聚体，还涉及三聚体、四聚体以及各种形状和大小（用于 2D 和 3D）。

我希望我能够使用单个位而不是字节，但我一直在阅读，据我所知，你一次只能更改 1 个字节，所以要么我需要做一些复杂的索引或者有更简单的方法吗？

感谢您的回答

就像标题所说，我试图找到存在于大型常量数组 N 中的 M 的元素。大多数时候，N 中不会存在 M 的元素，所以对 M 进行的绝大多数搜索都是浪费时间。

我正在寻找某种方法来创建索引以在对 M 进行全面搜索之前进行检查。类似于我的项目从 M 的每个元素的前几个字节创建一个位数组，据我所知，利用位级并行性以快速搜索它。我不完全理解这是如何工作的。

那么我可以使用什么技巧来减少不必要地搜索 M 的机会呢？

这是一个主要与语言无关的问题，但为了尽可能完整，我使用的是 C++。

我需要在 GetHashCode 中为 BitArray 生成一个快速哈希码。我有一个字典，其中的键是 BitArrays，并且所有 BitArrays 的长度都相同。

有没有人知道一种从可变位数生成良好哈希的快速方法，就像在这种情况下一样？

更新：

我最初采用的方法是直接通过反射访问内部整数数组（在这种情况下，速度比封装更重要），然后对这些值进行异或。XOR 方法似乎运作良好，即在 Dictionary 中搜索时不会过度调用我的“Equals”方法：

然而，Mark Byers 建议并在 StackOverflow 其他地方看到的方法稍微好一些（16570 Equals 调用 vs 16608 用于我的测试数据的 XOR）。请注意，这种方法修复了前一种方法中的一个错误，即位数组末尾之外的位可能会影响哈希值。如果位数组的长度减少，就会发生这种情况。

GetInternalValues 扩展方法是这样实现的：

欢迎任何改进建议！