Hamming
May 2, 2012 at 11:34am UTC
Can anyone please convert this piece of code to c++, It is written in python.
1 2 3 4 5 6 7
def hamming_distance(s1, s2):
assert len(s1) == len(s2)
return sum(ch1 != ch2 for ch1, ch2 in zip(s1, s2))
May 2, 2012 at 12:57pm UTC
This assumes 32 bit integers.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16
int bitcount(unsigned int u)
{
unsigned int uCount;
uCount = u
- ((u >> 1) & 033333333333)
- ((u >> 2) & 011111111111);
return
((uCount + (uCount >> 3))
& 030707070707) % 63;
}
unsigned int hamming_distance (unsigned int s1, unsigned int s2)
{
return (bitcount( s1 ^ s2));
}
Last edited on May 2, 2012 at 12:58pm UTC
May 2, 2012 at 2:37pm UTC
For counting bits,
std::bitset<>::count
is both simpler and faster (compiles to a single CPU instruction on x86, if the argument fits in a CPU register):
1 2 3 4 5 6 7
#include <bitset>
#include <climits>
unsigned int hamming_distance (unsigned int s1, unsigned int s2)
{
return std::bitset<CHAR_BIT * sizeof s1>(s1^s2).count();
}
However, that Python code was for any sequence, e.g. two strings. Its C++ equivalent would be
1 2 3 4 5 6 7 8 9 10
#include <numeric>
#include <functional>
template <typename C>
int hamdist(const C& c1, const C& c2)
{
return inner_product(c1.begin(), c1.end(),
c2.begin(), 0,
std::plus<int >(),
std::not_equal_to<typename C::value_type>() );
}
Last edited on May 2, 2012 at 2:40pm UTC
Topic archived. No new replies allowed.