Calculating Hamming distances in Go
I was looking for examples/tutorials on programs for finding the Hamming distance between two strings. The Hamming distance between two strings is the number of positions at which the corresponding bits are different.
Many of the examples I came across were simply comparing strings character by character. Don't do this.
The distance between the strings "A" and "B" is not 1, it is 2.
Thing | Value |
---|---|
ASCII code for A | 65 |
ASCII code for B | 66 |
65 in base 2 | 1000001 |
66 in base 2 | 1000010 |
Differing bits | 2 |
Hamming Distance | 2 |
Convert whatever data you have into byte slices
Go
func toByteSlice(s1 string) []byte {
return []byte(s1)
}
XOR the two byte slices
Go
func xorByteSlices(b1 []byte, b2 []byte) []byte {
b1 := []byte("kore nani ????")
b2 := []byte("kore nani neko")
b3 := make([]byte, len(b1))
for i := 0; i < len(b1); i++ {
b3[i] = b1[i] ^ b2[i]
}
return b3
}
Count the number of set bits that in the resulting slice
Go
func countSetBits(b1 []byte) int {
// instead of writing the slice manually
// you can start with 0b00000001 and perform a left shift before every &
// 0b00000001 << 1 == 0b00000010
oneSetBitByteSlice := []byte{
0b00000001,
0b00000010,
0b00000100,
0b00001000,
0b00010000,
0b00100000,
0b01000000,
0b10000000,
}
hammingDist := 0
for _, b := range b1 {
for _, oneSetBitByte := range oneSetBitByteSlice {
if (b & oneSetBitByte) > 0 {
hammingDist += 1
}
}
}
return hammingDist
}