将2D位集存储为1D时的XOR位集 [英] XOR bitset when 2D bitset is stored as 1D

问题描述

要回答如何存储二进制数据当您只关心速度吗?时，我试图编写一些比较表，所以我想使用std::bitset.但是，为了公平起见，我希望1D std::bitset模仿2D.

To answer How to store binary data when you only care about speed?, I am trying to write some to do comparisons, so I want to use std::bitset. However, for fair comparison, I would like a 1D std::bitset to emulate a 2D.

所以没有:

bitset<3> b1(string("010"));
bitset<3> b2(string("111"));

我想使用:

bitset<2 * 3> b1(string("010111"));

优化数据局部性.但是，现在我遇到了该如何处理的问题我存储并计算二进制代码之间的汉明距离吗?，如我的最小示例所示:

to optimize data locality. However, now I am having problem with How should I store and compute Hamming distance between binary codes?, as seen in my minimal example:

#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位后停止?

which occurs because it doesn't know when to stop! How I can tell it to stop after processing D bits?

我的意思是不使用2D data-结构.

I mean without using a 2D data-structure.

推荐答案

问题是v[i * D]访问单个位.在您的2D位数组的概念模型中，它访问i行和0列的位.

The problem is that v[i * D] accesses a single bit. In your conceptual model of a 2D bit array, it accesses the bit at row i and column 0.

因此，v[i * D]是bool，而q是std::bitset<D>，应用于这些位的按位逻辑XOR运算符(^)没有意义.

So v[i * D] is a bool and q is a std::bitset<D>, and the bitwise logical XOR operator (^) applied to those doesn't make sense.

如果v旨在表示大小为D的二进制矢量序列，则应改用std::vector<std::bitset<D>>.另外，std::bitset<N>::set()将所有位都设置为1.

If v is meant to represent a sequence of binary vectors of size D, you should use a std::vector<std::bitset<D>> instead. Also, std::bitset<N>::set() sets all bits to 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;
}

这篇关于将2D位集存储为1D时的XOR位集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！