home

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

Steps

Convert whatever data you have into byte arrays

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

XOR the two byte arrays

func xorByteArrays(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
}
func xorByteArrays(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 bits that are set to 1 in the resulting byte array

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
  oneSetBitByteArray := []byte{
      0b00000001,
      0b00000010,
      0b00000100,
      0b00001000,
      0b00010000,
      0b00100000,
      0b01000000,
      0b10000000,
  }

  hammingDist := 0

  for _, b := range b1 {
    for _, oneSetBitByte := range oneSetBitByteArray {
      if (b & oneSetBitByte) > 0 {
        hammingDist += 1
      }
    }
  }

  return hammingDist
}
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
  oneSetBitByteArray := []byte{
      0b00000001,
      0b00000010,
      0b00000100,
      0b00001000,
      0b00010000,
      0b00100000,
      0b01000000,
      0b10000000,
  }

  hammingDist := 0

  for _, b := range b1 {
    for _, oneSetBitByte := range oneSetBitByteArray {
      if (b & oneSetBitByte) > 0 {
        hammingDist += 1
      }
    }
  }

  return hammingDist
}