Hamming Distance

Hamming Distance

1. 문제 내용

Hamming Distance를 구하라

 

2. 접근 방법

Hamming distance는 기본적으로 두개의 integer를 bit로 변환했을 때, 몇개의 bit가 다른지 알아내는 문제이다.

예를 들어 2진수로

110001101

111000011

이 있다고 하면 다른 값은 위의 붉은색이 된다.

즉, 두개의 값의 차이가 나는 값, XOR로 대표 될 수 있다.

위의 값을 XOR해보자.

001001110

이 된다.

이제 1의 갯수를 구하면 답이 된다.

가장 쉬운 방법은 1bit씩 오른쪽으로 shift하면서 끝 값이 1인지만 확인 하면 된다.

var hammingDistance = function(x, y) {
    let xor = x ^ y;
    let count = 0;
    while(0 < xor){
        if(xor & 1) count++;
        xor = (xor >> 1);
    }
    
    return count;
};javascript

 

$O(N)$ 으로 해결이 가능한데, 조금더 빠른 방법은 없을까?

아래 XOR이 된 값을 보자.

001001110

1을 shift하면서 count하면 0도 Operation의 횟수에 포함 되게 된다.

그러면 1을 한번에 삭제 하는 방법은 없을까?

001001110

001001110 - 1

을 해보자.

001001110

001001101

두 값을 And 해보면

001001100이 된다.

가장 우측에 있던 1이 사라진것을 확인 할 수있다.

다시 한번더 해보자.

001001100 - 1

->

001001011

이 되고 AND를 해보면

001001000 역시 오른쪽 1이 사라졌다.

이런식으로 count하면 Time Complexity가 여전히 O(N)이지만 속도상으로 이득이 가능하다는 걸 생각 할 수 있다.

var hammingDistance = function(x, y) {
    let xor = x ^ y;
    let count = 0;
    while(0 < xor){
        count++;
        xor = xor & (xor-1);
    }
    
    return count;
};javascript

 

그런데 문제 풀이 내용을 읽어보니 Time Complexity는 O(1)이라고 한다. 그 이유는 number의 bit의 수가 정해져 있기 때문에, 가령 최대 32bit일 경우 32번 이상 interation을 돌지 않기 때문이라고 한다.

근데 이게... 난 잘 이해는 안간다 어쨌든 32bit 안에서 입력에 따라 유동이기 때문에 O(N)이라고 하는게 맞지 않나?

문제 내용에 만약에 Max Array 100 size인 array가 1부터 100 Size 사이에 있을 때 for loop를 이 size에 맞춰서 계산을 돌리면 우리는 O(N)이라고 하는데 뭐가 다른건가 모르겠다.