问题标签 [bitstring]

我正在尝试进行 Euler number 219项目，但未能掌握它。我正在尝试使用 Python，根据 Euler 项目，它应该能够在一分钟内完成！这让我认为他们不可能希望我计算每个单独的位串，因为这在 Python 中太慢了——必须有一个 sub O(n) 算法。

我查看了一个递归解决方案，它存储位串可能的前缀，以便它可以快速选择一个新的位串，甚至将它们分组考虑。这仅适用于 10 多一点的暴力破解值：

过去，我正在努力理解如何减少问题。总是可以制作出如下模式：

但对于超过 7 个位串来说，它并不是最优的。谁能指导我应该考虑什么？

我有一些 256 个十六进制字符的字符串，它们代表一系列位标志，我正在尝试将它们转换回位字符串，以便我可以使用&、|等来操作它们vec。十六进制字符串被写入整数范围的大端组，这样一组 8 个字节"76543210"应该转换为 bitstring "\x10\x32\x54\x76"，即最低 8 位是00001000。

问题是pack''h格式一次只处理一个字节的输入，而不是 8 个字节，因此直接使用它的结果不会按正确的顺序排列。目前我正在这样做：

这有效，但感觉很hackish。好像应该有更干净的方法，但我的pack-fu不是很强。有没有更好的方法来做这个翻译？

给定要解释为位字符串的 MATLAB uint32，计算字符串中有多少非零位的有效且简洁的方法是什么？

我有一个可行的、幼稚的方法来循环这些位，但这对我的需要来说太慢了。（使用 std::bitset count() 的 C++ 实现几乎立即运行）。

我发现了一个非常不错的页面，列出了各种位计数技术，但我希望有一种简单的 MATLAB 式方法。

http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

更新#1

刚刚实现了 Brian Kernighan 算法如下：

性能仍然很糟糕，仅计算 4096^2 权重计算需要超过 10 秒。我的 C++ 代码使用 std::bitset 中的 count() 可以在亚秒时间内完成。

更新#2

这是迄今为止我尝试过的技术的运行时间表。当我得到更多的想法/建议时，我会更新它。

评论：MATLAB 中的 dec2bin() 函数似乎实现得很差。它运行非常缓慢。

评论：“Naive bitget loop”算法实现如下：

评论： Scheiner 算法的循环展开版本如下所示：

Scott，我要感谢您的 BitString 程序。我正在解释来自中子探测器的数据，我发现这个模块正是我需要的工具。不幸的是，我还没有让模块成功通过 test-bitstring.py。我正在运行 Windows XP 和 Python 3.1。我已经从您的网站下载了您的文件 bitstring-0.4.1.zip，并将 bitstring.py 和 test-bitstring.py 解压缩到我的 Python 目录的 \lib 文件夹中。运行 test-bitstring.py 后，我得到 11 个错误。:(

我已经三重检查我是否下载了正确的版本，并且这两个 .py 文件都成功地进入了我的 \lib 文件夹。使用带有 BitString 的 Windows 是否存在已知的并发症？这可能是我正在做的事情，但我不知道从这里去哪里。在您的文档中，您明确表示如果版本正确并且错误仍然存​​在，请与您联系。我很确定我遗漏了一些明显的东西，但我想检查一下这不是某种兼容性问题吗？

感谢您抽出时间来阅读。很抱歉打扰您，因为我相信您对此有很多疑问。如果你有机会回复我，我很想知道你为什么认为它可能会通过测试。再次感谢！

我正在尝试找出一种方法来查看位串是否在小于 n 的时间内在位串大小 n 中具有 2 个连续的位串。

例如，假设我们有一个大小为 5 的位串（索引 0-4）。如果索引 1 和 3 都是 0，我可以返回 false。但如果他们都是，那么我可能需要偷看 5 次才能找到我的答案。

位串的长度不必为 5。为简单起见，假设它可以在 3 到 8 之间。

我们被要求编写DES 算法的 Java 实现（用于加密和解密）。我有几个问题：

1. DES 指定应该有 64 位的纯文本或密文和一个正好 56 位的共享密钥。给出字节数的方法是什么，

2. 该算法使用了大量的位级操作，例如将 64 位分成两个 32 位部分。如何才能做到这一点？

动机

想象一个哈夫曼压缩文件被部分下载，就像在 P2P 软件中一样，所以我们首先为整个文件分配磁盘空间，然后开始下载随机文件块。其中一个霍夫曼码（但我们不知道是哪一个）是一个结束码，所以如果这个码被解码，我们就停止。假设该文件由几个霍夫曼压缩流组成，我们可以尝试在下载完成之前解压缩其中的一些。

磁盘空间的预分配方式现在很重要：假设我们有一个霍夫曼流的开始，但它不完整，所以我们遇到了预分配的磁盘空间。通常，这个空间都是 0，所以我们会继续用 huffman code 解码符号00..。如果这不是我们的最终代码，我们不会注意到“无效”数据，如果有 2 GB 的预分配空间，我们会进行很多无用的解码。

所以我们想预先分配空间以使解码尽快停止。

问题

我正在寻找充当“霍夫曼终止符”的最短位串，这意味着如果我们解码这个字符串，我们将至少解码每个霍夫曼代码一次，所以我们肯定会收到一个结束代码。这应该适用于长度1..n位的霍夫曼码的每种组合。

注意：我知道上面的假设场景有简单的解决方案（00..用作结束代码，使用 P2P 段数据来检测尚未下载的块），但这只是一个示例场景，展示了“霍夫曼终结器”的理论使用位串，我对解决这种情况不感兴趣，而是寻找算法/方法/想法来生成/查找充当“霍夫曼终结者”的位串。

例子

让我们看看n = 2: [0, 1], [00, 01, 1], [0, 10, 11],可能的 Huffman 代码组合[00, 01, 10, 11]。现在让我们从一个包含所有可能长度的位序列1..n（0, 1, 00, 01, 10, 11）的位串开始：

001011

使用不同的霍夫曼代码组合解码给出（霍夫曼代码分配给符号A..D）：

这是一个好的开始，它已经解码了前三个的每个霍夫曼代码，但是如果我们用 解码它[00, 01, 10, 11]，我们就会丢失符号B（霍夫曼代码01）。因此，让我们将其附加到我们的位串中：

00101101

这是一个有效的“霍夫曼终止符” n=2，长度为 8 位。如果我们用这个字节预先分配我们的磁盘空间，我们肯定会终止所有不超过 2 位的霍夫曼代码。我们甚至知道不会有更短的终止符字符串，n=2因为它是组合[00, 01, 10, 11]解码每个符号一次的最小长度。

n=3我还找到了, （43 位）的“霍夫曼终结符” 0001011001110100111010011100010101111101110，但我不能 100% 确定它是否正确，也不知道它是否是最短的。

我在寻找什么

• 为给定的.找到或生成霍夫曼终止符的算法/想法n。我的尝试将类似于示例：生成一个起始字符串并根据需要附加位以满足所有不同的霍夫曼代码组合。但我确信有更好的方法。

• 特定的 Huffman 终止符，n=8和n=16，虽然生成它们的计算成本可能很高，而且它们可能会很长。

• 有关此问题（或类似问题）的论文/链接（如果有）。

奖金

寻找“霍夫曼终止符”的奖励积分如果我们从位开始也可以工作1..n，因此如果数据之前解码并且我们不会到达并在第一位开始新的霍夫曼代码，它甚至会终止。

更新：在 python-bitstring 3.0.0 步骤中具有常规含义

我正在使用 python bitstring，我从文件加载了一个 ConstBitArray ，我想获得一个步长不同于 1 的切片。

在正常列表中，我会这样做：

但是位串对步进有一个奇怪的定义，请参阅：

http://packages.python.org/bitstring/slicing.html#stepping-in-slices

有人知道该怎么做吗？

谢谢

我正在编写代码来解码来自二进制协议的消息。每个消息类型都分配有一个 1 字节的类型标识符，并且每个消息都带有这个类型 id。消息都以由 5 个字段组成的公共标头开始。我的 API 很简单：

我的第一直觉是通过为每种消息类型编写一个解码函数并在 fun 参数中完全解码该消息类型来大量依赖模式匹配

请注意，虽然消息的前 5 个字段在结构上是相同的，但之后的字段因每种消息类型而异。

我有大约 20 种消息类型，因此有 20 个与上述类似的功能。我是否使用这种结构多次解码完整消息？是地道的吗？我最好只解码函数头中的消息类型字段，然后解码消息正文中的完整消息吗？

我正在尝试用更优雅的东西替换以下函数：

（我现在这不是尾递归——想保持简单，此外在较新的 Erlang 版本中性能并不重要）

示例输出：

带有列表推导的优雅解决方案将是更可取的，因为此结果将使用列表推导进一步处理，然后可以将其包装在一个推导中。

我试过

但是如果 Size 不是以下的倍数，这会留下最后一个块byte_site(P)：