问题标签 [bitarray]

我正在尝试集成两个处理图像的系统。一个系统以 sbyte[] 的形式提供图像，而另一个系统使用 BitArray。我需要从sbyte[]获取数据并将其转换为 BitArray。有人知道怎么做吗？

谢谢，保罗

在 VB.NET 中从一个字节存储 4 位的最佳方法是什么？最好的意思是：

• 从 Byte 类型存储最直接的方法。
• 在执行按位运算时最容易使用。
• 将位直接转换为其他类型。

通过其构造函数将它们存储在 BitArray 中会反转位的顺序。这意味着尝试获取第一位的值将需要在 BitArray 的最后一个条目中查找该值。将它们存储在布尔数组中不会提供从字节转换的直接方法，并且会阻碍转换为其他类型。

过去我不得不这样做很多次，但我从未对结果感到满意。

任何人都可以建议一种将连续位数组从源复制到目标的快速方法，其中源和目标可能不会在方便的处理器边界上对齐（右移）？

如果源和目标都未对齐，则问题可以迅速转变为只有其中一个未对齐的问题（在第一个副本之后）。

作为一个起点，我的代码不可避免地最终看起来像下面这样（未经测试，忽略副作用，这只是一个即兴的例子）：

（其实这个比我之前做的好。看起来还不错）

我有一个 System.Collections.BitArray 数组（约 3000 个项目），我想将所有位向左移动 1。但是该集合似乎不支持该操作（即 bitArray << 1 不工作并且在那里是没有方法）。关于如何做到这一点的任何想法？

谢谢！

iOS / Objective-C：我有大量的布尔值。

这是存储这些值的一种低效方式——当只需要一个时，每个元素至少使用八位。

我该如何优化？

我们的操作系统教授提到，为了将进程 id 分配给新进程，内核在一个大小等于最大进程数（默认为 ~32,768）的数组中增量搜索第一个零位，其中分配的进程 id 为 1存储在其中。

据我所知，C 中没有位数据类型。显然，我在这里缺少一些东西。

有没有这样的特殊结构可以用来构建位数组？这究竟是如何完成的？

更重要的是，在这样的数组上可以执行哪些操作？

在一个涉及 Active Directory 的项目中，我一直在使用 System.DirectoryServices。我很好奇 UserAccountControl 属性的实现来控制特定帐户的属性。如果我想在我自己的应用程序中使用字节组合来实现设置来确定 x 或 y 设置的状态，我将如何在 C# 中执行此操作？假设我想在我自己的类上实现一个 useraccountcontrol 属性，并且我想使用字节组合来确定帐户应该拥有哪些权限。

这是它在 Active Directory 中的修改方式：http: //support.microsoft.com/kb/305144

这里是对象定义的地方：http: //msdn.microsoft.com/en-us/library/ms680832%28VS.85%29.aspx

编辑：

假设我有一个自己的 User 类，并且我想实现一个类似于在 Active Directory 中实现 UserAccountControl 的方式的属性。假设我想要一组四个字节来存储设置。

我想使用最后一个字节来确定帐户状态，0 = 帐户不活动 1 = 帐户活动 2 = 帐户已过期 4 = 一些其他状态 8 = 另一个状态。

然后左边的下一个字节我想包含帐户类型：16=Admin Account，32=Regular Account，64=Guest Account，128=Other Account。

然后使用左边的下一个字节来设置一些其他设置，以便 256 = 某些东西，512 = 其他东西，1024 = 其他东西，等等。

我想将其结合起来使用按位组合来设置帐户属性。我脑子里有这个想法，但我不确定如何实现它，或者我想要做什么是否有意义。

编辑：在收到答案并进行更多挖掘后，我发现这个链接更多地讨论了设置标志：http: //msdn.microsoft.com/en-us/library/ms229062.aspx

我有特殊需要，最重要的问题是：

• 在记忆中
• 非常低的内存占用
• 速度

这是我的“问题”：我需要在内存中存储大量非常稀疏的位数组。这些位集是“仅附加”的，主要用于交叉路口。巨大的，我的意思是高达 200 000 位数组。

每个位集的范围应在 [0...16 000 000] 之间。

我使用“仅”包含一些实际数据的 10 673 位数组进行了一些预测试，得到了以下结果：

看到所涉及的数字，我显然需要使用压缩位数组，这不是问题：看到位数组是“仅附加”的，它应该很容易处理。

打开的位数组位有点分组，但不完全。所以你会倾向于在同一个区域有几个位（但通常不是一个接一个，这使得 RLE 不太适合那些打开的位）。

我的问题是使用什么样的压缩？

现在我不知道我应该把我的第一种方法放在这里还是回答我自己的问题。

基本上我想象了一个使用非常愚蠢的编码的“最坏情况”场景：

• 1 位：如果打开，接下来的 5 位确定需要多少位来计算“跳过”，如果关闭，则优化：接下来的 5 位确定需要多少位（即 'on' 或 'off '，不跳过）[只有在确定比其他表示更有效时才会切换到，所以当它启动时，它应该始终是优化（大小方面）]

• 5 位：在下一位之前我们可以跳过多少位

• x位：跳过

这是一个示例：一个位数组有 3 个位集，第一个位在 3 098 137，第二个在 3 098 141，第三个在 3 098 143。

第一个位告诉我们要跳过位。5 下一位（总是 5）告诉我们需要多少位，告诉我们将跳过多少位 22 位告诉跳到 3 098 137 一位告诉现在我们没有跳过位 5 下一位（总是 5）告诉我们将“按原样”读取多少位 6 位：关闭、关闭、关闭、开启、关闭、开启意味着 3 098 141 和 3 098 143 开启等。

看到这些位数组惊人的稀疏性，这似乎非常节省大小。

所以使用这种编码，我获取了我的样本数据并计算了一个“最坏情况”的场景（我还没有编写算法，我宁愿先从这里输入一些）：基本上我认为不仅“大小优化”永远不会启动，而且 5 位将始终设置为其最大值（24 位），这当然不会发生。

我这样做只是为了对“最坏中的最坏”情况有一个非常粗略的近似。

我非常惊喜：

数据是实际数据并且所有数据都相似，我知道，如果情况变得更糟，我可以将我的 200 000 位数组存储在大约 240 MB 中，这很好。

我很确定实际的编码会比这少，但由于我还没有真正编写它，我只能（非常容易地）计算“最坏情况”，这就是为什么我只显示那个。

关于如何提高尺寸效率的任何提示/想法（记住这些是超稀疏位数组，应该有数十万个，它们必须在内存中，并且它们应该“仅附加”） ?

关于我的“仅附加”案例

基本上我有一个不断增长的“扩展”（范围，但“扩展”是我理解的实际术语）和许多具有一些位集的位数组。当范围从 0 到 1 000 000 时，所有位数组都从 0 到 1 000 000 到。当范围增长到 1 000 001 时，所有位数组也在增长，全部增长一位。但是大多数这些位数组的末尾会附加一个“0”，而大约 4 到 8 个位数组的末尾会附加一个“1”。但是，我无法提前预测哪些位数组将附加 0 或 1。

所以我有很多大小相同的位数组，它们都非常稀疏（< 0.5% 的位集）并且随着范围的增长而“增长”（所以它们总是在增长以同样的速度）。

Judy 数组很棒。但几年前我读到了它们，这些东西“在我头上”。Judy 数组是一个仅限 C 语言的 20KLOC 库，我绝对不会重新实现它。但他们太棒了。

所以我想我需要补充一下，我希望所有这些都保持相对简单，这并不是牵强附会，因为我非常稀疏的位数组的特殊“仅附加”属性。

.NET Micro Framework 是否有 BitArray 替代品？我在考虑简单地使用 bool[]，但是如何将它转换回 byte[] 呢？

在完整的框架中，考虑到“位”是一个 BitArray，以下工作：

但我似乎在微框架中找不到 BitArray 类

想象一下，您想序列化和反序列化 stackoverflow 帖子，包括它们的标签，尽可能有效地节省空间（以二进制形式），而且在进行标签查找时也能提高性能。这种场景有没有好的数据结构？

Stackoverflow 有大约 28532 个不同的标签，您可以创建一个包含所有标签的表格并为它们分配一个整数，此外您可以按频率对它们进行排序，以便最常见的标签具有最低的数字。从搜索和存储的角度来看，仍然像“1 32 45”格式的字符串一样简单地存储它们似乎有点低效

另一个想法是将标签保存为变量位数组，这从查找和序列化的角度来看很有吸引力。由于最常见的标签是第一个，因此您可能会将标签放入少量内存中。

问题当然是不常见的标签会产生巨大的位数组。是否有任何标准用于“压缩”大跨度 0 的位数组？还是应该完全使用其他结构？

编辑

我不是在寻找数据库解决方案或需要将整个表保存在内存中的解决方案，而是用于过滤单个项目的结构