本文主要是介绍【Java】LeetCode - 位运算 - #461 汉明距离,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
力扣力扣 https://leetcode-cn.com/problems/hamming-distance/
#461 汉明距离
汉明距离广泛应用于多个领域。在编码理论中用于错误检测,在信息论中量化字符串之间的差异。
两个整数之间的汉明距离是对应位置上数字不同的位数。
两个整数之间的汉明距离指的是这两个数字对应二进制位不同的位置的数目。
给出两个整数 x
和 y
,计算它们之间的汉明距离。
方法一:内置位计数功能
大多数编程语言中,都存在各种内置计算等于 1 的位数函数。
class Solution {public int hammingDistance(int x, int y) {return Integer.bitCount(x ^ y); }
}
方法二:移位
为了计算等于 1
的位数,可以将每个位移动到最左侧或最右侧,然后检查该位是否为 1
。
class Solution {public int hammingDistance(int x, int y) {int z = x ^ y;int distance = 0;while(z != 0){if(z % 2 == 1){distance +=1;}z = z >> 1;}return distance;}
}
方法三:布赖恩·克尼根算法
方法二是逐位移动,逐位比较边缘位置是否为 1。寻找一种更快的方法找出等于 1 的位数。
是否可以像人类直观的计数比特为 1 的位数,跳过两个 1 之间的 0。例如:10001000。
上面例子中,遇到最右边的 1 后,如果可以跳过中间的 0,直接跳到下一个 1,效率会高很多。
这是布赖恩·克尼根位计数算法的基本思想。该算法使用特定比特位和算术运算移除等于 1 的最右比特位。
当我们在 number 和 number-1 上做 AND 位运算时,原数字 number 的最右边等于 1 的比特会被移除。
基于以上思路,通过 2 次迭代就可以知道 10001000
中 1 的位数,而不需要 8 次。
class Solution {public int hammingDistance(int x, int y) {int z = x ^ y;int distance = 0;while(z != 0){distance += 1;z = z & (z-1);}return distance;}
}
这篇关于【Java】LeetCode - 位运算 - #461 汉明距离的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!