1

我想解释

std::vector<unsigned int> numbers

作为位向量，即 的 MSBnumbers[0]是第 1 位，的 MSBnumbers[1]是第 33 位，依此类推。我想在这个向量中找到所有的序列，并将相应的位置存储在数据结构中。（这里也将单个One定义为序列）

例如：我将值 15 和 112 存储在数字中。因此位 29 到 32 和位 58 到 60 等于 1。挑战是优化这个函数的运行时间。

这是我如何处理这个问题的想法：我想到了使用两个for循环。第一个循环遍历“数字”的元素（我们称之为 element_loop），而第二个循环用于计算单个元素中所有 One 的位置（我们称之为 bit_loop）。为此，我想到了检测序列的“上升沿”和“下降沿”。

在每个 bit_loop 循环开始时，将掩码初始化为十六进制。值0x80000000。使用此掩码，我检查第 1 位是否等于 1。如果是，则存储当前位置 (0)。接下来，使用二进制表示的掩码“ 10 00...”来检测下一个周期中的“下降沿”。如果否，则将掩码向右移动一位“ 01 00...”，以便在下一个周期中检测“上升沿”。（我只关心这两个粗体数字）

一旦检测到边缘，我就会存储当前位置并以适当的方式将掩码移动一位。因此，在 pos 之后。边缘（01）我切换到否定。边缘检测（10），反之亦然。在遍历 32 位无符号数时，我将所有边缘位置存储在某种向量中。这个向量可以是 2-dim。数组，第一列是一个序列的开始，第二列是序列的结束。此外，我需要对从一个元素到下一个元素的转换进行一些特殊处理。

这是我的一般问题：您如何看待这种方法？有没有办法更有效地处理这个问题？非常感谢您提前提供的帮助。

本

4

2 回答 2

1

有各种按位技巧可以有效地进行位扫描，但如果您使用 C++，您可以利用其中一个std::bitset或boost::dynamic_bitset迭代位位置。但是，您描述的算法会为每个块向后迭代，因此您可能希望使用类似32 - (32 - i).

根据体系结构，每个位应该大约需要一个周期。

于 2015-10-16T17:57:39.093 回答
0

There are efficient (constant time) methods for finding the first bit set in a word, using either special processor instructions or various clever tricks (see e.g. Position of least significant bit that is set).

With a bit of care you could work backwards and use those to scan for the first one, then do some masking and bit flipping and search for the next zero, and so on.

This might give you a faster algorithm, especially if the sequences are long on average so the gain on the fast scans outweighs the cost of the bit twiddling.

于 2015-10-16T18:16:23.773 回答