查找位返回数组？

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