汉明距离问题描述问题解决
问题的说明
两个整数之间的汉明距离是指两个数字与二进制比特的不同位置对应的数量。
给定两个整数x和y,计算它们之间的汉明距离。
输入: x=1,y=4
输出: 2
说明:
1(0001 ) ) ) )。
4(0(1)0) ) ) ) ) )。
。
上面的箭头表示与二进制位对应的不同位置。
求解问题的汉明距离在很多领域被广泛应用。 在编码理论中用于错误检测,在信息论中量化字符串之间的差异。
两个整数之间的汉明距离是对应位置的数字不同的位数。
根据以上定义,提出了仅在输入比特不同时输出1的XOR的比特运算。
要计算x和y之间的汉明距离,可以先计算x XOR y,然后在统计结果中计算等于1的位数。
现在,原始问题已转换为比特数问题。 位数有各种各样的想法,以下方法进行介绍。
方法一:内置位计数功能
class solution { publicinthammingdistance (intx,int y ) returninteger.bitcount ) x^y; }} 方法二:移位
这里采用右移的话,各位置会向最右边移动。 移位后,检查最右边的比特是否为1即可。 要检查最右边的位是否为1,请使用模操作(i % 2)或AND操作(i 1 )。 任何操作都屏蔽最右边位以外的位。
class solution { publicinthammingdistance (intx,int y ) intxor=x^y; int distance=0; wile(xor!=0) if(xor%2==1) distance =1; xor=xor 1; }返回距离; }} 方法三:可耐的滑板算法
想法
方法二是逐位移动,逐位比较边缘位置是否为1。 用更快的方法找到等于1的位数。
是否可以跳过两个1之间的0,就像人的直观计数位为1的位数一样。 例如,10001000。
在上例中,如果遇到最右边的1后,可以跳过中间的0,直接跳到下一个1,效率会变高。
这是能耐受的滑板计数算法的基本思想。 该算法使用特定的比特和算术运算,去除等于1的最右边比特。
对number和number-1执行AND位运算将删除等于原始数字number最右边1的位。
根据以上想法,通过两次迭代可以知道10001000中1的位数,不需要8次。
class solution { publicinthammingdistance (intx,int y ) intxor=x^y; int distance=0; wile(xor!=0) { distance =1; //removetherightmostbitof '1' xor=xor (xor-1 ); }返回距离; }