將std :: vector <unsigned int>解釋爲bitvector - 高效算法？

Question

我想解釋

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。數組，第一列是單序列的開始，第二列是序列的結尾。此外，我將需要一些特殊的待遇，從一個元素到下一個元素的營業額。

這裏是我的一般性問題：你覺得這個辦法怎麼樣？有沒有辦法更有效地處理這個問題？提前感謝您的幫助。

本

Answer 1

有各種花樣按位有效做到位掃描，但如果你使用C++，你可以利用兩種或std::bitset的boost::dynamic_bitset遍歷位的位置。你所描述的算法對每個塊都會反向迭代，所以你可能想用32 - (32 - i)這樣的方法來反轉你的位置。

根據各自的體系，每一位應採取大約一個週期。

Answer 2

有用於尋找在一個字組的第一比特，即使用專用處理器的指令或各種聰明的技巧高效（恆定時間）的方法（參見例如Position of least significant bit that is set）。

有了一點照顧，你可以反向工作，並利用這些掃描的第一個，然後做一些屏蔽和位翻轉和搜索下一個零，依此類推。

這可能給你一個更快的算法，尤其是如果序列平均長，所以快速掃描的收益超過了位twiddling的成本。