leetcode461. 汉明距离

leetcode 461. 汉明距离

题目描述

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4 输出：2 解释： 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。 示例 2：

输入：x = 3, y = 1 输出：1

提示：

0 <= x, y <= 231 - 1

来源：力扣（LeetCode） 链接：https://leetcode.cn/problems/hamming-distance 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

法1

异或数1
二进制数只有01,异或操作相同为0,不同为1,我们使用异或操作不同的位置就变成1,数1的个数就为不同的个数\

1. 异或
2. 计算个数:使用Brian Kernighan算法算法

• 时间复杂度(O(n))
• 空间复杂度(O(1))

执行结果

法1

func hammingDistance(x int, y int) int {
 x ^= y//异或
 y = 0
 for x > 0 {//数1Brian Kernighan算法
  x ^= x - 1
  y++
 }
 return y
}

执行结果： 通过 显示详情 查看示例代码 添加备注

执行用时： 0 ms , 在所有 Go 提交中击败了 100.00% 的用户 内存消耗： 1.8 MB , 在所有 Go 提交中击败了 84.19% 的用户 通过测试用例： 149 / 149 炫耀一下: