461. Hamming Distance

- 원문

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.

- 해석

두 정수 사이의 해밍 거리는 비트가 다른 위치의 갯수입니다.

두 개의 정수 x와 y가 주어지면, 해밍 거리를 계산하십시오.

Note:
0 ≤ x, y < 231.

Example:

Input: x = 1, y = 4

Output: 2

Explanation:
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑

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

- 기존 풀었던 방식

public class Solution {
    
    private String binaryNotation(int n){
		String result = "";
		int res;
		
		while(n > 0){
			res = n % 2;
			result = res + result;
			n /= 2;
		}
		
		return result;
	}
    
    public int hammingDistance(int x, int y) {
       		String sx, sy;
		
		if(x < y){
			int temp = x;
			x = y;
			y = temp;
		}
		
		sx = binaryNotation(x);
		sy = binaryNotation(y);

		int length = sx.length() - sy.length();
		
		for(int i = 0; i < length; i++){
			sy = "0" + sy;
		}

		int result = 0;

		for(int i = 0; i < sy.length(); i++){
			if(sx.charAt(i) != sy.charAt(i)){
				result++;
			}
		}
		
		return result;
    }
}

- 회고

난이도에 비해 너무 어렵게 풀었던 것 같다. 10진수를 2진수로 꼭 변경을 해야한다고 생각한 부분이 문제였던 것으로 보인다. 이 문제는 1line 짜리 API를 활용한 해결방안부터 조금 더 Simple한 해결방안이 존재해서 다음을 소개하고자 한다.

- 1line Solution

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

여기서 bitCount를 JavaAPI를 보면 메서드의 기능은 다음과 같다.

bitCount public static int bitCount(int i) 지정된 int의 2의 보수 바이너리 표현에서의, 1의 비트의 수를 돌려줍니다. 파라미터: i - 비트가 카운트 되는 값 반환값: 지정된int치의 2의 보수 바이너리 표현에서의, 1의 비트의 수.

그래서 Integer.bitCount에서 bit가 서로 다른 경우 1을 반환하는 XOR연산을 이용해서 bitCount를 사용하는 것으로 쉽게 구할 수 있다.

하지만 API를 이용하지 않고 푸는 것을 면접에서도 원할 수 있기 때문에 찾아보니 다음과 같은 솔루션이 있었다.

- 본인이 생각하기에 최적의 솔루션

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

이진수를 구하라는 얘기가 없으면 이진수를 굳이 만드려고 하지말고 비트 연산을 통해서 문제를 해결하도록 하자...