本文主要是介绍LeetCode--461. Hamming Distance 191. Number of 1 Bits 477. Total Hamming Distance，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
问题链接：
https://leetcode.com/problems/hamming-distance/
https://leetcode.com/problems/number-of-1-bits/
https://leetcode.com/problems/total-hamming-distance/
这三个都是有关hamming距离的问题，都是基于位运算相对简单基础的问题。
问题一：
求两个数的汉明距离，XOR操作即可，代码如下：
class Solution {public int hammingDistance(int x, int y) {int b=x^y,ret=0,mask=1;for(int i=0;i<31;i++){if((mask & b)!=0)ret++;mask<<=1;}return ret;}
}问题二：
求某个数二进制表达中1的个数，有两种方法，第一种用掩模的方法，第一种用代码如下：
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int ret=0,mask=1;for(int i=0;i<32;i++){if((n & mask) !=0)ret++;mask <<= 1;}return ret;}
}第二种使用n = n& (n-1)的操作来（从右往左）逐步消去二进制表达中的1来判断，每次消去一个1就计数器加1，代码如下：
public class Solution {// you need to treat n as an unsigned valuepublic static int hammingWeight(int n) {int p=0;while(n!=0){p++;n &= n-1;}return p;}
}问题三：基本可以基于问题一来做一个复杂度为O(n^2)的算法，很容易想到，代码如下：
class Solution {public int totalHammingDistance(int[] nums) {int sum=0;for(int i=0;i<nums.length-1;i++){for(int j=i+1;j<nums.length;j++){sum += hammingDistance(nums[i],nums[j]);}}return sum;}public static int hammingDistance(int x, int y) {int b=x^y,ret=0,mask=1;for(int i=0;i<31;i++){if((mask & b)!=0)ret++;mask<<=1;}return ret;}
}问题三还可以用如下时间复杂度O(32n)的算法解决：
class Solution {public int totalHammingDistance(int[] nums){int sum=0,n=nums.length;for(int i=0;i<32;i++){int n_bits1=0;for(int j=0;j<n;j++){if(((nums[j]>>i) & 1) != 0)n_bits1 += 1; }sum += (n - n_bits1) * n_bits1;}return sum;}
}
这篇关于LeetCode--461. Hamming Distance 191. Number of 1 Bits 477. Total Hamming Distance的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
