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 < 231.
Example 1:
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.
题目大意
在信息论中，两个等长字符串之间的汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
解题思路
使用异或运算，将问题转化为求异或结果’1’的个数的问题。
code-java：
class Solution {
public int hammingDistance(int x, int y) {
return Integer.bitCount(x ^ y);
}
code-Python：
class Solution:
def hammingDistance(self, x: int, y: int) -> int:
return bin(x ^ y).count('1')
使用右移或者左移运算符，将每一位与1按位与运算（或与2取模运算），循环之后即可得出’1’的个数。
public int hammingDistance(int x, int y) {
int xor = x ^ y;
int distance = 0;
while (xor != 0 ){
if ((xor&1) == 1)
// if ((xor%2) == 1)
distance += 1;
xor = xor >> 1;
}
return distance;
}
布赖恩·克尼根位计数算法的基本思想是：使用特定比特位和算术运算移除等于 1 的最右比特位。
当我们在 number 和 number-1 上做 AND 位运算时，原数字 number 的最右边等于 1 的比特会被移除。
code-java：
class Solution {
public int hammingDistance(int x, int y) {
int xor = x ^ y;
int distance = 0;
while (xor != 0) {
distance += 1;
// remove the rightmost bit of '1'
xor = xor & (xor - 1);
}
return distance;
}
}
补充知识点：
在信息论中，两个等长字符串之间的 汉明距离（英语：Hamming distance）是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。
例如：
- 1011101与 1001001之间的汉明距离是2。
- 2143896与 2233796之间的汉明距离是3。
- ” toned“与” roses“之间的汉明距离是3。
Original: https://www.cnblogs.com/ancientlian/p/14317727.html
Author: Lian_tiam
Title: 461. Hamming Distance
原创文章受到原创版权保护。转载请注明出处：https://www.johngo689.com/642650/
转载文章受原作者版权保护。转载请注明原作者出处！