查找位返回數組？

Question

我有以下的使用情況下， 陣列基於位表示整數

vector<int> containing elements 123 345 678 890 555 ... 
          pos 0 1 2 3 4 

的我收到e.g

101 then return 123 678 (Elements of the array with its position bits set) 
0011 then return 678 890 
00001 then return 555 

你能推薦我可以用它來解決這個問題的任何庫。

編輯：矢量本身是動態的，位大小可以變化，基於1位想要返回相應的數組元素。

Answer 1

您最終想要將位設置爲其位索引。這是很容易使用衆所周知的位擺弄黑客：

bit_mask_iterator= bits; 

while (bit_mask_iterator) 
{ 
    long single_bit_set= bit_mask_iterator & -bit_mask_iterator; 
    long bit_index= count_bits_set(single_bit_set - 1); // this is the index you want 
    bit_mask_iterator&= bit_mask_iterator - 1; 
} 

凡count_bits_set可以用編譯器的內部或手動設置（參見http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel）來實現。如果您願意，也可以使用查找single_bit_set的log2。

Answer 2

這是一個快速和骯髒的解決方案

vector<int> filtered; 

    char *bits = "0011"; 

    for(int i = 0;i < sizeof(bits) ; i++) 
     if(bit[i] == '1') 
     filtered.push_back(myvector[i]); 

    return filtered 

Answer 3

OK，你可以使用過濾迭代器做一個稍微更優雅。正如我在你的問題中所看到的那樣，陣列上的索引以與數字相反的順序開始（數字的位置「0」的索引對應於陣列中的位置「3」）。所以你必須反過來看陣列來選擇正確的元素。另外，由於返回值可能包含0,1,2,3或4個元素，我建議您返回一個列表。這裏是一個暗示：

struct filter 
{ 
    filter (int n) :number (n) 
    { 
    } 

    bool operator()(int other_number) 
    { 
      bool result = number & 1; 
      number>>=1; 
      return result; 
    } 

    int number; 

}; 


int main(void) 
{ 
using namespace std; 

    vector<int> my_v (4); 
    my_v[0] = 123; 
    my_v[1] = 356; 
    my_v[2] = 678; 
    my_v[3] = 890; 

    int bin_num = 10; // 1010 

    list<int> out_list; 

    std::copy(boost::make_filter_iterator (filter (bin_num), 
              my_v.rbegin(), 
              my_v.rend()), 
       boost::make_filter_iterator(filter (bin_num), 
              my_v.rend(), my_v.rend()), 
       std::front_inserter (out_list)); 
    // out_list will have 123 678 

} 

希望這有助於

Answer 4

int bitMask = 11; // 1011 (reverse the bitmask when it comes in) 
int count = 0; 
vector<int> myVector (4); 
vector<int> returnVector; 

myVector[0] = 123; 
myVector[1] = 356; 
myVector[2] = 678; 
myVector[3] = 890; 

while (bitMask) 
{ 
    if (bitMask & 0x01) 
    { 
     returnVector.push_back (myVector[count]); 
    } 
    count++; 
    bitMask >>= 1; 
} 

Answer 5

我認爲一個位掩碼存儲在容器（在系統上支持位掩碼超過sizeof(uintmax_t)位）。在這種情況下溶液的本質是：

std::remove_copy_if(v.begin(), v.end(), std::back_inserter(out), 
        !*boost::lambda::var(pred)++); 

凡v - 輸入向量; out - 存儲結果的向量; pred - 位掩碼上的迭代器。

如果想避免boost::lambda，則很容易模擬：

template <class InputIterator, class OutputIterator, class PredicateIterator> 
void copy_if(InputIterator first, InputIterator last, OutputIterator result, 
      PredicateIterator pred) { 
    for (; first != last; ++first) 
    if (*pred++) 
     *result++ = *first; 
} 

它可以如下（使用相同的表示法，如上面的例子）使用：

copy_if(v.begin(), v.end(), std::back_inserter(out), pred); 

或使用謂詞相同：

template <class Iterator> 
class Pred { 
    Iterator it; 
public: 
    Pred(Iterator it_) : it(it_) {} 
    template <class T> 
    bool operator()(T /* ignore argument */) { return !*it++; } 
}; 
template <class Iterator> 
Pred<Iterator> iterator2predicate(Iterator it) { 
    return Pred<Iterator>(it); 
} 

可按如下方式使用：

std::remove_copy_if(v.begin(), v.end(), std::back_inserter(out), 
        iterator2predicate(pred)); 

實施例（使用boost::lambda，但它很容易通過上述兩個其他選項來代替它）：

/** g++ -Wall -Ipath/to/boost -o filter_array filter_array.cpp */ 
#include <algorithm> 
#include <iostream> 
#include <iterator>  // back_inserter() 
#include <vector>  
#include <boost/lambda/lambda.hpp> 

#define LEN(array) (sizeof(array)/sizeof(*(array)))  
#define P(v) { std::for_each(v.begin(), v.end(),   \ 
        std::cout << boost::lambda::_1 << " "); \ 
       std::cout << std::endl; } 

int main() { 
    int a[] = {123, 345, 678, 890, 555,}; 
    const size_t n = LEN(a); 
    bool bits[][n] = { 
    1, 0, 1, 0, 0, 
    0, 0, 1, 1, 0, 
    0, 0, 0, 0, 1, 
    }; 
    typedef std::vector<int> Array; 
    Array v(a, a + n); 
    P(v);  
    for (size_t i = 0; i < LEN(bits); ++i) { 
    Array out; 
    std::vector<bool> b(bits[i], bits[i] + LEN(bits[i])); 
    std::vector<bool>::const_iterator pred = b.begin(); 
    P(b); 
    std::remove_copy_if(v.begin(), v.end(), std::back_inserter(out), 
         !*boost::lambda::var(pred)++); 
    P(out); 
    } 
} 

輸出：

123 345 678 890 555 
1 0 1 0 0 
123 678 
0 0 1 1 0 
678 890 
0 0 0 0 1 
555