Fast hamming distance between 2 bitset
<p>I'm writing a software that heavily relies on (1) accessing single bit and (2) Hamming distance computations between 2 bitset A and B (ie. the numbers of bits that differ between A and B). The bitsets are quite big, between 10K and 1M bits and i have a bunch of them. Since it is impossible to know the bitset sizes at compilation time, i'm using <code>vector &lt; bool &gt;</code> , but i plan to migrate to <code>boost::dynamic_bitset</code> soon.</p>

<p>Hereafter are my questions:</p>

<p>(1) Any ideas about which implementations have the fastest single bit access time?</p>

<p>(2) To compute Hamming distance, the naive approach is to loop over the single bits and to count differences between the 2 bitsets. But, my feeling is that it might be much faster to loop over bytes instead of bits, perform R = byteA XOR byteB, and look in a table with 255 entries what "local" distance is associated with R. Another solutions would be store a 255 x 255 matrix and access directly without operation to the distance between byteA and byteB. So my question: Any idea how to implement that from <code>std::vector &lt; bool &gt;</code> or boost::dynamic_bitset? In other words, do you know if there is a way to get access to the bytes array or i have to recode everything from scratch?</p>
