欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode Hot 热题100 算法题 461.汉明距离-算法&测试-easy模式

程序员文章站 2024-03-22 14:17:34
...

LeetCode Hot 热题100 算法题 461.汉明距离-算法&测试-easy模式

两个整数之间的汉明距离指的是这两个数字对应的二进制位不同位置的数目。
给出两个整数x和y,计算它们之间的汉明距离。
示例:x=1, y=4
输出:2

package leetcode.medium;

//461.汉明距离
public class Solution461 {
	public static void main(String[] args) {
		int x=12,y=9;
		
		S461HanMingDistance testDistance = new S461HanMingDistance();
		System.out.println(testDistance.calDist(x, y));
	}
}

//汉明距离:将两个数 二进制进行异或运算,统计结果中1的个数
class S461HanMingDistance{
	//法1:内置方法bitCount
	public int calDist(int x,int y) {
		return Integer.bitCount(x^y);
	}
	
	//法2:%2判断最右侧那位是否为1,右移从而判断每一位
	public int calDistance(int x,int y) {
		int dist=0;
		long xor = x^y;
		while (xor!=0) {
			if (xor%2==1) {
				dist++;
			}
			xor = xor >> 1;
		}
		return dist;
	}
	
	//法3:布莱恩 克尼根算法
	//遇到最右边的1后,跳过中间的0,直接跳到下一个1
	// num & (num-1) 原数字最右边等于1的比特被移除
	public int hanMingDist(int x,int y) {
		int dist=0;
		long xor=x^y;
		while(xor!=0) {
			dist++;
			xor = xor & (xor-1);
		}
		return dist;
	}	
}

参考:
https://leetcode-cn.com/problems/hamming-distance/solution/yi-ming-ju-chi-by-leetcode