Hamming Distance

Algorithm
algorithm, leetcode

leetcode 문제링크

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
2
3
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

The above arrows point to positions where the corresponding bits are different.

나의 풀이

※ 해밍거리(Hamming Distance)
블록 부호 이론에서, 해밍 거리(Hamming距離, 영어: Hamming distance)는 곱집합 위에 정의되는 거리 함수이다. 대략, 같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지를 센다.

주어진 값들을 이진수 형태에서 비교해서 같은 위치에 다른 수가 몇개인지를 세면 되는 것 같다. 이진수로 바꾸는 방법은 toString 메소드를 사용했고, 수에 따라 같은 길이가 아닐 수 있으니 뒤의 수부터 비교해주기로 했다.
sort를 이용해 길이가 긴 수를 정해서 reduce를 통해 그 길이에 수가 둘 다 있으면 두 수(문자)를 비교해 다르면 누적에 1을 더하고 만약 위치에 수가 없으면 수가 있는 배열의 값이 ‘1’일 경우 더한다. 

1
2
3
4
5
6
7
8
9
10
11
12
13
// 56 ms
var hammingDistance = function(x, y) {
    const arr = [x.toString(2).split('').reverse(), y.toString(2).split('').reverse()].sort((a, b) => b.length - a.length);
    return arr[0].reduce((acc, item, index, array) => {
        if(arr[1][index] && arr[1][index] !== item) {
            return acc + 1
        } else if (!arr[1][index] && item === '1') {
            return acc + 1
        } else {
            return acc
        }
    }, 0)
};

다른 사람 풀이

이걸 한 줄로 푸네…

1
2
3
4
// 60ms
var hammingDistance = function(x, y) {
    return (x ^ y).toString(2).split('0').join('').length;
};

1. ^(Bitwise XOR)

^부분이 이해가 안되었는데 XOR이라는 연산자로 다음의 표와 같이 a와 b가 다른 경우 1을 산출한다고 한다.

a b a XOR b
0 0 0
0 1 1
1 0 1
1 1 0

비트 연산자는 피연산자를 10진수나 16진수나 8진수와 같은 숫자가 아니라, 32비트(0과 1)의 집합으로 표현한다.

1
2
3
4
.    9 (base 10) = 00000000000000000000000000001001 (base 2)
    14 (base 10) = 00000000000000000000000000001110 (base 2)
                   --------------------------------
14 ^ 9 (base 10) = 00000000000000000000000000000111 (base 2) = 7 (base 10)

그렇다면 위의 풀이에서 x, y 간의 배타적 논리합을 구해서 그 수의 이진수 표현(문자열) 중 문자 ‘0’을 제거하면(split(‘0’)) ‘1’만 남게 되는 데 이 1은 x, y가 같은 위치에 다른 문자였음을 의미하니까 그 길이를 구하면 원하는 결과를 얻을 수 있다.

다만, 왜 이 풀이가 내 풀이보다 느린 지 아직 잘 모르겠다. 처음에는 32비트 집합간의 비교라서 그런건가 했는데 비트가 더…느릴 수…있나? 왠지 환경에 따라 다를 것 같은 미미한 차이라…

Share Comments