Вернуть массив путем поиска битов? - PullRequest
Новая
       11

Вернуть массив путем поиска битов?

2 голосов
/ 12 февраля 2009

У меня есть следующий вариант использования, массив целых чисел 

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 бит, которые хотят вернуть соответствующие элементы массива.

Ответы [ 5 ]

4 голосов
/ 12 февраля 2009

В конечном итоге вы хотите отобразить биты, установленные на их битовый индекс. Это довольно легко, используя известные хиты с трюками: 

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 ) Вы также можете использовать поиск log2 single_bit_set, если хотите.

1 голос
/ 12 февраля 2009

Я предполагаю, что битовая маска хранится в контейнере (для поддержки битовых масок с более чем 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
1 голос
/ 12 февраля 2009 
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;
}
0 голосов
/ 12 февраля 2009

ОК, Вы можете сделать это немного более элегантно, используя итераторы фильтрации. Как я вижу по вашему вопросу, индексы в массиве начинаются в обратном порядке по сравнению с номером (индекс позиции «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

}

Надеюсь, это поможет,

0 голосов
/ 12 февраля 2009

Это быстрое и грязное решение 

    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
...