Calculating Hamming distances in Go

Jun 21, 2021

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

Steps

Convert whatever data you have into byte slices

func toByteSlice(s1 string) []byte {
  return []byte(s1)
}

XOR the two byte slices

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

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
}