leetcode：461. 汉明距离

题目

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例：

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

解答 & 代码

分为两步：

  • 两个数 x、y 进行异或运算，得到的结果的二进制串中 1 的个数就是汉明距离

  • 统计一个数 n 的二进制串中 1 的个数：Brian Kernighan 算法

    • 令 [简单] 461. 汉明距离 - 图1，那么 f(x) 恰为 x 删去其二进制表示中最右侧 1 的结果
      • eg. [简单] 461. 汉明距离 - 图2

    • 不断让 n=n&(n-1)，这样每次与操作都删除了 n 的二进制表示最右侧的 1，直到 n 变为 0 时，与操作的次数就是二进制表示中 1 的个数

      1. class Solution {
      2. public:
      3. int hammingDistance(int x, int y) {
      4.      // x、y 求异或，得到的结果 xor_xy 中 1 的个数就是两个数字的汉明距离
      5.    int xor_xy = x ^ y;
      7.      // 统计 xor_xy 二进制串中 1 的个数：
      8.      // xor_xy = xor_xy & (xor_xy - 1)，直到 xor_xy 变为 0，与操作的次数就是 1 的个数
      9.    int cnt = 0;
      10.    while(xor_xy != 0)
      11.    {
      12.        ++cnt;
      13.        xor_xy &= (xor_xy - 1);
      14.    }
      15.    return cnt;
      16. }
      17. };

      复杂度分析：

  • 时间复杂度 O(log C)：C 值元素的数据范围，本题中 C= [简单] 461. 汉明距离 - 图3。因为 Brian Kernighan 算法统计一个数 n 的二进制串中的 1 比特个数的时间复杂度为 log n

  • 空间复杂度 O(1)

执行结果：

  1. 执行结果：通过
  3. 执行用时：0 ms, 在所有 C++ 提交中击败了 100.00% 的用户
  4. 内存消耗：5.9 MB, 在所有 C++ 提交中击败了 40.81% 的用户