将std :: vector <unsigned int>解释为bitvector - 高效算法？

我想解释将std :: vector <unsigned int>解释为bitvector - 高效算法？

std::vector<unsigned int> numbers

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

例如：我有15和112存储在数字的值。因此，位29至32和位58至60等于1。挑战是优化此功能的运行时间。

这里是我的想法如何处理这个问题：我想与 -loops的两个一起工作。第一个循环遍历“数字”元素（我们称之为element_loop），而第二个循环用于找出单个元素中所有元素的位置（我们称之为bit_loop）。我想到为此目的检测序列的“上升”和“下降沿”。

在每个bit_loop周期的开始，一个面具被初始化为十六进制。值为0x80000000。用这个掩码我检查第一位是否等于1。如果是，则存储当前位置（0）。以下，二进制表示中的掩码“ 00 ...”用于检测下一个周期中的“下降沿”。如果否，则将掩码向右移动一位“ 00 ...”以检测下一个周期中的“上升沿”。（I只关心夫妇粗体数字的）

一旦检测到边缘，我存储当前位置，并通过一个比特移位以适当方式掩模。因此，在一个pos之后。边缘（）我切换到neg。边缘检测（），反之亦然。在遍历32位的已分配数字时，我将所有边缘位置存储在某种向量中。这个向量可能是2-dim。数组，第一列是单序列的开始，第二列是序列的结尾。此外，我将需要一些特殊的待遇，从一个元素到下一个元素的营业额。

这里是我的一般性问题：你觉得这个办法怎么样？有没有办法更有效地处理这个问题？提前感谢您的帮助。

本

来源

2015-10-16 Raist246

如果你想确保它是32位，并同时隐式记录该事实，请使用'uint32_t'。 –

嗯，你可以尝试性病::矢量或bitset 。 – Surt

检查[this]（http://stackoverflow.com/a/523737/2339141）如何检查是否设置了一个位。 –

有各种花样按位有效做到位扫描，但如果你使用C++，你可以利用两种或std::bitset的boost::dynamic_bitset遍历位的位置。你所描述的算法对每个块都会反向迭代，所以你可能想用32 - (32 - i)这样的方法来反转你的位置。

根据各自的体系，每一位应采取大约一个周期。

来源

2015-10-16 17:57:39 Jason

有用于寻找在一个字组的第一比特，即使用专用处理器的指令或各种聪明的技巧高效（恒定时间）的方法（参见例如Position of least significant bit that is set）。

有了一点照顾，你可以反向工作，并利用这些扫描的第一个，然后做一些屏蔽和位翻转和搜索下一个零，依此类推。

这可能给你一个更快的算法，尤其是如果序列平均长，所以快速扫描的收益超过了位twiddling的成本。

来源

2015-10-16 18:16:23

非常感谢那篇技巧！这就是我现在使用的：从LSB端开始，我用DeBruijn序列检测第一个“1”。之后，我反转数字并将所有得到的“1”右边的检测位置零，并使用掩码（0xFFFFFFFF <<找到位置+1）。我会在下一个循环中检测到的“1”是序列的结尾。 – Raist246

将std :: vector <unsigned int>解释为bitvector - 高效算法？

回答

相关问题