Hamming Distance

Hamming Distance

문제 내용

Hamming Distance를 구하라

 

접근 방법

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;
};

 

$ 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;
};

 

그런데 문제 풀이 내용을 읽어보니 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)이라고 하는데 뭐가 다른건가 모르겠다.