XOR bitset, когда 2D bitset сохраняется как 1D
Отвечать Как хранить двоичные данные, когда вы заботитесь только о скорости?, Я пытаюсь написать некоторые для сравнения, поэтому я хочу использовать std::bitset, Тем не менее, для справедливого сравнения, я хотел бы 1D std::bitset подражать 2D.
Поэтому вместо того, чтобы:
bitset<3> b1(string("010"));
bitset<3> b2(string("111"));
Я хотел бы использовать:
bitset<2 * 3> b1(string("010111"));
оптимизировать локальность данных. Тем не менее, сейчас у меня возникли проблемы с Как мне хранить и вычислять расстояние Хемминга между двоичными кодами?, как видно из моего минимального примера:
#include <vector>
#include <iostream>
#include <random>
#include <cmath>
#include <numeric>
#include <bitset>
int main()
{
const int N = 1000000;
const int D = 100;
unsigned int hamming_dist[N] = {0};
std::bitset<D> q;
for(int i = 0; i < D; ++i)
q[i] = 1;
std::bitset<N * D> v;
for(int i = 0; i < N; ++i)
for(int j = 0; j < D; ++j)
v[j + i * D] = 1;for(int i = 0; i < N; ++i)
hamming_dist[i] += (v[i * D] ^ q).count();
std::cout << "hamming_distance = " << hamming_dist[0] << "\n";
return 0;
}
Ошибка:
Georgioss-MacBook-Pro:bit gsamaras$ g++ -Wall bitset.cpp -o bitset
bitset.cpp:24:32: error: invalid operands to binary expression ('reference' (aka
'__bit_reference<std::__1::__bitset<1562500, 100000000> >') and
'std::bitset<D>')
hamming_dist[i] += (v[i * D] ^ q).count();
~~~~~~~~ ^ ~
/Library/Developer/CommandLineTools/usr/bin/../include/c++/v1/bitset:1096:1: note:
candidate template ignored: could not match 'bitset' against
'__bit_reference'
operator^(const bitset<_Size>& __x, const bitset<_Size>& __y) _NOEXCEPT
^
1 error generated.
что происходит, потому что он не знает, когда остановиться! Как я могу сказать это остановить после обработки D бит?
Я имею в виду без использования 2D структура данных.
Решение
Проблема в том, что v[i * D] доступ к одному биту. В вашей концептуальной модели двумерного битового массива он обращается к биту в строке i и колонка 0,
Так v[i * D] это bool а также q это std::bitset<D>и побитовый логический оператор XOR (^) применять к тем не имеет смысла.
Если v предназначен для представления последовательности двоичных векторов размера D, вы должны использовать std::vector<std::bitset<D>> вместо. Также, std::bitset<N>::set() устанавливает все биты в 1,
#include <vector>
#include <iostream>
#include <random>
#include <cmath>
#include <numeric>
#include <bitset>
int main()
{
const int N = 1000000;
const int D = 100;
std::vector<std::size_t> hamming_dist(N);
std::bitset<D> q;
q.set();
std::vector<std::bitset<D>> v(N);
for (int i = 0; i < N; ++i)
{
v[i].set();
}
for (int i = 0; i < N; ++i)
{
hamming_dist[i] = (v[i] ^ q).count();
}
std::cout << "hamming_distance = " << hamming_dist[0] << "\n";
return 0;
}
Другие решения
Других решений пока нет …