# Hamming distance = XOR? - Unix

This is a discussion on Hamming distance = XOR? - Unix ; The hamming distance (HD) measures the number of different bits in two bitpatterns: v1 = [1 1 1 0] v2 = [0 1 0 0] HD = 2 But is the hamming distance not just a basic XOR operation: INPUT ...

# Thread: Hamming distance = XOR?

1. ## Hamming distance = XOR?

The hamming distance (HD) measures the number of different bits in two
bitpatterns:

v1 = [1 1 1 0]
v2 = [0 1 0 0]

HD = 2

But is the hamming distance not just a basic XOR operation:

INPUT OUTPUT

A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

2. ## Re: Hamming distance = XOR?

saneman wrote:
> The hamming distance (HD) measures the number of different bits in two
> bitpatterns:
>
> v1 = [1 1 1 0]
> v2 = [0 1 0 0]
>
> HD = 2
>
> But is the hamming distance not just a basic XOR operation:
>
> INPUT OUTPUT
>
> A B A XOR B
> 0 0 0
> 0 1 1
> 1 0 1
> 1 1 0

http://en.wikipedia.org/wiki/Hamming...ial_properties

Bye, Jojo

3. ## Re: Hamming distance = XOR?

Joachim Schmitz wrote:
> saneman wrote:
>> The hamming distance (HD) measures the number of different bits in
>> two bitpatterns:
>>
>> v1 = [1 1 1 0]
>> v2 = [0 1 0 0]
>>
>> HD = 2
>>
>> But is the hamming distance not just a basic XOR operation:
>>
>> INPUT OUTPUT
>>
>> A B A XOR B
>> 0 0 0
>> 0 1 1
>> 1 0 1
>> 1 1 0

> http://en.wikipedia.org/wiki/Hamming...ial_properties

Actually no, but it's the number of bits set after the XOR, not the value of
the XOR operation (which in your example would be 6 in decimal)

Bye, Jojo

4. ## Re: Hamming distance = XOR?

"Joachim Schmitz" skrev i en meddelelse
news:g1j79o\$kdr\$1@online.de...
> Joachim Schmitz wrote:
>> saneman wrote:
>>> The hamming distance (HD) measures the number of different bits in
>>> two bitpatterns:
>>>
>>> v1 = [1 1 1 0]
>>> v2 = [0 1 0 0]
>>>
>>> HD = 2
>>>
>>> But is the hamming distance not just a basic XOR operation:
>>>
>>> INPUT OUTPUT
>>>
>>> A B A XOR B
>>> 0 0 0
>>> 0 1 1
>>> 1 0 1
>>> 1 1 0

>> http://en.wikipedia.org/wiki/Hamming...ial_properties

> Actually no, but it's the number of bits set after the XOR, not the value
> of the XOR operation (which in your example would be 6 in decimal)

Where does 6 come from?

v1 =

1 1 1 0

v2 =

0 1 0 0

x_or =

1 0 1 0

sum_xor =

2

5. ## Re: Hamming distance = XOR?

saneman wrote:
> "Joachim Schmitz" skrev i en
> meddelelse news:g1j79o\$kdr\$1@online.de...
>> Joachim Schmitz wrote:
>>> saneman wrote:
>>>> The hamming distance (HD) measures the number of different bits in
>>>> two bitpatterns:
>>>>
>>>> v1 = [1 1 1 0]
>>>> v2 = [0 1 0 0]
>>>>
>>>> HD = 2
>>>>
>>>> But is the hamming distance not just a basic XOR operation:
>>>>
>>>> INPUT OUTPUT
>>>>
>>>> A B A XOR B
>>>> 0 0 0
>>>> 0 1 1
>>>> 1 0 1
>>>> 1 1 0
>>> http://en.wikipedia.org/wiki/Hamming...ial_properties

>> Actually no, but it's the number of bits set after the XOR, not the
>> value of the XOR operation (which in your example would be 6 in
>> decimal)

>
> Where does 6 come from?
>
> v1 =
>
> 1 1 1 0
>
>
> v2 =
>
> 0 1 0 0
>
>
> x_or =
>
> 1 0 1 0
>
>
> sum_xor =
>
> 2

01010 is 18 decimal. 2nd and 4th bit set. In the original it was 0110, 2nd
and 3rd bit set, and that is 6 decimal.

Bye, Jojo

6. ## Re: Hamming distance = XOR?

On May 28, 11:58 am, "saneman" wrote:
> The hamming distance (HD) measures the number of different bits in two
> bitpatterns:
>
> v1 = [1 1 1 0]
> v2 = [0 1 0 0]
>
> HD = 2
>
> But is the hamming distance not just a basic XOR operation:
>
> INPUT OUTPUT
>
> A B A XOR B
> 0 0 0
> 0 1 1
> 1 0 1
> 1 1 0

No, it's a XOR operation and then take the result and apply it to a
function that counts bits in an integer.

-- snip.c --
#include
#include

/* unsigned char bit_tbl[256] = { ... } */

uint32_t hd(uint32_t a, uint32_t b);

int main(void) {

uint32_t a = 6, b = 42;

printf("hd(%" PRIu32 ", %" PRIu32 ") = %" PRIu32 "\n",
a, b, hd(a, b));

return 0;
}

uint32_t hd(uint32_t a, uint32_t b) {

uint32_t c = a ^ b;

return bit_tbl[c & 0xffu] +
bit_tbl[(c >> 8) & 0xffu] +
bit_tbl[(c >> 16) & 0xffu] +
bit_tbl[(c >> 24) & 0xffu];
}
-- snip.c --

7. ## Re: Hamming distance = XOR?

>The hamming distance (HD) measures the number of different bits in two
>bitpatterns:
>
>v1 = [1 1 1 0]
>v2 = [0 1 0 0]
>
>HD = 2
>
>But is the hamming distance not just a basic XOR operation:
>
>INPUT OUTPUT
>
>A B A XOR B
>0 0 0
>0 1 1
>1 0 1
>1 1 0

Hamming distance is a bitwise XOR, followed by counting the 1 bits
in that result.