461. Hamming Distance

柔情只为你懂 2022-05-31 09:51 180阅读 0赞

> Description：

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

> Note:

0 ≤ x, y < 2^31.

> Example:

Input: x = 1, y = 4

Output: 2

Explanation:  
1 (0 0 0 1)  
4 (0 1 0 0)  
        ↑    ↑

The above arrows point to positions where the corresponding bits are different.

> Solution:

本质就是两个数的二进制表示所对应位置不同的数量，首先想到的就是通过“异或”  
方法一：  
利用JDK所提供的方法  
Integer.bitCount(int i):返回指定int值的二进制补码表示形式的1位的数量

public class Solution {
        public int hammingDistance(int x, int y) {
            return Integer.bitCount(x ^ y);
        }
    }

方法二：  
Java中int用32位表示，依次判断x和y的二进制表示的每一位数是否相同

public int hammingDistance(int x, int y) {
           int res = 0;
           for(int i = 0; i < 32; i++){
             res += (x & 1) ^ (y & 1);
             x = x >> 1;
             y = y >> 1;
           }
          return res;
        }

方法三：（自己首先想到的思路）  
首先计算出异或的结果，然后对结果进行计算，找1出现的次数

class Solution { 
        public int hammingDistance(int x, int y) {
            int sum = 0;
            int result = x ^ y;    
            while(result !=0){
                if((result&1)== 1){
                    sum ++;
                }
                result = result >> 1;
            }
            return sum;
        }
    }

上述代码优化后：

public int hammingDistance(int x, int y) {
        int xor = x ^ y, count = 0;
        for (int i=0;i<32;i++) 
            count += (xor >> i) & 1;
        return count;
    }