[코딩연습] Hamming Distance 해밍거리 구하기

 

LeetCode 문제 중 난이도 Easy인 Hamming Distance이다. 문제 링크는 포스팅의 맨 마지막에 추가하였다. 언어는 Java를 사용했다.

 

  문제해석
두 정수 사이의 해밍거리는 상응하는 위치에서 값이 다른 비트의 개수이다.
두 정수 x,y를 입력으로 받아 해밍거리를 구하여라.

* x,y는 0 이상 2^31 이하

 

 

 

 

비트연산자를 이용하면 서로 다른 비트만 1로 표시할 수 있다. 

 

0101 ^ 0100 = 0001

 

100111 ^ 101011 = 001100

 

비트연산자란?

 

 

입력 받은 x와 y에 XOR 연산을 하면 x와 y에서 비트값이 다른 위치의 비트를 1로 바꾸어다. 그 결과값에서 1의 개수를 리턴하면 된다. 자바에서 제공해주는 Integer.bitCount를 사용하면 1줄만에 해결이 가능하다.

public class Solution {
    public int hammingDistance(int x, int y) {
        return Integer.bitCount(x^y);
    }
}

 

 

하지만 왠지 이 방법은 너무 치사한(?)것 같으니 비트의 개수를 직접 세어 주자.

 

 

 

 

어떤 숫자에서 1을 빼면 마지막 1이 있는 위치부터 끝까지 비트가 바뀐다

 

1001100 - 1 = 1001011

 

그 상태에서 원래의 숫자와 AND(&)연산을 하면 맨 오른쪽의 1이 사라지게 된다.

 

1001100 & 1001011 = 1001000

 

 

 

 

위의 원리를 이용해 코드에 적용해 보자. x^y의 결과값이 0이 될 때까지 오른쪽에서부터 1을 차례로 없애주고 count를 1씩 늘린다. 마지막에는 count 값을 리턴한다.

class Solution {
    public int hammingDistance(int x, int y) {
        int xor=x^y, count=0;
        
        while(xor!=0) {
            xor=xor&(xor-1);
            count++;
        }
        return count;
    }
}

연산 횟수의 최댓값은 Integer의 비트수로 상수로 정해져 있으니 시간복잡도는 O(1)이고 공간복잡도도 O(1)이다.