[C++] 해밍 거리 (Hamming Distance)

참고: https://powerclabman.tistory.com/4

[C++] Bitwise Operator와 빠른 홀수, 짝수 찾기

 

📕 해밍 거리란?

같은 길이의 두 문자열에서, 같은 위치에서 서로 다른 기호들이 몇 개인지 세는 것을 뜻합니다.

 

두 문자열 A, B가 다음과 같을 경우

A = 1011

B = 1001

 

밑줄 친 부분을 고려하면, 해밍 거리는 1이 되겠죠

 

A = Hello!

B = Halro!

 

 이 경우에는 해밍 거리는 2가 됩니다.

 

저는 '비트 연산'을 활용해서

2개의 정수가 주어질 때, 해밍 거리가 몇 인지 구하는 알고리즘을 짜보려고 합니다.

 

📘 아이디어

임의의 두 정수 A, B가 다음과 같이 주어진다고 칩시다.

(부호 비트는 고려하지 않습니다.)

 

A = 1011 0101 (10 진수로 181)

B = 0011 0111 (10 진수로 55)

 

이 경우 '다른 비트'를 찾을 때 사용하기 좋은 연산자는 뭐가 있을까요?

 

아무래도 XOR 연산이 좋아 보입니다.

참고로 XOR 연산의 진리표는 다음과 같습니다.

 

A와 B의 비트가 다를 경우만 '1'

같을 경우는 '0'

 

해밍 거리를 계산하는데 딱 쓰기좋은 연산자입니다.

그래서 A^B를 구해보면 다음과 같습니다.

 

A = 1011 0101

B = 0011 0111

A^B = 1000 0010

 

A^B에서 1이 몇 개인지 카운팅하는 알고리즘만 추가로 짜면 되겠죠.

오른쪽 시프트 연산(>>)과 AND 연산을 이용해서 쉽게 구현할 수 있습니다.

 

📗 구현

#include <iostream>
using namespace std;

int hammingDistance(int x, int y) {
    int XORrst = x ^ y;
    int rst = 0;

    while (XORrst > 0)
    {
        rst += XORrst & 1;
        XORrst = XORrst >> 1;
    }
    return rst;
}

int main()
{
    int x;
    int y;

    cin >> x >> y;

    cout << hammingDistance(x, y) << endl;

    return 0;
}

 

 

실행결과입니다.

아주 잘나오네요.

 

오늘도 한 걸음 걸어가봅니다.