[비트 연산 (Bitwise)] LC #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, return the Hamming distance between them.

Example 1:

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.

Example 2:

Input: x = 3, y = 1
Output: 1

Constraints:


문제 링크: https://leetcode.com/problems/hamming-distance/

1. 문제의 핵심: XOR(^) 연산으로 차이점만 남기기

이 문제는 '비트가 다른 위치의 개수'를 묻고 있습니다. 비트 연산에서 두 비트가 다를 때만 `1`을 반환하는 연산자는 바로 XOR(^)입니다.

핵심 아이디어: x ^ y를 계산하면, 두 숫자의 비트가 다른 위치만 `1`로 표시된 결과가 나온다.

예제 1을 보면, x = 1 (0001), y = 4 (0100) 입니다. x ^ y를 계산하면 0001 ^ 0100 = 0101 (십진수 5)가 됩니다. 이제 문제는 "숫자 5의 이진 표현에서 1의 개수는 몇 개인가?"로 단순화됩니다.

2. 해결 전략: 1의 개수 세기 (Built-in Function 활용)

특정 숫자의 이진 표현에서 `1`의 개수를 세는 것을 '비트 카운팅' 또는 'population count'라고 합니다. 대부분의 언어는 이를 위한 효율적인 내장 함수를 제공합니다. Java에서는 Integer.bitCount()를 사용하면 됩니다.

3. Java 코드 구현 (가장 간결한 풀이)

위 아이디어를 코드로 옮기면 단 한 줄로 문제를 해결할 수 있습니다. 

class Solution {
    public int hammingDistance(int x, int y) {
        // 1. x와 y의 비트가 다른 부분만 1로 만든다.
        int xorResult = x ^ y;

        // 2. xorResult에서 1의 개수(set bit)를 센다.
        return Integer.bitCount(xorResult);
    }
}

💡 코드 세부 포인트