Prev: Nelson & Carter
Next: John Wilson's Differential Geometry UserRPL Program
From: supergems on 9 Apr 2010 03:44
Hi, how can we calculate the Hamming distance ( http://en.wikipedia.org/wiki/Hamming_distance
) between two binary numbers? For example, the Hamming distance
between 1011101 and 1001001 is 2.

supergems

From: supergems on 9 Apr 2010 03:45
Obviously with the HP 50g ;-)
From: Teuvo Yrjömäki on 9 Apr 2010 05:52
a quick try, works at least for some numbers...

<< 0 -> acc
<< dup2 b->r .001 + log 2 log / ip
swap
b->r .001 + log 2 log / ip
max 0 swap 1 +
for x dup2 #1b and swap #1b and if /=
then acc 1 + 'acc' sto end
sr swap sr next
drop2 acc
>>
>>

supergems schreef:
> Hi, how can we calculate the Hamming distance ( http://en.wikipedia.org/wiki/Hamming_distance
> ) between two binary numbers? For example, the Hamming distance
> between 1011101 and 1001001 is 2.
>
> supergems
>
From: Dave Hayden on 9 Apr 2010 07:00
On Apr 9, 3:44 am, supergems <simone.cer...(a)gmail.com> wrote:
> Hi, how can we calculate the Hamming distance (http://en.wikipedia.org/wiki/Hamming_distance
> ) between two binary numbers? For example, the Hamming distance
> between 1011101 and 1001001 is 2.
>
> supergems

Given two binary numbers A and B, then Hamming distance is the number
of "1" bits in (A AND B). Here's a library that will count the bits:
http://www.hpcalc.org/details.php?id=2752

There are some REALLY clever ways to count bits. This site lists many
of them:
http://graphics.stanford.edu/~seander/bithacks.html#CountBitsSetNaive

If you expect the Hamming distance to be small, then Brian Kernighan's
method would be a good choice. It's very small and the run time and
proportional to the number of bits that are set. In C code:
unsigned int v; // count the number of bits set in v
unsigned int c; // c accumulates the total bits set in v
for (c = 0; v; c++)
{
v &= v - 1; // clear the least significant bit set
}

From: Michael J. Sch�lke on 9 Apr 2010 08:29
Dave Hayden schrieb:
> Given two binary numbers A and B, then Hamming distance is the number
> of "1" bits in (A AND B).

A XOR B, surely?

Regards,
Michael
 |  Next  |  Last
Pages: 1 2
Prev: Nelson & Carter
Next: John Wilson's Differential Geometry UserRPL Program