通过查找位返回一个数组？

Question

我有以下用例， 整数数组

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

基于我收到的位表示，例如，

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

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 3

我假设位掩码存储在容器中（以支持系统上具有超过 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 

Answer 4

这是一个快速但肮脏的解决方案

    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 5

好的，您可以使用过滤迭代器来稍微优雅地完成此操作。 正如我在你的问题中看到的，数组上的索引以与数字相反的顺序开始（数字位置“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

}

希望这有帮助，