汉明距离

本文由Faye_Zuo发布于http://www.cnblogs.com/zuofeiyi/, 本文可以被全部的转载或者部分使用，但请注明出处.

最近算法和数据结构暂时告一段落，准备重新回到leetcode刷题去。这道题目叫做hamming distance, accepted 70%，easy. 但是我没有做出来，思路是对的。其实这道题考察的是位运算，但是我基础烂的千疮百孔，慢慢补吧！

Hamming Distance(461)

The Hamming Distance between two integers is the number of positions at which the corresponding bits are different.

Given two integers x and y,calculate the Hamming distance.

一、什么是Hamming Distance?

中文译为汉明距离。指的是不同整数的对应位置上（二进制）几个不同的字节的个数。

二、我的解题思路

1.首先计算出一个整数的二进制；

2.再对这两个整数的二进制进行比较，如果不一样，count+1;

3.返回count;

三、总结

下面是我编写的程序，当然我编写出来的是千疮百孔版本，经过某位大牛调整，变成以下版本。主要我一定要总结一下我的问题所在：

在确保能够run的前提下，找错误不能想当然的胡乱试。要根据自己的思路去print，然后一定要跟着程序执行的顺序，一大块一大块的查找。然后在一小块一小块的查找。

1.对两个二进制进行比较的函数写错，思维不缜密。尤其没有考虑到两个二进制可能有长度不一样的可能性。

2.在对两个数组的元素进行比较的时候，我写的是if(BinaryList1[i]！=BinaryList2[i])。这样的写法很难干净，换做下面写法，真的是干净太多了

int a = 0;
int b = 0;

if (i < BinaryList1.size()) {

 a = BinaryList1.get(i);

 }


if (i < BinaryList2.size()) {
          b = BinaryList2.get(i);
        }
        if (a != b) {
          count++;
        }
      }

3.感觉自己的程序差在逻辑上，思维上。当然手写的感觉也相当差，估计这个问题只有靠多做题来弥补了。问题是不要怕难啊！

import java.util.ArrayList;

import Marth2017.HammingDistance.Solution;

public class HammingDistance1 {

  public static void main(String[] args) {
    int b = Solution.HammingDistance(35, 14);
    System.out.println("1:" + b);
    System.out.println("===================");

  }

  public static ArrayList<Integer> IntegerToBinary(int n) {
    ArrayList<Integer> BinaryList = new ArrayList<Integer>();
    while (n != 0) {
      BinaryList.add(n % 2);
      n = n / 2;
      continue;
    }
    System.out.println("2:" + BinaryList.size());

    for (int k = 0; k < BinaryList.size(); k++) {
      System.out.print(BinaryList.get(k) + " ");
    }
    System.out.println();

    return BinaryList;
  }

  public static class Solution {
    public static int HammingDistance(int x, int y) {
      int count = 0;
      ArrayList<Integer> BinaryList1 = new ArrayList<Integer>();
      ArrayList<Integer> BinaryList2 = new ArrayList<Integer>();
      BinaryList1 = IntegerToBinary(x);
      BinaryList2 = IntegerToBinary(y);
      for (int i = 0; i < Math.max(BinaryList1.size(), BinaryList2.size()); i++) {
        int a = 0;
        int b = 0;
        if (i < BinaryList1.size()) {
          a = BinaryList1.get(i);
        }
        if (i < BinaryList2.size()) {
          b = BinaryList2.get(i);
        }
        if (a != b) {
          count++;
        }
      }

      return count;
    }
  }
}

四、答案解析（看了答案解析，我一口老血要喷出来的节奏）：

按位分别取出两个数对应位上的数并异或，我们知道异或的性质上相同的为0，不同的为1，我们只要把为1的情况累加起来就是汉明距离了。

注意：(x & (1 << i))和(y & (1 << i)))其实就是一步一步的取位比较的算法，可强行记忆。

100011 x

001110 y

^^^^^^

x, i=0

000001 &

100011

000001

y, i=0

001110 &

000001

000000

x, i=1

000010 &

100011

000010

y, i=1

001110 &

000010

x, i=2

000100 &

100011

000000

y, i=2

001110 &

000100

000000 ^

000100

000100=4

public static class Solution {
    public static int hammingDistance(int x, int y) {
      int count = 0;
      for (int i = 0; i < 32; i++) {
        if (((x & (1 << i)) ^ (y & (1 << i))) != 0) {
          count += 1;
        }
      }
      return count;

    }
  }

补充知识点：位运算

1.什么是位运算？

位运算是直接对二进制进行的计算。

2.与运算：&

3.或运算：|

4.异或运算：^

5.左移：<<

3<<2:3*2（2）=12

左移几位其实就是该数据乘以2的几次方

6.右移：>>

6>>1:6/2(1)=3

右移其实就是该数据除以2的次幂

PS:右移如高位出现1，则拿1补位

这道题学完以后，虽然过程烦烦的，总算让我基本搞懂了

1.位运算，虽然运用起来肯定还是问题很多。

2.查找错误的大方法：

（1）按照思路先大块查找，再小块查找

（2）学会跟上计算机的思路

3.还让我见识到自己独立编写代码的不易，

希望下道题练完有新的收获！