Return an array by looking up bits?

Question

I have the following use case , array of integers

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

Based on the bits representation I receive for 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

Can you recommend any libraries which I can use to solve this problem.

EDIT: The vector itself is dynamic and the bit size can vary, based on the 1 bits want to return corresponding array elements.

Answer 1

You ultimately want to map bits set to their bit index. That's pretty easy using well-known bit twiddling hacks:

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;
}

Where count_bits_set can be implemented with a compiler intrinsic or manually (see http://www-graphics.stanford.edu/~seander/bithacks.html#CountBitsSetParallel). You could also use finding the log2 of single_bit_set if you wanted to.

Answer 2

This is a quick and dirty solution

    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, You can do this one slightly more elegant using filtering iterators. As I see on your question, the indices on the array start in reverse order than that of the number (index of position "0" of the number corresponds to position "3" in the array). So you have to go in reverse looking at the array to select the correct elements. Also, as the return value may contain 0, 1, 2, 3, or 4 elements, I suggest you to return a list. Here is a hint:

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

}

Hope this helps,

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

I assume that a bit mask is stored in a container (to support bit masks with more than sizeof(uintmax_t) bits on your system). In this case the essence of solution is:

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

Where v - an input vector; out - a vector to store results; pred - an iterator over a bit mask.

If you'd like to avoid boost::lambda then it is easily simulated:

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;
}

It can be used as follows (using the same notation as in the above example):

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

Or the same using a predicate:

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);
}

That can be used as follows:

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

Example (using boost::lambda, but it is easy to replace it by the above two other options):

/** 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);
  }
}

Output:

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