Самый быстрый способ очистить каждый k-й бит в boost :: dynamic_bitset - PullRequest
Новая
       29

Самый быстрый способ очистить каждый k-й бит в boost :: dynamic_bitset

1 голос
/ 13 апреля 2011

Какой самый быстрый способ очистить каждый kth бит в boost::dynamic_bitset, возможно со смещения j?

В настоящее время я делаю это, что чертовски медленно (псевдокод): 

for (i = j; i < bitset.size(); i += k) {
    bitset[i] = 0;
}

Нужно сделать миллионы бит-клиров, поэтому я ищу быстрый способ сделать это.

Ответы [ 2 ]

1 голос
/ 13 апреля 2011

хорошо, не уверен, что это быстрее, но я думаю, что вы можете проверить:

Ключевой операцией является построение наборов битов маски, у вас должна быть таблица предварительно созданных масок (которая будетпозволяет вам сбросить каждый k -й бит до каждого 32-го бита [на моей платформе unsigned long - 32-битный]).Затем дорогостоящая операция создает полную маску того же размера, что и входные данные - если он всегда имеет одинаковый размер, а память не является ограничением, вы можете просто создать для этого таблицу поиска, а затем просто &Использование двухбитовых наборов. 

#include <iostream>
#include <limits>
#include <boost/dynamic_bitset.hpp>

using namespace std;

int main(void)
{
  boost::dynamic_bitset<> orig(64);
  for (int i = 0; i < orig.size(); ++i) {
    orig[i] = rand() % 2;
  }

  std::cout << orig << std::endl;

  unsigned long mask = 0x88888888; // reset every 4th bit
  boost::dynamic_bitset<> mbits(numeric_limits<unsigned long>::digits, mask);

  while(mbits.size() < orig.size())
    mbits.append(mask);
  mbits.resize(orig.size()); // incase not aligned
  mbits <<= 5; // arbitary starting point (i.e. j)
  std::cout << mbits << std::endl;

  mbits.flip();

  std::cout << mbits << std::endl;

  orig &= mbits;

  std::cout << orig << std::endl;

  return 0;
}

ОБНОВЛЕНИЕ: Хорошо, просто очень грубо протестировали его, и вы можете увидеть результат здесь: http://www.ideone.com/ez3Oc, с предварительно созданной маской, это может быть почти+ На 40% быстрее ...

0 голосов
/ 13 апреля 2011

Для очень больших наборов битов вычислите маску длиной n бит (где n - ваш собственный размер, например 64 для x86_64), как предложил Nim, примените его.
Если ваша собственная длина не кратна k, сдвиньте ее соответственно.
Так что, если у вас есть собственная длина 10 и вы хотите установить только каждый 3-й бит из 30-битного набора битов, вам потребуется 3 прохода, как это:
Первые 10 бит: 0010010010
Вторые 10 бит: 0100100100
Последние 10 бит: 1001001001
Итак, после применения каждой маски вам нужно сдвинуть ее (n% k) битов влево.

Повторяйте, пока не закончите.

...