2018-07-30

leetcode-461 Hamming Distance

461. Hamming Distance

Description

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:

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.

Analyse

这道我理解错了题意，理解成了两个不同位之间的距离，实际上要算的是number of positions at which the corresponding bits are different，也就是不同的位的 数量

下面是正确写法，然而不算我自己写出来的，我在看错题意而去搜其他人的做法的时候看到了这个

先用异或找出两个数的二进制中不同的地方，然后数 1 的个数

int hammingDistance(int x, int y) {
    int r = x ^ y;
    int count = 0;
    while (r != 0)
    {
        if (r & 1 == 1)
        {
            ++count;
        }
        r = r >> 1;
    }

    return count;
}

这道题在这里就结束了

下面是我写的计算两个不同位之间距离的代码，以及当时不成熟的想法

思路是先x ^ y, 得到一个新的数，里面的两个 1 就是两个数的二进制不同的地方（这里其实能看出我把题看错了，不可能都只有两个不同的地方）

然后算出两个 1 的 index，再减一下就是不同位之间的距离了（这里我又走了远路，上面正确答案里在一个循环里 &1，再加一个计数器就能解决这个问题了）

下面这句代码可以提出 x 的最后一个 1，把其他位全变成 0

1	int r = x & (-x);

举个例子


x	00010100
-x（x 按位取反+1）	11101100
r = x & (-x)	00000100

算r的二进制中 1 的 index 用到了 MIT 公开课里的代码

这段是用来算$log_2{(x)}$的，也能用来算 1 的 index

const uint64_t deBruijn = 0x022fdd63cc95386d;
const unsigned int convert[64] =
    { 0, 1, 2, 53, 3, 7, 54, 27,
    4, 38, 41, 8, 34, 55, 48, 28,
    62, 5, 39, 46, 44, 42, 22, 9,
    24, 35, 59, 56, 49, 18, 29, 11,
    63, 52, 6, 26, 37, 40, 33, 47,
    61, 45, 43, 21, 23, 58, 17, 10,
    51, 25, 36, 32, 60, 20, 57, 16,
    50, 31, 19, 15, 30, 14, 13, 12};

r = convert[(r * deBruijn) >> 58];

这是我当时的完整代码，并不能 AC，但好歹学到了点位运算的知识

int indexOfOne(int x)
{
    int r = x & (-x);
    const uint64_t deBruijn = 0x022fdd63cc95386d;
    const unsigned int convert[64] =
        { 0, 1, 2, 53, 3, 7, 54, 27,
        4, 38, 41, 8, 34, 55, 48, 28,
        62, 5, 39, 46, 44, 42, 22, 9,
        24, 35, 59, 56, 49, 18, 29, 11,
        63, 52, 6, 26, 37, 40, 33, 47,
        61, 45, 43, 21, 23, 58, 17, 10,
        51, 25, 36, 32, 60, 20, 57, 16,
        50, 31, 19, 15, 30, 14, 13, 12};

    r = convert[(r * deBruijn) >> 58];
    return r;
}

int hammingDistance(int x, int y) {
    int r = x ^ y;
    int index_1 = indexOfOne(r);
    r = r >> (index_1 + 1);
    int index_2 = indexOfOne(r);
    return index_2 + 1;
}

X

leetcode-461 Hamming Distance

Description

Analyse

References