461. 汉明距离

1 题目描述

2、题目说明

     【汉明距离】广泛应用于多个领域。在编码理论中用于错误检测，在信息论中量化字符串之间的差异。两个整数之间的汉明距离是对应位置上数字不同的位数。

 

方法一：内置位计数功能

思路及算法

大多数编程语言都内置了计算二进制表达中 1 的数量的函数。在工程中，可直接使用内置函数。

class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x ^ y);
    }
}

复杂度分析

• 时间复杂度：O(1)。不同语言的实现方法不一，我们可以近似认为其时间复杂度为 O(1)。

• 空间复杂度：O(1)。

方法二：移位实现位计数

循环对res进行判断，直到二进制数中的1全移除为止，每次移除计数+1

class Solution {
    public int hammingDistance(int x, int y) {
        int s = x ^ y, ret = 0;
        while (s != 0) {
            ret += s & 1;
            s >>= 1;
        }
        return ret;
    }
}

复杂度分析

时间复杂度：O(logC)，其中 C 是元素的数据范围，在本题中 logC=log2 ^31 =31。

空间复杂度：O(1)。