[알고리즘 문제] LeetCode - Hamming Distance

문제는 두 정수가 있을 때 해밍 거리는 구하면 된다. 즉 두 정수간의 해밍 거리는 비트가 다른 위치의 수를 구하면 되는 문제이다.

 

여기서 xor연산을 했는데, 두 정수를 xor연산을 하면 비트가 다른 부분만 1로표시가 된다.

그러면 xor한 숫자를 오른쪽으로 1,2,3...31번까지 시프트연산을 하면서 그 결과를 1과 and연산을 한다. 만약 1이 있으면 count가 1을 더한 것이다.

 

예를 들어 설명하면,

13 -> 1101
16 -> 10000

13 xor 16 : 29 -> 11101

이 되는데, 사실상 11101이 아니라, 0000 0000 0000 0000 0000 0000 0001 1101이 된다.

 

앞의 0을 다 짜르고 11101을 사용하는 것이며, for문에서 xor >> i은 xor의 모든 비트를 오른쪽으로 하나씩 이동하는 것이다. 

for문에서 i=0부터 시작하기 때문에 11101 & 00001을 하면 1의 자리 1이 같기 때문에 count에 1을 더한다. 

i=1일 때, 01110 & 00001을 하면 1의 자리가 1,0 서로 다르기 때문에 count=0을 더한다. 이 과정을 32번 반복하는데, 어짜피 11101을 제외한 앞 자리는 0이기 때문에 의미가 없다.

 

 

// Hamming Distance

class Solution {
    public int hammingDistance(int x, int y) {

        int xor = x ^ y;
        int count = 0;
        for (int i = 0; i < 32; i++) {
            count += (xor >> i) & 1;
        }
        return count;
    }
}