해밍 거리 (Hamming Distance)?
설명:
해밍 거리는 두 이진 문자열 간에 서로 다른 비트의 개수를 의미합니다. 즉, 두 개의 동일한 길이의 문자열에서 각 위치에서 다른 값을 가진 비트의 수를 측정하는 데 사용됩니다. 이는 주로 오류 검출 및 교정, 데이터 전송에서 사용됩니다.
사용 사례:
- 오류 검출 및 교정: 데이터 전송 중 발생할 수 있는 비트 오류를 탐지하고 교정하는 데 사용됩니다. 해밍 코드를 사용하면 해밍 거리가 1인 경우, 즉 한 비트만 다른 경우 오류를 교정할 수 있습니다.
- 유사도 측정: 해밍 거리는 두 개의 이진 벡터가 얼마나 다른지를 측정할 수 있어 이미지 처리나 텍스트 유사도 측정 등에서 사용될 수 있습니다.
JavaScript 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function hammingDistance(x, y) {
// 두 숫자를 XOR 연산하여 다른 비트 위치 찾기
let xor = x ^ y;
let distance = 0;
// XOR 결과에서 1의 개수를 세면 다른 비트의 개수를 구할 수 있음
while (xor > 0) {
distance += xor & 1; // 마지막 비트가 1이면 거리 증가
xor >>= 1; // 비트를 오른쪽으로 한 칸 이동
}
return distance;
}
// 사용 예시
console.log(hammingDistance(3, 1)); // 출력: 1 (3: 011, 1: 001, 해밍 거리: 1)
설명:
- 두 숫자
x와y를 XOR 연산하면 서로 다른 비트의 위치가 1로 표시됩니다. - 그 후, XOR 결과에서 1의 개수를 세어 해밍 거리를 계산합니다. 각 1은 두 숫자 사이의 다른 비트 하나를 의미합니다.
Rust 예제
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fn hamming_distance(x: i32, y: i32) -> i32 {
let mut xor = x ^ y;
let mut distance = 0;
while xor > 0 {
distance += xor & 1; // 마지막 비트가 1이면 거리 증가
xor >>= 1; // 비트를 오른쪽으로 이동
}
distance
}
fn main() {
let x = 3;
let y = 1;
println!("{}", hamming_distance(x, y)); // 출력: 1 (3: 011, 1: 001, 해밍 거리: 1)
}
설명:
- Rust에서도 JavaScript와 마찬가지로 두 숫자를 XOR 연산하여 다른 비트를 찾습니다.
xor & 1을 통해 마지막 비트가 1인지 확인하고, 1이면 해밍 거리를 증가시킵니다. 그런 다음,xor값을 오른쪽으로 이동하여 다음 비트를 검사합니다.
요약:
해밍 거리는 두 이진 값 사이에서 다른 비트의 수를 측정하는 방법입니다. 이 방법은 주로 오류 검출 및 교정에서 사용되며, 유사도 측정에서도 중요한 역할을 합니다. XOR 연산을 통해 두 값의 다른 비트를 찾고, 이를 통해 해밍 거리를 계산할 수 있습니다.
Hamming Distance?
Explanation:
The Hamming Distance is the number of differing bits between two binary strings. It is used to measure how many bit positions differ between two equal-length binary strings. This concept is commonly applied in error detection, correction, and data transmission.
Use Cases:
- Error Detection and Correction: Hamming distance is used in detecting and correcting bit errors during data transmission. Using Hamming codes, errors can be corrected if the Hamming distance between two data points is 1 (i.e., only one bit is different).
- Similarity Measurement: Hamming distance can be used to measure the difference between two binary vectors, which is useful in applications like image processing or text similarity analysis.
JavaScript Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
function hammingDistance(x, y) {
// XOR the two numbers to find differing bit positions
let xor = x ^ y;
let distance = 0;
// Count the number of 1s in the XOR result to get the Hamming distance
while (xor > 0) {
distance += xor & 1; // Increment distance if the last bit is 1
xor >>= 1; // Shift bits to the right
}
return distance;
}
// Example usage
console.log(hammingDistance(3, 1)); // Output: 1 (3: 011, 1: 001, Hamming distance: 1)
Explanation:
- By XORing the two numbers
xandy, we can find the positions where the bits differ. - Then, by counting the number of 1s in the XOR result, we can calculate the Hamming distance. Each 1 represents a differing bit between the two numbers.
Rust Example
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
fn hamming_distance(x: i32, y: i32) -> i32 {
let mut xor = x ^ y;
let mut distance = 0;
while xor > 0 {
distance += xor & 1; // Increment distance if the last bit is 1
xor >>= 1; // Shift bits to the right
}
distance
}
fn main() {
let x = 3;
let y = 1;
println!("{}", hamming_distance(x, y)); // Output: 1 (3: 011, 1: 001, Hamming distance: 1)
}
Explanation:
- In Rust, similar to JavaScript, XOR is used to find the differing bit positions between two numbers.
- We use
xor & 1to check if the last bit is 1, which indicates a differing bit, and increment the Hamming distance accordingly. We then shift thexorvalue to the right to check the next bit.
Summary:
The Hamming Distance measures the number of differing bits between two binary values. It is primarily used in error detection and correction and plays a vital role in similarity measurement. By applying XOR between two values, we can find their differing bits and calculate the Hamming distance.